Information about Randomized Algorithms for Higher-Order Voronoi Diagrams

One of many important generalizations of ordinary Voronoi diagrams is the higher-order Voronoi diagram. The order-k Voronoi diagram is the partitioning of the plane into regions, such that each point within a fixed region has the same k nearest sites. Many algorithms have been developed that construct the higher-order Voronoi diagram of point-sites. In this talk we will discuss randomized algorithms that can be used for a larger class of sites—specifically, polygonal objects and the abstract setting. We describe the algorithms in combinatorial rather than geometric terms, which makes it possible to construct higher-order Voronoi diagrams that have bisectors satisfying certain combinatorial properties.

Nearest Neighbor Voronoi Diagram The nearest neighbor Voronoi diagram is the partitioning of the plane into regions, such that all points within a region have the same closest site.

Higher Order Voronoi Diagram The order-k Voronoi diagram is the partitioning of the plane into regions, such that all points within an order-k region have the same k nearest sites. VR2 ({p, q}, S) p q [Bohler et al.’13, Lee’82, Papadopoulou&Zavershynskyi’12]

Abstract Voronoi Diagrams Deﬁned by bisecting system rather than concrete geometric sites or distance measures. D(p, q) J(p, q) D(q, p) [Bohler et al.’13, Klein et al.’09, Klein et al.’93]

Abstract Voronoi Diagrams First-order Voronoi region: VR1 ({p}, S) = D(p, q) q∈S,q=p For each S ⊆ S A1) VR1 (p, S ) is pathwise connected R2 belongs to some VR1 (p, S ) A2) Each point in A3) VR1 (p, S ) is not empty A4) J(p, q) is unbounded Jordan-curve A5) J(p, q) and J(s, t) have ﬁnitely many intersection points that are transversal. [Bohler et al.’13, Klein et al.’09, Klein et al.’93]

Abstract Voronoi Diagrams Order-k Voronoi region: VRk (H, S) = D(p, q) p∈H,q∈SH • • • Points in convex distance metrics, Karlsruhe metric Disjoint line segments in Lp Disjoint convex polygons in Lp Structural complexity is ≤ 2k(n − k) [Bohler et al.’13, Klein et al.’09, Klein et al.’93]

Construction Algorithms Construction Time 2 2 O n + b log n 1+ O n k 2 O nk log n 2 O nk + n log n 3 O nk + n log n 3 O n log n + nk log n O (n log n + nk log n) c log∗ k O n log n + nk2 Reference Chazelle&Edelsbrunner’87 Clarkson’87 Aurenhammer’90 Mulmuley’91 Boissonnat et al.’93 Agarwal et al.’98 Chan’98 Ramos’99

Our Results We Present 3 Algorithms for Abstract Diagrams 1. Randomized Divide-n-Conquer Algorithm • Expected time complexity O(kn1+ε ) for any constant ε > 0 • Based on Clarkson-Shor technique and Clarkson’s algorithm for points. • Uses two other algorithms for subroutines. 2. Traversal-based Algorithm 3. Iterative Algorithm

Construction Algorithms Randomized divide-n-conquer algorithm Traversal-based algorithm 2 α(n) O(n 2 log n) good for large k es us us es O(kn1+ε ) Iterative algorithm O(k 2 n log n) good for small k

Additional Axiom Additional Axiom: A6) Each bisector has constant number of points of vertical tangencies.

Divide-n-Conquer Algorithm

Vertical Decomposition Vertical decomposition of Vk (S) : 1. Consider Vk (S) ∪ Vk+1 (S) 2. Shoot vertical rays from each vertex and vertical tangent point. Vk (S)

Vertical Decomposition Vertical decomposition of Vk (S) : 1. Consider Vk (S) ∪ Vk+1 (S) 2. Shoot vertical rays from each vertex and vertical tangent point. Vk (S) ∪ Vk+1 (S)

Vertical Decomposition Vertical decomposition of Vk (S) : 1. Consider Vk (S) ∪ Vk+1 (S) 2. Shoot vertical rays from each vertex and vertical tangent point. Vk (S) ∪ Vk+1 (S)

Random Sampling Draw random sample R such that it is a good estimator of S . Trapezoid is deﬁned by at most d elements of R e.g.: s2 s1 p s3 d=5 p - dominator s4 [Clarkson’87]

Random Sampling Site s strongly conﬂicts with if ⊂ D(s, p) D(s, p) s2 s1 p s4 s3 d=5 p - dominator

Random Sampling Site s weakly conﬂicts with if ∩ D(s, p) = ∅ D(s, p) s2 s1 p s4 s3 d=5 p - dominator

Lemma 1 Lemma 1 For a random sample R , with probability at least 1/2 1) number of strong conﬂicts with S is ≥ |S|/(r − 5) 2) number of weak conﬂicts with S is ≤ α|S| for each trapezoid in vert. decomposition of Vβ (R) Allows to efﬁciently “bracket” the space! [Clarkson’87] r = |R|, α = O(log r), β = O(log r/ log log r)

Lemma 2 - set of sites S Vk (S) - order-k diagram v - vertex v [Clarkson’87] r = |R|, α = O(log r), β = O(log r/ log log r)

Lemma 2 - set of sites S Vk (S) - order-k diagram v - vertex v [Clarkson’87] R ⊂ S - random sample where each in vert. decomp. of Vβ (R) has ≥ k strong conﬂicts r = |R|, α = O(log r), β = O(log r/ log log r)

