Document Open Access Logo

An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams

Authors Cecilia Bohler, Rolf Klein, Chih-Hung Liu

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.21.pdf
  • Filesize: 0.67 MB
  • 15 pages

Document Identifiers

Author Details

Cecilia Bohler
Rolf Klein
Chih-Hung Liu

Cite As Get BibTex

Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.21

Abstract

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O(k(n-k)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before.

Subject Classification

Keywords
  • Order-k Voronoi Diagrams
  • Abstract Voronoi Diagrams
  • Randomized Geometric Algorithms

Metrics

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

References

  1. Pankaj K. Agarwal, Mark de Berg, Jirí Matousek, and Otfried Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput., 27(3):654-667, 1998. Google Scholar
  2. Franz Aurenhammer and Otfried Schwarzkopf. A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. In Proceedings of the Seventh Annual Symposium on Computational Geometry (SoCG), pages 142-151, 1991. Google Scholar
  3. Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, and Maksym Zavershynskyi. On the complexity of higher order abstract Voronoi diagrams. Computational Geometry, 48(8):539-551, 2015. Google Scholar
  4. Cecilia Bohler and Rolf Klein. Abstract Voronoi diagrams with disconnected regions. Int. J. Comput. Geometry Appl., 24(4):347-372, 2014. Google Scholar
  5. Cecilia Bohler, Chih-Hung Liu, Evanthia Papadopoulou, and Maksym Zavershynskyi. A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams. In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), pages 27-37, 2014. Google Scholar
  6. Jean-Daniel Boissonnat, Olivier Devillers, and Monique Teillaud. A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmica, 9(4):329-356, 1993. Google Scholar
  7. Timothy M. Chan. Random sampling, halfspace range reporting, and construction of (less= k)-levels in three dimensions. SIAM J. Comput., 30(2):561-575, 2000. Google Scholar
  8. Timothy M. Chan and Konstantinos Tsakalidis. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. In Proceeding of the 31st International Symposium on Computational Geometry (SoCG), pages 719-732, 2015. Google Scholar
  9. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6:485-524, 1991. Google Scholar
  10. Bernard Chazelle and Herbert Edelsbrunner. An improved algorithm for constructing k th-order Voronoi diagrams. IEEE Trans. Computers, 36(11):1349-1354, 1987. Google Scholar
  11. Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Jack Snoeyink. Computing a face in an arrangement of line segments and related problems. SIAM J. Comput., 22(6):1286-1302, 1993. Google Scholar
  12. Kenneth L. Clarkson. New applications of random sampling in computational geometry. Discrete & Computational Geometry, 2:195-222, 1987. Google Scholar
  13. Kenneth L. Clarkson and Peter W. Shor. Application of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989. Google Scholar
  14. Andreas Gemsa, D. T. Lee, Chih-Hung Liu, and Dorothea Wagner. Higher order city Voronoi diagrams. In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 59-70, 2012. Google Scholar
  15. David Haussler and Emo Welzl. epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. Google Scholar
  16. Rolf Klein. Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes in Computer Science. Springer, 1989. Google Scholar
  17. Rolf Klein, Elmar Langetepe, and Zahra Nilforoushan. Abstract Voronoi diagrams revisited. Comput. Geom., 42(9):885-902, 2009. Google Scholar
  18. Rolf Klein, Kurt Mehlhorn, and Stefan Meiser. Randomized incremental construction of abstract Voronoi diagrams. Comput. Geom., 3:157-184, 1993. Google Scholar
  19. D. T. Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Computers, 31(6):478-487, 1982. Google Scholar
  20. Chih-Hung Liu and D. T. Lee. Higher-order geodesic Voronoi diagrams in a polygonal domain with holes. In Proceedings of the Twenty-Fourth Annual Symposium on Discrete Algorithms (SODA), pages 1633-1645, 2013. Google Scholar
  21. Kurt Mehlhorn, Stefan Meiser, and Ronald Rasch. Furthest site abstract Voronoi diagrams. Int. J. Comput. Geometry Appl., 11(6):583-616, 2001. Google Scholar
  22. Ketan Mulmuley. Computational geometry - an introduction through randomized algorithms. Prentice Hall, 1994. Google Scholar
  23. Evanthia Papadopoulou and Marksim Zavershynskyi. On higher order Voronoi diagrams of line segments. Algorithmica, 2014. Published on-line. Google Scholar
  24. Edgar A. Ramos. On range reporting, ray shooting and k-level construction. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG), pages 390-399, 1999. Google Scholar
  25. Robert Endre Tarjan and Christopher J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon. SIAM J. Comput., 17(1):143-178, 1988. 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