advertisement

Randomized Algorithms for Higher-Order Voronoi Diagrams

50 %
50 %
advertisement
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.
advertisement

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 Defined 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 finitely 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 defined 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 conflicts with ￿ if ￿ ⊂ D(s, p) D(s, p) s2 s1 p ￿ s4 s3 d=5 p - dominator

Random Sampling Site s weakly conflicts 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 conflicts with S is ≥ |S|/(r − 5) 2) number of weak conflicts with S is ≤ α|S| for each trapezoid ￿ in vert. decomposition of Vβ (R) Allows to efficiently “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 conflicts 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 conflicts S ⊂ S - sites in weak conflict 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 finding 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 conflict with ￿ .

Traversal-Based Algorithm

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

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

Traversal-Based Algorithm Union of all influence 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 conflict points that belong to the intersection of the halfplanes - analog of strong conflict

Add a comment

Related presentations

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

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

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

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

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

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

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

An Efficient Randomized Algorithm for Higher-Order ...

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

Constructing Levels in Arrangements and Higher Order ...

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

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

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
Read more

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] ...
Read more

A simple on-line randomized incremental algorithms for ...

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

Constructing levels in arrangements and higher order ...

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