More Web Proxy on the site http://driver.im/

article

An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams

Authors:

Cecilia Bohler,

Chih-Hung LiuAuthors Info & Claims

Algorithmica, Volume 81, Issue 6

Pages 2317 - 2345

https://doi.org/10.1007/s00453-018-00536-7

Published: 01 June 2019 Publication History

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)$$O(k(n-k)log2n+nlog3n) steps, where $$O(k(n-k))$$O(k(n-k)) is the number of faces in the worst case. This result applies to disjoint line segments in the $$L_p$$Lp norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, a running time with a polylog factor to the number of faces was only achieved for point sites in the $$L_1$$L1 or Euclidean metric before.

References

[1]

Agarwal, P.K., de Berg, M., Matousek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654---667 (1998)

Digital Library

[2]

Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Int. J. Comput. Geom. Appl. 2(4), 363---381 (1992)

[3]

Bohler, C., Cheilaris, P., Klein, R., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. Comput. Geom. 48(8), 539---551 (2015)

Digital Library

[4]

Bohler, C., Klein, R.: Abstract Voronoi diagrams with disconnected regions. Int. J. Comput. Geom. Appl. 24(4), 347---372 (2014)

[5]

Bohler, C., Klein, R., Liu, C.-H.: An efficient randomized algorithm for higher-order abstract Voronoi diagrams. In: Proceeding of the 32nd International Symposium on Computational Geometry (SoCG 2016), pp. 21:1---21:15 (2016)

[6]

Bohler, C., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams. Comput. Geom. 59, 26---38 (2016)

Digital Library

[7]

Boissonnat, J.-D., Devillers, O., Teillaud, M.: A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmica 9(4), 329---356 (1993)

[8]

Chan, T.M.: Random sampling, halfspace range reporting, and construction of ($$\le k$$≤k)-levels in three dimensions. SIAM J. Comput. 30(2), 561---575 (2000)

Digital Library

[9]

Chan, T.M., Tsakalidis, K.: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete Comput. Geom. 56(4), 866---881 (2016)

Digital Library

[10]

Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485---524 (1991)

Digital Library

[11]

Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing $$k$$k-th-order Voronoi diagrams. IEEE Trans. Comput. 36(11), 1349---1354 (1987)

Digital Library

[12]

Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M., Snoeyink, J.: Computing a face in an arrangement of line segments and related problems. SIAM J. Comput. 22(6), 1286---1302 (1993)

Digital Library

[13]

Chew, L.P., Scot Drysdale, R.L.: Voronoi diagrams based on convex distance functions. In: Proceedings of the First Annual Symposium on Computational Geometry, (SoCG 1985), pp. 235---244 (1985)

Digital Library

[14]

Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195---222 (1987)

Digital Library

[15]

Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387---421 (1989)

Digital Library

[16]

Gemsa, A., Lee, D.T., Liu, C.-H., Wagner, D.: Higher order city Voronoi diagrams. In: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 59---70 (2012)

Digital Library

[17]

Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127---151 (1987)

Digital Library

[18]

Klein, R.: Voronoi diagrams in the Moscow metric (extended abstract). In: Proceedings of the 14th International Workshop of Graph-Theoretic Concepts in Computer Science (WG88), pp. 434---441 (1988)

Digital Library

[19]

Klein, R.: Concrete and Abstract Voronoi Diagrams. Volume 400 of Lecture Notes in Computer Science. Springer, Berlin (1989)

[20]

Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comput. Geom. 42(9), 885---902 (2009)

Digital Library

[21]

Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract Voronoi diagrams. Comput. Geom. 3, 157---184 (1993)

Digital Library

[22]

Lee, D.T.: On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31(6), 478---487 (1982)

Digital Library

[23]

Liu, C.-H., Lee, D.T.: Higher-order geodesic Voronoi diagrams in a polygonal domain with holes. In: Proceedings of the Twenty-Fourth Annual Symposium on Discrete Algorithms (SODA), pp. 1633---1645 (2013)

Digital Library

[24]

Mehlhorn, K., Meiser, S., Rasch, R.: Furthest site abstract Voronoi diagrams. Int. J. Comput. Geom. Appl. 11(6), 583---616 (2001)

[25]

Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)

[26]

Papadopoulou, E.: The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica 40(2), 63---82 (2004)

Digital Library

[27]

Papadopoulou, E., Zavershynskyi, M.: On higher order Voronoi diagrams of line segments. Algorithmica 74(1), 415---439 (2016)

Digital Library

[28]

Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG), pp. 390---399 (1999)

Digital Library

[29]

Tarjan, R.E., Van Wyk, C.J.: An $$O(n \log \log n)$$O(nloglogn)-time algorithm for triangulating a simple polygon. SIAM J. Comput. 17(1), 143---178 (1988)

Digital Library

Cited By

Claverol Mde las Heras Parrilla AHuemer CMartínez-Moraian A(2024)The edge labeling of higher order Voronoi diagramsJournal of Global Optimization10.1007/s10898-024-01386-090:2(515-549)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10898-024-01386-0
Junginger KPapadopoulou E(2023)Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related ProblemsDiscrete & Computational Geometry10.1007/s00454-022-00463-z69:4(1040-1078)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1007/s00454-022-00463-z

Index Terms

An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Index terms have been assigned to the content through auto-classification.

Recommendations

Abstract Voronoi diagrams revisited

Abstract Voronoi diagrams [R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, vol. 400, Springer-Verlag, 1987] were designed as a unifying concept that should include as many concrete types of diagrams as possible. To ...
On the complexity of higher order abstract voronoi diagrams
ICALP'13: Proceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part I

Abstract Voronoi diagrams [15,16] are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and circles. They serve as a unifying concept. Once the bisector system of any concrete type of ...
A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams

Given a set of n sites in the plane, their order-k Voronoi diagram partitions the plane into regions such that all points within one region have the same k nearest sites. The order-k abstract Voronoi diagram offers a unifying framework that represents a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 81, Issue 6

Jun 2019

530 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Claverol Mde las Heras Parrilla AHuemer CMartínez-Moraian A(2024)The edge labeling of higher order Voronoi diagramsJournal of Global Optimization10.1007/s10898-024-01386-090:2(515-549)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10898-024-01386-0
Junginger KPapadopoulou E(2023)Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related ProblemsDiscrete & Computational Geometry10.1007/s00454-022-00463-z69:4(1040-1078)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1007/s00454-022-00463-z

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents