Document Open Access Logo

Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Authors Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.75.pdf
  • Filesize: 0.72 MB
  • 17 pages

Document Identifiers

Author Details

Matias Korman
  • Department of Computer Science, Tufts University, Medford, MA, USA
André van Renssen
  • School of Computer Science, University of Sydney, Australia
Marcel Roeloffzen
  • Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands
Frank Staals
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands

Funding

  • Korman, Matias: M.K. was partially supported by MEXT KAKENHI No. 17K12635 and the NSF award CCF-1422311.
  • van Renssen, André: A.V.R. was supported by JST ERATO Grant Number JPMJER1201, Japan.
  • Roeloffzen, Marcel: M.R. was supported by JST ERATO Grant Number JPMJER1201, Japan and the Netherlands Organisation for Scientific Research (NWO) under project no. 628.011.005.
  • Staals, Frank: F.S. was supported by the Netherlands Organisation for Scientific Research under project no. 612.001.651.

Acknowledgements

We would like to thank Man-Kwun Chiu and Yago Diez for interesting discussions during the initial stage of this research.

Cite AsGet BibTex

Matias Korman, André van Renssen, Marcel Roeloffzen, and Frank Staals. Kinetic Geodesic Voronoi Diagrams in a Simple Polygon. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.75

Abstract

We study the geodesic Voronoi diagram of a set S of n linearly moving sites inside a static simple polygon P with m vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most O(m³), and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in O(log m) time, and our Voronoi center handles each event in O(log² m) time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • kinetic data structure
  • simple polygon
  • geodesic voronoi diagram

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal, Lars Arge, and Frank Staals. Improved dynamic geodesic nearest neighbor searching in a simple polgyon. In Proceedings of the 34th Annual Symposium on Computational Geometry, volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.4.
  2. Pankaj K. Agarwal, Haim Kaplan, Natan Rubin, and Micha Sharir. Kinetic voronoi diagrams and delaunay triangulations under polygonal distance functions. Discrete & Computational Geometry, 54(4):871-904, December 2015. URL: https://doi.org/10.1007/s00454-015-9729-3.
  3. Boris Aronov. On the Geodesic Voronoi Diagram of Point Sites in a Simple Polygon. Algorithmica, 4(1):109-140, 1989. Google Scholar
  4. Boris Aronov, Steven Fortune, and Gordon Wilfong. The furthest-site geodesic voronoi diagram. Discrete & Computational Geometry, 9(3):217-255, March 1993. Google Scholar
  5. Boris Aronov, Leonidas J. Guibas, Marek Teichmann, and Li Zhang. Visibility queries and maintenance in simple polygons. Discrete & Computational Geometry, 27(4):461-483, January 2002. URL: https://doi.org/10.1007/s00454-001-0089-9.
  6. Julien Basch, Leonidas J. Guibas, and John Hershberger. Data structures for mobile data. J. Algorithms, 31(1):1-28, 1999. URL: https://doi.org/10.1006/jagm.1998.0988.
  7. G. S. Brodal and R. Jacob. Dynamic planar convex hull. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 617-626, November 2002. URL: https://doi.org/10.1109/SFCS.2002.1181985.
  8. Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O'Rourke. The open problems project. URL: http://maven.smith.edu/~orourke/TOPP/.
  9. J. E. Goodman and J. O'Rourke. Handbook of Discrete and Computational Geometry. CRC Press series on discrete mathematics and its applications. Chapman & Hall/CRC, 2004. Google Scholar
  10. Leonidas 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, November 1987. URL: https://doi.org/10.1007/BF01840360.
  11. Leonidas J. Guibas, Joseph S. B. Mitchell, and Thomas Roos. Voronoi diagrams of moving points in the plane. In Graph-Theoretic Concepts in Computer Science, pages 113-125, Berlin, Heidelberg, 1992. Springer. Google Scholar
  12. Monika R. Henzinger, Valerie King, and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4):502-516, July 1999. URL: https://doi.org/10.1145/320211.320215.
  13. 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
  14. Menelaos I. Karavelas and Leonidas J. Guibas. Static and kinetic geometric spanners with applications. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pages 168-176, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. Google Scholar
  15. Matias Korman, André van Renssen, Marcel Roeloffzen, and Frank Staals. Kinetic geodesic voronoi diagrams in a simple polygon. CoRR, abs/2002.05910, 2018. URL: http://arxiv.org/abs/2002.05910.
  16. Chih-Hung Liu. A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.58.
  17. Anna Lubiw, Jack Snoeyink, and Hamideh Vosoughpour. Visibility graphs, dismantlability, and the cops and robbers game. Computational Geometry, 66:14-27, 2017. URL: https://doi.org/10.1016/j.comgeo.2017.07.001.
  18. J. S. B. Mitchell. Shortest paths among obstacles in the plane. In Proceedings of the 9th Annual ACM Symposium on Computational Geometry, pages 308-317, 1993. Google Scholar
  19. Joseph S. B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence, 3(1):83-105, March 1991. URL: https://doi.org/10.1007/BF01530888.
  20. Eunjin Oh. Optimal algorithm for geodesic nearest-point voronoi diagrams in simple polygons. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 391-409. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.25.
  21. Eunjin Oh and Hee-Kap Ahn. Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discrete & Computational Geometry, March 2019. URL: https://doi.org/10.1007/s00454-019-00063-4.
  22. Eunjin Oh, Jean-Lou De Carufel, and Hee-Kap Ahn. The 2-center problem in a simple polygon. In Algorithms and Computation, pages 307-317, Berlin, Heidelberg, 2015. Springer. Google Scholar
  23. 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
  24. Natan Rubin. On kinetic delaunay triangulations: A near-quadratic bound for unit speed motions. Journal of the ACM, 62(3):25:1-25:85, June 2015. URL: https://doi.org/10.1145/2746228.
  25. Micha Sharir and Pankaj K Agarwal. Davenport-Schinzel sequences and their geometric applications. Cambridge university press, 1995. Google Scholar
  26. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. URL: https://doi.org/10.1016/0022-0000(83)90006-5.
  27. Subhash Suri. A linear time algorithm with minimum link paths inside a simple polygon. Computer Vision, Graphics and Image Processing, 35(1):99-110, 1986. URL: https://doi.org/10.1016/0734-189X(86)90127-1.
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 Imprint Privacy Contact