Hierarchical decompositions and circular ray shooting in simple polygons

Cited 4 time in webofscience Cited 0 time in scopus
  • Hit : 451
  • Download : 221
A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon on n vertices can be answered in O(log(2) n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).
Publisher
SPRINGER
Issue Date
2004-10
Language
ENG
Article Type
Article
Keywords

TREES

Citation

DISCRETE COMPUTATIONAL GEOMETRY, v.32, no.3, pp.401 - 415

ISSN
0179-5376
DOI
10.1007/s00454-004-1098-2
URI
http://hdl.handle.net/10203/303
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
2002-016.pdf(201.4 kB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 4 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0