Document Open Access Logo

Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon

Authors Pankaj K. Agarwal, Lars Arge, Frank Staals

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.4.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
Lars Arge
Frank Staals

Cite As Get BibTex

Pankaj K. Agarwal, Lars Arge, and Frank Staals. Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.4

Abstract

We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of point sites in a static simple polygon P. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q in P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(n log^3n log m + m) space, where n is the number of sites in S and m is the number of vertices in P. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.

Subject Classification

Keywords
  • data structure
  • simple polygon
  • geodesic distance
  • nearest neighbor searching
  • shallow cutting

Metrics

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

References

  1. Pankaj K. Agarwal and Jiří Matoušek. Dynamic Half-Space Range Reporting and its Applications. Algorithmica, 13(4):325-345, 1995. Google Scholar
  2. Pankaj Agarwal K., Lars Arge, and Frank Staals. Improved dynamic geodesic nearest neighbor searching in a simple polygon. CoRR, abs/1803.05765, 2018. URL: http://arxiv.org/abs/1803.05765.
  3. Lars Arge and Frank Staals. Dynamic geodesic nearest neighbor searching in a simple polygon. CoRR, abs/1707.02961, 2017. URL: http://arxiv.org/abs/1707.02961.
  4. Boris Aronov. On the Geodesic Voronoi Diagram of Point Sites in a Simple Polygon. Algorithmica, 4(1):109-140, 1989. Google Scholar
  5. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic voronoi diagram. Discrete & Computational Geometry, 9(3):217-255, Mar 1993. Google Scholar
  6. Jon Louis Bentley and James B Saxe. Decomposable searching problems I. Static-to-dynamic transformation. Journal of Algorithms, 1(4):301-358, 1980. Google Scholar
  7. Timothy M. Chan. Random Sampling, Halfspace Range Reporting, and Construction of (≤ k)-levels in Three Dimensions. SIAM Journal on Computing, 30(2):561-575, 2000. Google Scholar
  8. Timothy M. Chan. A Dynamic Data Structure for 3-D Convex Hulls and 2-D Nearest Neighbor Queries. Journal of the ACM, 57(3):16:1-16:15, 2010. Google Scholar
  9. Timothy M. Chan and Konstantinos Tsakalidis. Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings. In Proc. 31st International Symposium on Computational Geometry, volume 34 of Leibniz International Proceedings in Informatics, pages 719-732. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  10. Kenneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989. Google Scholar
  11. David Dobkin and Subhash Suri. Maintenance of Geometric Extrema. Journal of the ACM, 38(2):275-298, 1991. Google Scholar
  12. Herbert Edelsbrunner, Leo J. Guibas, and Jorge Stolfi. Optimal Point Location in a Monotone Subdivision. SIAM Journal on Computing, 15(2):317-340, 1986. Google Scholar
  13. Leonidas J. Guibas and John Hershberger. Optimal Shortest Path Queries in a Simple Polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. Google Scholar
  14. Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons. Algorithmica, 2(1):209-233, 1987. Google Scholar
  15. Sariel Har-Peled. Geometric Approximation Algorithms, volume 173. American mathematical society Boston, 2011. Google Scholar
  16. Sariel Har-Peled and Micha Sharir. Relative (p,ε)-approximations in Geometry. Discrete & Computational Geometry, 45(3):462-496, Apr 2011. Google Scholar
  17. John Hershberger. A new data structure for shortest path queries in a simple polygon. Information Processing Letters, 38(5):231-235, 1991. Google Scholar
  18. John Hershberger and Subhash Suri. An Optimal Algorithm for Euclidean Shortest Paths in the Plane. SIAM Journal on Computing, 28(6):2215-2256, 1999. Google Scholar
  19. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2017. Google Scholar
  20. Rolf Klein and Andrzej Lingas. Hamiltonian abstract Voronoi diagrams in linear time, pages 11-19. Springer Berlin Heidelberg, Berlin, Heidelberg, 1994. Google Scholar
  21. Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE Transactions on Computers, C-31(6):478-487, June 1982. Google Scholar
  22. Chih-Hung Liu and D. T. Lee. Higher-order geodesic voronoi diagrams in a polygonal domain with holes. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1633-1645, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.117.
  23. Jiří Matoušek. Reporting points in halfspaces. Computational Geometry Theory and Applications, 2(3):169-186, 1992. Google Scholar
  24. Eunjin Oh and Hee-Kap Ahn. Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon. In Proc. 33rd International Symposium on Computational Geometry, volume 77 of Leibniz International Proceedings in Informatics, pages 52:1-52:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  25. Evanthia Papadopoulou and Der-Tsai Lee. A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains. Algorithmica, 20(4):319-352, 1998. 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