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

article

The Higher-Order Voronoi Diagram of Line Segments

Authors:

Evanthia Papadopoulou,

Maksym ZavershynskyiAuthors Info & Claims

Algorithmica, Volume 74, Issue 1

Pages 415 - 439

https://doi.org/10.1007/s00453-014-9950-0

Published: 01 January 2016 Publication History

Abstract

The order-$$k$$k Voronoi diagram of line segments has properties surprisingly different from its counterpart for points. For example, a single order-$$k$$k Voronoi region may consist of $$\varOmega (n)$$Ω(n) disjoint faces. In this paper, we analyze the structural properties of this diagram and show that its combinatorial complexity is $$O(k(n-k))$$O(k(n-k)), for $$n$$n non-crossing line segments, despite the presence of disconnected regions. The same bound holds for $$n$$n intersecting line segments, for $$k\ge n/2$$k n/2. We also consider the order-$$k$$k Voronoi diagram of line segments that form a planar straight-line graph, and augment the definition of an order-$$k$$k diagram to cover sites that are not disjoint. On the algorithmic side, we extend the iterative approach to construct this diagram, handling complications caused by the presence of disconnected regions. All bounds are valid in the general $$L_p$$Lp metric, $$1\le p\le \infty $$1≤p≤ . For non-crossing segments in the $$L_\infty $$L and $$L_1$$L1 metrics, we show a tighter $$O((n-k)^2)$$O((n-k)2) bound for $$k>n/2$$k>n/2.

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]

Aggarwal, A., Guibas, L.J., Saxe, J.B., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4, 591---604 (1989)

Digital Library

[3]

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)

[4]

Aurenhammer, F., Drysdale, R.L.S., Krasser, H.: Farthest line segment Voronoi diagrams. Inf. Process. Lett. 100(6), 220---225 (2006)

Digital Library

[5]

Aurenhammer, F., Klein, K., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations, World Scientific, 1---337, ISBN 978-981-4447-63-8, pp. I-VIII (2013)

[6]

Bohler, C., Klein, R., Liu, C.-H., Papadopoulou, E., Cheilaris, P., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. In: Fomin, F.V., et al. (eds.) ICALP 2013. Lecture Notes in Computer Science, vol. 7965, pp. 208---219. Springer, Heidelberg (2013)

[7]

Bohler, C., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams. 25th International Symposium on Algorithms and Computation, ISAAC 2014. Lecture Notes in Computer Science, vol. 8889, (to appear)

[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]

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

Digital Library

[10]

Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., Na, H.-S.: Farthest-polygon Voronoi diagrams. Comput. Geom. 44(4), 234---247 (2011)

Digital Library

[11]

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

Digital Library

[12]

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

Digital Library

[13]

Edelsbrunner, H.: The complexity of higher-order Voronoi diagrams. In: Edelsbrunner, H.: Algorithms in Combinatorial Geometry, pp. 319---324. EATCS monographs on theoretical computer science. Springer, Nre York (1987)

[14]

Edelsbrunner, H., Maurer, H.A., Preparata, F.P., Rosenberg, A.L., Welzl, E., Wood, D.: Stabbing line segments. BIT 22(3), 274---281 (1982)

[15]

Kirkpatrick, D.G.: Efficient computation of continuous skeletons. FOCS: 18---27, 20th Annual Symposium on Foundations of Computer Science (1979)

Digital Library

[16]

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

Digital Library

[17]

Lee, D.T.: Two-dimensional Voronoi diagrams in the $$\text{ L }_{p}$$Lp-metric. J. ACM 27(4), 604---618 (1980)

Digital Library

[18]

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

[19]

Liu, C.-H., Papadopoulou, E., Lee, D.T.: The k-nearest-neighbor Voronoi diagram revisited. Algorithmica (2013).

[20]

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

[21]

Papadopoulou, E.: Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE Trans. CAD Integr. Circuits Syst. 30(5), 704---717 (2011)

[22]

Papadopoulou, E., Dey, S.K.: On the farthest line segment Voronoi diagram. Int. J. Comput. Geom. Appl. 23(6), 443---460 (2013)

[23]

Papadopoulou, E., Zavershynskyi, M.Z.: On higher order Voronoi diagrams of line segments. In: Chao, K.-M. et al. (eds.) ISAAC 2012, Lecture Notes in Computer Science, 7676, 177---186 (2012)

[24]

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

[25]

