Cited By
View all- Chen JHuang QKanj IXia G(2024)Nearly Time-Optimal Kernelization Algorithms for the Line-Cover Problem with Big DataAlgorithmica10.1007/s00453-024-01231-686:8(2448-2478)Online publication date: 9-May-2024
Dynamic planar point location in optimal time
Pages 1003 - 1014
Abstract
In this paper we describe a fully-dynamic data structure that supports point location queries in a connected planar subdivision with n edges. Our data structure uses O(n) space, answers queries in O(logn) time, and supports updates in O(logn) time. Our solution is based on a data structure for vertical ray shooting queries that supports queries and updates in O(logn) time.
References
[1]
Lars Arge, Gerth Stølting Brodal, and Loukas Georgiadis. 2006. Improved dynamic planar point location. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. 305–314.
[2]
Lars Arge and Jeffrey Scott Vitter. 2003. Optimal External Memory Interval Management. SIAM J. Comput. 32, 6 (2003), 1488–1508.
[3]
Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn. 1994. Dynamic point location in general subdivisions. J. Algorithms 17, 3 (1994), 342–380.
[4]
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. 2002. Two Simplified Algorithms for Maintaining Order in a List. In 10th Annual European Symposium on Algorithms (ESA). 152–164.
[5]
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo Montes. 2017. File Maintenance: When in Doubt, Change the Layout!. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1503–1522.
[6]
Jon Louis Bentley. 1977. Algorithms for Klee's rectangle problems. (1977). Unpublished manuscript, Department of Computer Science, Carnegie-Mellon University.
[7]
Timothy M. Chan and Yakov Nekrich. 2015. Towards an Optimal Method for Dynamic Planar Point Location. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 390–409.
[8]
Timothy M. Chan and Yakov Nekrich. 2018. Towards an Optimal Method for Dynamic Planar Point Location. SIAM J. Comput. 47, 6 (2018), 2337–2361.
[9]
Timothy M. Chan and Konstantinos Tsakalidis. 2018. Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. In 34th International Symposium on Computational Geometry (SoCG 2018) (LIPIcs, Vol. 99), Bettina Speckmann and Csaba D. Tóth (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 25:1–25:15.
[10]
Bernard Chazelle. 1991. Computational Geometry for the Gourmet: Old Fare and New Dishes. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming. 686–696.
[11]
Bernard Chazelle. 1994. Computational geometry: A retrospective. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing. 75–94.
[12]
Bernard Chazelle and Leonidas J. Guibas. 1986. Fractional cascading: I. A data structuring technique. Algorithmica 1, 2 (1986), 133–162.
[13]
Siu-Wing Cheng and Ravi Janardan. 1992. New results on dynamic planar point location. SIAM J. Comput. 21, 5 (1992), 972–999.
[14]
Yi-Jen Chiang, Franco P. Preparata, and Roberto Tamassia. 1996. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM J. Comput. 25, 1 (1996), 207–233.
[15]
Yi-Jen Chiang and Roberto Tamassia. 1992. Dynamization of the trapezoid method for planar point location in monotone subdivisions. Int. J. Comput. Geometry Appl. 2, 3 (1992), 311–333.
[16]
Yi-Jen Chiang and Roberto Tamassia. 1992. Dynamic algorithms in computational geometry. Proc. IEEE 80, 9 (1992), 1412–1434.
[17]
Paul F. Dietz and Daniel Dominic Sleator. 1987. Two Algorithms for Maintaining Order in a List. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing. 365–372.
[18]
Otfried Fries. 1990. Suchen in dynamischen planaren Unterteilungen. Ph.D. Thesis. Universität des Saarlandes.
[19]
Yoav Giora and Haim Kaplan. 2009. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Transactions on Algorithms 5, 3 (2009), 28.
[20]
Mordecai J. Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich. 2018. Dynamic Trees with Almost-Optimal Access Cost. In 26th Annual European Symposium on Algorithms (ESA) (LIPIcs, Vol. 112). 38:1–38:14.
[21]
Michael T. Goodrich and Roberto Tamassia. 1998. Dynamic trees and dynamic point location. SIAM J. Comput. 28, 2 (1998), 612–636.
[22]
Leonidas J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts. 1977. A new representation for linear lists. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing. 49–60.
[23]
Kurt Mehlhorn and Stefan Näher. 1990. Dynamic fractional cascading. Algorithmica 5, 2 (1990), 215–241.
[24]
Christian Worm Mortensen. 2006. Fully dynamic orthogonal range reporting on RAM. SIAM J. Comput. 35, 6 (2006), 1494–1525.
[25]
J. Ian Munro and Yakov Nekrich. 2019. Dynamic Planar Point Location in External Memory. In 35th International Symposium on Computational Geometry (SoCG). 52:1–52:15.
[26]
Franco P. Preparata and Roberto Tamassia. 1989. Fully dynamic point location in a monotone subdivision. SIAM J. Comput. 18, 4 (1989), 811–830.
[27]
Neil Sarnak and Robert Endre Tarjan. 1986. Planar Point Location Using Persistent Search Trees. Communincations of the ACM 29, 7 (1986), 669–679.
[28]
Jack Snoeyink. 2004. Point location. In Handbook of Discrete and Computational Geometry (2nd ed.), Jacob E. Goodman and Joseph O'Rourke (Eds.). CRC Press LLC, Boca Raton, FL, Chapter 34, 767–787.
Index Terms
- Dynamic planar point location in optimal time
Recommendations
Towards an Optimal Method for Dynamic Planar Point Location
We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in $O(\log n(\log\log n)^2)$ time and updates ...
Dynamic Trees and Dynamic Point Location
This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision $\cal S$. The main approach is based on the maintenance of two interlaced spanning trees, one for $\cal S$ and one for the ...
New Techniques for Exact and Approximate Dynamic Closest-point
Let $S$ be a set of $n$ points in $\IR^{D}$. It is shown that a range tree can be used to find an $L_{\infty}$-nearest neighbor in $S$ of any query point, in $O((\log n)^{D-1} \log\log n)$ time. This data structure has size $O(n (\log n)^{D-1})$ ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2021
1797 pages
ISBN:9781450380539
DOI:10.1145/3406325
- General Chair:
- Samir Khuller,
- Program Chair:
- Virginia Vassilevska Williams
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 June 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
STOC '21
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 150Total Downloads
- Downloads (Last 12 months)29
- Downloads (Last 6 weeks)1
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
Cited By
View all- Chen JHuang QKanj IXia G(2024)Nearly Time-Optimal Kernelization Algorithms for the Line-Cover Problem with Big DataAlgorithmica10.1007/s00453-024-01231-686:8(2448-2478)Online publication date: 9-May-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in