Document Open Access Logo

Point Location in Incremental Planar Subdivisions

Author Eunjin Oh

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.51.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Eunjin Oh
  • Max Planck Institute for Informatics, Saarbrücken, Germany

Cite As Get BibTex

Eunjin Oh. Point Location in Incremental Planar Subdivisions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.51

Abstract

We study the point location problem in incremental (possibly disconnected) planar subdivisions, that is, dynamic subdivisions allowing insertions of edges and vertices only. Specifically, we present an O(n log n)-space data structure for this problem that supports queries in O(log^2 n) time and updates in O(log n log log n) amortized time. This is the first result that achieves polylogarithmic query and update times simultaneously in incremental planar subdivisions. Its update time is significantly faster than the update time of the best known data structure for fully-dynamic (possibly disconnected) planar subdivisions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Dynamic point location
  • general incremental planar subdivisions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Lars Arge, Gerth Stølting Brodal, and Loukas Georgiadis. Improved Dynamic Planar Point Location. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 305-314, 2006. Google Scholar
  2. Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn. Dynamic Point Location in General Subdivisions. Journal of Algorithms, 17(3):342-380, 1994. Google Scholar
  3. Jon Louis Bentley and James B. Saxe. Decomposable Searching Problems 1: Static-to-Dynamic Transformations. Journal of Algorithms, 1(4):297-396, 1980. Google Scholar
  4. Timothy M. Chan and Yakov Nekrich. Towards an Optimal Method for Dynamic Planar Point Location. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), pages 390-409, 2015. Google Scholar
  5. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete &Computational Geometry, 6(3):485-524, 1991. Google Scholar
  6. Siu-Wing Cheng and Ravi Janardan. New Results on Dynamic Planar Point Location. SIAM Journal on Computing, 21(5):972-999, 1992. Google Scholar
  7. Yi-Jen Chiang, Franco P. Preparata, and Roberto Tamassia. A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps. SIAM Journal on Computing, 25(1):207-233, 1996. Google Scholar
  8. Yi-Jen Chiang and Roberto Tamassia. Dynamization of the trapezoid method for planar point location in monotone subdivisions. International Journal of Computational Geometry & Applications, 2(3):311-333, 1992. Google Scholar
  9. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 2008. Google Scholar
  10. Michael T. Goodrich and Roberto Tamassia. Dynamic Trees and Dynamic Point Location. SIAM Journal on Computing, 28(2):612-636, 1998. Google Scholar
  11. Hiroshi Imai and Takao Asano. Dynamic orthogonal segment intersection search. Journal of Algorithms, 8(1):1-18, 1987. Google Scholar
  12. Kurt Mehlhorn and Stefan Näher. Dynamic fractional cascading. Algorithmica, 5(1):215-241, 1990. Google Scholar
  13. Eunjin Oh and Hee-Kap Ahn. Point Location in Dynamic Planar Subdivision. In Proceedings of the 34th International Symposium on Computational Geometry (SOCG 2018), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1-63:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.63.
  14. Franco P. Preparata and Roberto Tamassia. Fully Dynamic Point Location in a Monotone Subdivision. SIAM Journal on Computing, 18(4):811-830, 1989. Google Scholar
  15. Jack Snoeyink. Point Location. In Handbook of Discrete and Computational Geometry, Third Edition, pages 1005-1023. Chapman and Hall/CRC, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact