# Randomized Algorithms for Higher-Order Voronoi Diagrams

50 %
50 %
Information about Randomized Algorithms for Higher-Order Voronoi Diagrams
Technology

Published on February 27, 2014

Author: maksym_zavershynskyi

Source: slideshare.net

## Description

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.

Randomized Algorithms for Higher-Order Voronoi Diagrams Maksym Zavershynskyi1 Cecilia joint work with Bohler2, Chih-Hung Liu2 and Evanthia Papadopoulou1 1University of Lugano, Faculty of Informatics, CH-6904 Lugano, Switzerland 2University of Bonn, Institute of Computer Science I, D-53113 Bonn, Germany This work was supported by the European Science Foundation (ESF) in the EUROCORES collaborative research project EuroGIGA/VORONOI, SNF 20GG21-134355. The work of the 1rd and 4rth author was supported in part by the Swiss National Science Foundation grant 200020-149658.

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

 User name: Comment:

## Related presentations

#### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

#### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

#### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

#### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

#### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

#### All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

## Related pages

### A randomized divide and conquer algorithm for higher-order ...

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

### A Randomized Divide and Conquer Algorithm for Higher-Order ...

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

### An Efficient Randomized Algorithm for Higher-Order ...

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

### Constructing Levels in Arrangements and Higher Order ...

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

### A simple on-line randomized incremental algorithm for ...

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

### Constructing Levels in Arrangements and Higher Order ...

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

### Higher Order City Voronoi Diagrams - arxiv.org

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