Lemma 2 - set of sites S Vk (S) - order-k diagram v - vertex R ⊂ S - random sample v Allows to perform divide-n-conquer! [Clarkson’87] where each in vert. decomp. of Vβ (R) has ≥ k strong conﬂicts S ⊂ S - sites in weak conﬂict Vk (S ) then v is vertex of r = |R|, α = O(log r), β = O(log r/ log log r)

Divide-n-Conquer Algorithm Construction of Vk (S) can be reduced to ﬁnding all the vertices of Vk (S). [Clarkson’87]

Divide-n-Conquer Algorithm If |S| ≤ k(r − 5) then use traversal-based algorithm. Else choose “good” random sample R . • Construct Vβ (R) and the decomposition, using iterative algorithm. • For each trapezoid in the decomposition recursively compute vertices in Vk (S ) . [Clarkson’87] where S ⊂ S - the sites in weak conﬂict with .

Traversal-Based Algorithm

Inﬂuence Region Inﬂuence region of site s - union of all order-k Voronoi regions induced by the site s. Vk (S) inﬂuence region of site s [Papadopoulou&Zavershynskyi, Bohler et al.’13]

Traversal-Based Algorithm We can construct inﬂuence region of site s O(n2α(n) log n) , using Har-Peled’s random in time walk method. Vk (S) inﬂuence region of site s [Har-Peled’00]

Traversal-Based Algorithm Union of all inﬂuence regions is the order-k Voronoi diagram. O(n2 2α(n) log n) Total running time: [Har-Peled’00, Chazelle&Edelsbrunner’87]

Iterative Algorithm

Iterative Algorithm Order-k Voronoi diagram can be computed from the order-(k-1) Voronoi diagram in O(k(n − k) log n) expected time. Total running time: O(k2 n log n) [Bohler et al.’13, Lee’82, Papadopoulou&Zavershynskyi, Klein et al.’93]

SUMMARY We have developed 3 randomized algorithms for abstract higher-order Voronoi diagrams. 1.Divide-n-conquer algorithm with O(kn1+ε ) time complexity. O(n2 2α(n) log n) 2.Traversal-based algorithm with time complexity. Good for large orders. 3.Iterative algorithm with O(k2 n log n) time complexity. Good for small orders.

Thank you!

References 1) C. Bohler, P. Cheilaris, R. Klein, C.-H. Liu, E. Papadopoulou, and M. Zavershynskyi. On the complexity of higher order abstract Voronoi diagrams. 40th International Colloquium on Automata, Languages and Programming (ICALP’13), pp. 208–219, 2013. 2) K. L. Clarkson. New applications of random sampling in computational geometry. Discrete and Computational Geometry 2 (1), pp. 195–222, 1987. 3) S. Har-Peled. Taking a walk in a planar arrangment. SIAM Journal on Computing 30(4), pp. 1341-1367, 2000. 4) D. T. Lee. On k Nearest Neighbor Voronoi Diagrams in the Plane. IEEE Trans. Computers 31(6), pp. 478-487, 1982. 5) E. Papadopoulou and M. Zavershynskyi. On Higher Order Voronoi Diagrams of Line Segments. 23rd International Symposium on Algorithms and Computation (ISAAC ’12), LNCS 7676, pp. 177–186, 2012. 6) R. Klein, E. Langetepe, and Z. Nilforoushan. Abstract Voronoi Diagrams Revisited. Computational Geometry: Theory and Applications 42(9), pp. 885-902, 2009. 7) R. Klein, K. Mehlhorn, and St. Meiser. Randomized Incremental Construction of Abstract Voronoi Diagrams. Computational Geometry: Theory and Applications 3(1), pp. 157–184 1993. 8) B. Chazelle and H. Edelsbrunner. An improved algorithm for constructing kth-order Voronoi Diagram. IEEE Transactions on Computers 36(11), pp. 1349–1454, 1987.

Misc projection

Misc planes that correspond to extremal positions of β-sets

Misc planes that correspond to extremal positions of β-sets

Misc normals planes that correspond to extremal positions of β-sets

Misc normals planes that correspond to extremal positions of β-sets

Misc normals triangulation of the cone planes that correspond to extremal positions of β-sets

Misc normals points that belong to the union of the halfplanes - analog of weak conﬂict points that belong to the intersection of the halfplanes - analog of strong conﬂict

Abstract. 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 ...

Read more

A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams Cecilia Bohler 1, Chih-Hung Liu , Evanthia Papadopoulou2(B), and ...

Read more

Keywords: Order-k Voronoi Diagrams, Abstract Voronoi Diagrams, Randomized Geometric Algorithms : Seminar: 32nd International Symposium on Computational ...

Read more

... Pradeep Teregowda): We give simple randomized incremental algorithms ... Arrangements and Higher Order Voronoi ... Higher Order Voronoi Diagrams} ...

Read more

... O. SchwarzkopL A Simple Online Randomized Incremental Algorithm for Computing Higher Order Voronoi Diagrams. ... Randomized Incremental Algorithms in a ...

Read more

CONSTRUCTING LEVELS IN ARRANGEMENTS AND HIGHER ORDER VORONOI ... We give simple randomized incremental algorithms for ... random sampling, Voronoi diagrams

Read more

Higher Order City Voronoi Diagrams Andreas Gemsa1, D. T. Lee2;3, Chih-Hung Liu1; ... Additionally, there are several randomized algorithms [2,13] ...

Read more

A simple on-line randomized incremental algorithms for computing higher order voronoi diagrams (1991)

Read more

Constructing levels in arrangements and higher order Voronoi diagrams. Full Text: PDF: Authors: Pankaj K. Agarwal: Department of Computer ...

Read more

## Add a comment