Rappaport, D.: Computing the furthest site Voronoi diagram for a set of discs (preliminary report). In: Dehne, F.K.H.A., et al. (eds.) WADS 1989. Lecture Notes in Computer Science, vol. 382, pp. 57---66. Springer, Heidelberg (1989)

[26]

Rosenberger, H.: Order-k Voronoi diagrams of sites with additive weights in the plane. Algorithmica 6(4), 490---521 (1991)

Digital Library

[27]

Seidel, R.: The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom. 19(1), 1---17 (1998)

[28]

Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)

[29]

Sharir, M.: The Clarkson---Shor technique revisited and extended. Comb. Probab. Comput. 12(2), 191---201 (2003)

Digital Library

[30]

Zavershynskyi, M., Papadopoulou, E.: A sweepline algorithm for higher order Voronoi diagrams. In: Proceedings of 10th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2013. IEEE-CS, pp. 16---22 (2013)

Cited By

Barequet GPapadopoulou ESuderland M(2024)Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher DimensionsDiscrete & Computational Geometry10.1007/s00454-023-00492-272:3(1304-1332)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00454-023-00492-2
Adhinugraha KRahayu WHara TTaniar D(2022)Measuring fault tolerance in IoT mesh networks using Voronoi diagramJournal of Network and Computer Applications10.1016/j.jnca.2021.103297199:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.jnca.2021.103297
Vass BTapolcai JBérczi-Kovács E(2021)Enumerating Maximal Shared Risk Link Groups of Circular Disk Failures Hitting k NodesIEEE/ACM Transactions on Networking10.1109/TNET.2021.307010029:4(1648-1661)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1109/TNET.2021.3070100
Show More Cited By

The Higher-Order Voronoi Diagram of Line Segments
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher Dimensions
Abstract
We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of ... $^{}$ $^{}$ $^{}$ $^{}$
A Metric for Line Segments

This correspondence presents a metric for describing line segments. This metric measures how well two line segments can be replaced by a single longer one. This depends for example on collinearity and nearness of the line segments. The metric is ...
The L_infinity (L_1) Farthest Line-Segment Voronoi Diagram
ISVD '12: Proceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering

We present structural properties of the farthest line-segment Voronoi diagram in the piecewise linear L_infinity and L_1 metrics, which are computationally simpler than the standard Euclidean distance and very well suited for VLSI applications. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 74, Issue 1

January 2016

557 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
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

Barequet GPapadopoulou ESuderland M(2024)Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher DimensionsDiscrete & Computational Geometry10.1007/s00454-023-00492-272:3(1304-1332)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00454-023-00492-2
Adhinugraha KRahayu WHara TTaniar D(2022)Measuring fault tolerance in IoT mesh networks using Voronoi diagramJournal of Network and Computer Applications10.1016/j.jnca.2021.103297199:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.jnca.2021.103297
Vass BTapolcai JBérczi-Kovács E(2021)Enumerating Maximal Shared Risk Link Groups of Circular Disk Failures Hitting k NodesIEEE/ACM Transactions on Networking10.1109/TNET.2021.307010029:4(1648-1661)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1109/TNET.2021.3070100
Barequet GDe MGoodrich M(2021)Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex PolygonsAlgorithmica10.1007/s00453-021-00824-983:7(2245-2272)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00453-021-00824-9
Bohler CKlein RLiu C(2019)An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi DiagramsAlgorithmica10.1007/s00453-018-00536-781:6(2317-2345)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00453-018-00536-7
Aguilar-Rivera A(2019)Path-Finding with a Full-Vectorized GPU Implementation of Evolutionary Algorithms in an Online Crowd Model Simulation FrameworkComputational Science – ICCS 201910.1007/978-3-030-22750-0_17(223-236)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22750-0_17
Junginger KMantas IPapadopoulou E(2019)On Selecting Leaves with Disjoint Neighborhoods in Embedded TreesAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-11509-8_16(189-200)Online publication date: 14-Feb-2019
https://dl.acm.org/doi/10.1007/978-3-030-11509-8_16
Barequet GDe MGoodrich M(2018)Computing Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex PolygonsComputing and Combinatorics10.1007/978-3-319-94776-1_12(130-142)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94776-1_12
Bohler CLiu CPapadopoulou EZavershynskyi M(2016)A randomized divide and conquer algorithm for higher-order abstract Voronoi diagramsComputational Geometry: Theory and Applications10.1016/j.comgeo.2016.08.00459:C(26-38)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.comgeo.2016.08.004

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents