Parabola separation queries and their applicationto stone throwing

Given two sets A and B of m non-crossing line segments in the plane. we show how to compute in O(m log m) time a data structure that uses O(m) storage and supports the following query in O(log m) time: Given a parabola gamma : y = ax(2) + bx + c, does gamma separate A and B? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon of complexity n, we can answer such "such-throwing" queries in O(log(2) n) time, using O(n log n) storage and O(n log(2) n) preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.
Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
Issue Date
2007-08
Language
ENG
Keywords

VORONOI DIAGRAMS; RAY

Citation

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, v.17, no.4, pp.349 - 360

ISSN
0218-1959
DOI
10.1142/S0218195907002379
URI
http://hdl.handle.net/10203/7726
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
000251316600004.pdf(136.31 kB)Download
  • Hit : 1061
  • Download : 303
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0