Document Open Access Logo

Point Location in Dynamic Planar Subdivisions

Authors Eunjin Oh, Hee-Kap Ahn

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2018.63.pdf
  • Filesize: 475 kB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • dynamic point location
  • general subdivision

Metrics

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

Abstract

We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number of edges in the subdivision. This answers a question posed by Snoeyink in the Handbook of Computational Geometry. When only deletions of edges are allowed, the update time and query time are just O(alpha(n)) and O(log n), respectively.

Cite As Get BibTex

Eunjin Oh and Hee-Kap Ahn. Point Location in Dynamic Planar Subdivisions. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.63

Author Details

Eunjin Oh
Hee-Kap Ahn

References

  1. Alfred V. Aho and John E. Hopcroft. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., 1974. Google Scholar
  2. 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
  3. Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn. Dynamic point location in general subdivisions. Journal of Algorithms, 17(3):342-380, 1994. Google Scholar
  4. Jon Louis Bentley and James B Saxe. Decomposable searching problems 1: Static-to-dynamic transformations. Journal of Algorithms, 1(4):301-358, 1980. Google Scholar
  5. 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
  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. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 2008. Google Scholar
  8. Jiří Matousěk. Efficient partition trees. Discrete &Computational Geometry, 8(3), 1992. Google Scholar
  9. Mark H. Overmars. Range searching in a set of line segments. Technical report, Rijksuniversiteit Utrecht, 1983. Google Scholar
  10. Mark H. Overmars and Jan van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problem. Information Processing Letters, 12(4):168-173, 1981. Google Scholar
  11. Neil Sarnak and Robert E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29(7):669-679, 1986. Google Scholar
  12. Jack Snoeyink. Point location. In Handbook of Discrete and Computational Geometry, Third Edition, pages 1005-1023. Chapman and Hall/CRC, 2017. Google Scholar
  13. Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, 1975. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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