Report

On Farthest, Higher-order, and Hausdorff Voronoi diagrams Overview Evanthia Papadopoulou Università della Svizzera italiana -- USI (University of Lugano) 1 Project Overview Order-k Voronoi diagrams of line segments Farthest (k=n-1) Voronoi diagrams of line segments In 2,3,d dimensions Hausdorff Voronoi diagram – min-max type Completely ignored in CG literature (surprisingly) Application: line segments forming polygons and planar graphs Captures defects destroying shapes / clusters of points L simplifications (motivated by VLSI applications) LVoronoi diagram of line segments in CGAL 2 Talk Overview Summarize our work on Order-k line-segment Voronoi diagram Farthest line-segment Voronoi diagram in 2D, 3D L software Elena Khramtcova will talk on the Hausdorff Voronoi diagram Maksym Zavershyskyi on recent algorithms for order-k diagrams 3 Order-k Voronoi diagram Given a set of sites, the order-k Voronoi diagram is a partitioning of the plane into regions such that all points within one region have the same k nearest sites. Order-1 Order-2 4 Order-k line-segment Voronoi diagram Line segments: surprisingly different properties from points Disconnected regions A single order-k region may disconnect into (n) disjoint faces 5 Order-k line-segment Voronoi diagram Line segments: surprisingly different properties from points Disconnected regions A single order-k region may disconnect into (n) disjoint faces Ω(n-k) bounded faces. For 1<k<n/2, Ω(n-k) = Ω(n) 6 Order-k line-segment Voronoi diagram Line segments: surprisingly different properties from points Disconnected regions A single order-k region may disconnect into (n) disjoint faces k n-k Ω(k) unbounded faces. For n/2<k n, Ω(k) = Ω(n) 7 Overall structural complexity: O(k(n-k)) Same as points, where Voronoi regions are connected Disjoint line segments Intersecting line segments, for k>n/2 For k>n/2, complexity is independent of #intersections O(k(n-k) +I) for k< n/2; I: # intersections Line segments forming a PSLG Important for applications -- polygonal objects [joint work with M. Zavershynskyi] 8 Order-k VD of PSLG Planar straight-line graph (PSLG). Non-disjoint sites Inherently degenerate Areas where multiple segments are equidistant -- their number is independent of k Standard definition assumes |H|=k -- not sufficient Vk (H , S ) x | s H , t S \ H , d x, s d x, t Must allow > k elements in an order-k set Challenge: Augment definition of order-k region 9 Order-k disk Dk(x) Order-k disk Dk(x): Disk of minimum radius that intersects at least k line-segments (centered at x) Proper Dpk(x): touches exactly one elementary site p The set of segments intersected by such a disk is an order-k subset p k = 5,6,7 10 Order-k subset Order-k subset H 1. |H|=k (Type-1) 2. |H| > k (Type-2) and there is a proper order-k disk Dpk(x) that intersects H p -- representative of H H p H is order-k subset for k = 5,6,7 Order-k Voronoi region of non-disjoint sites Define in terms of order-k subsets -- not cardinality-k H Type 1 – standard definition of a Voronoi region Vk (H, S) = { x | "s Î H, "t Î S \ H, d ( x, s) < d ( x, t )} Vk (H, S) = { x | Sk (x) = H } type 1 H = Hp Type 2 (representative p) Sk(x) the set of line segments intersected by Dk(x) 12 Type-2 Voronoi regions Non-standard configurations – pose no problems Degree 4, 5, 6 Voronoi vertices Type-2 regions expand (as k increases) until they become Type-1 k=1 k=2 k=3,..,6 k=7 Algorithms -- order-k VD of line segments Standard iterative construction (all cases) O(k2nlogn) Plane sweep (all cases) [P. & Zavershyskyi 2013] Maintain the level-k in an arrangement of segment wave-curves Maintain the level <= k Time O(k2nlogn) Randomized techniques (disjoint sites) appropriate for larger k (Maksym’s talk) 14 Order-k AVDs Generalized complexity results to order-k Abstract Voronoi Diagrams Represent a much wider class of order-k diagrams of disjoint sites Disjoint line segments: a concrete instance of order-k AVDs (PSLG or intersecting line segments not such an instance) [Joint work with Bonn] [Bohler, Cheilaris, Klein, Liu, Papadopoulou, Zavershynskyi, ICALP 2013] 15 Gaussian Map for VD Structure that encodes the unbounded regions of a VD Maps VD at infinity on the sphere of directions Signature of VD at infinity Useful for VDs that consist of unbounded regions Example: the farthest line-segment Voronoi diagram 16 Farthest line-segment Voronoi diagram [Aurenhammer, Drysdale, Krasser, IPL 06] Properties surprisingly different from points Not related to convex hull Disconnected Voronoi regions A single segment may have (n) disconnected faces! Tree structure, size: O(n) Constructed in O(nlog n) time 17 Farthest line-segment Voronoi diagram Faces of the FVD still characterized by the farthest-hull Convex-hull-like structure Closed polygonal curve represented by its Gaussian map (Gmap) [P. & Dey 2012] 18 Farthest hull -- Supporting line A segment s (or segment endpoint p) has a nonempty farthest Voronoi region if it admits a supporting line l Line l is supporting if it defines an open half-plane H(l) that intersects all segments except s H(l) H(l) l s s Hull vertex Hull segment 19 Supporting segment Two points p1,p2 define a supporting segment if the line l through p1,p2 defines an open half-plane H(l) that intersects all segments except segments incident to p1,p2. p1 p2 H(l) Unbounded bisector in FVD 20 Farthest line-segment hull (f-hull) The sequence of hull segments and supporting segments ordered in the angular order of their unit normals yields the farthest hull and its Gaussian map on the unit circle. The farthest hull is a closed polygonal curve. 21 Gaussian map: simple circular list The f-hull may look complicated but its Gmap is a simple circular list (like a convex hull) a vertex may appear multiple times on Gmap (multiple arcs) a segment may appear twice (two opposite unit vectors) 22 Connection with point-line duality A point can be mapped into a line (in dual space) and vice versa A line segment can be mapped into a wedge below (or above) two intersecting lines [Aurenhammer, Drysdale, Krasser, IPL 06] lines passing above AB 23 Faces FVD = Upper envelope of wedges Faces of FVD, unbounded in direction 0 to = upper envelope of wedges [Aurenhammer, Drysdale, Krasser, IPL 06] Upper (lower) Gmap = Upper (lower) envelope of wedges Gmap arc = envelope edge Gmap unit vector = envelope vertex 24 Computing the FVD Compute Gmap, O(nlogh) time h: # Voronoi faces Adapt convex hull techniques D&C, quick hull, incremental, Chan’s output-sensitive, Jarvis march (no Graham scan) [P. & Dey 12] Compute FVD from circular list of unbounded bisectors, O(h log h) time [Aurenhammer, Drysdale, Krasser, IPL 06] Conjecture: FVD can also be computed in O(h) time, given the Gmap 25 FVD -- line segments (and lines) in 3D FVD: cell complex – all regions unbounded Voronoi skeleton is connected The region of one segment may induce Θ(n2) unbounded features Total number of unbounded features in FVD is Θ(n2) FVD of lines in 3D, Θ(n2) unbounded features As NN-VD of lines in 3D, diagram complexity open, O(n3+ε) [Recent joint work with Gill Barequet] 26 FVD -- line segments (and lines) in d-D Results seem to generalize in d-dimensions by induction The total number of unbounded features of FVD is Θ(nd-1) Tool used: the Gaussian Map, Duality [Recent joint work with Gill Barequet] 27 Supporting plane A plane P is supporting P passes through 3 endpoints of (three or two) segments of ; One closed halfspace +, fully contains these segments The other open halfspace, −, intersects all other segments 3-leg tricycle 29 Gaussian map – line segments Planar map on the sphere of directions as implied by the unbounded features of FVD Vertices: Correspond to supporting planes (either 3-leg or tricycle) Edges: Correspond to rotations of supporting planes Two types of rotations Type I: rotations about a segment Not part of FVD Connect tricycle vertices Type II: about the line defined by two endpoints of different segments (bisectors) 30 Vertices / Edges 3-leg vertices reveal unbounded trisectors in the FVD Type II edges correspond to unbounded bisectors of FVD Tricycle vertices reveal hull segments (like in 2D) They are breakpoints of Type II edges (bisectors) Type I arcs are not part of the regular Gmap Can be included in an augmented Gmap Reveal hull segments (like in 2D) Represent two parallel planes separating the open portion and endpoints (in an augmented FVD) 31 Faces of Gaussian map Segment faces Correspond to Voronoi cells of entire segments Contain a Type I rotation arc One segment can have Θ(n) faces around its Type-I great circle Endpoint faces Correspond to Voronoi cells of segment endpoints Bounded by Type-II edges only One segment endpoint can induce Θ(n2) vertices on the Gmap 32 One endpoint may induce Θ(n2) vertices Put n-1 long segments connecting almost antipodal points on a sphere and 1 short segment near the center of the sphere Any pair of long segments together with the short segment define a distinct supporting plane. The region of the short segment induces Θ(n2) vertices on Gmap 2D example of [Aurenhammer, Drysdale, Krasser, IPL 06] 34 Gaussian map segments in 3-d (lower bound) V 36 Complexity of Gmap is Θ(n2) The worst case complexity of the Gmap is Θ(n2) Lower bound n line segments connecting antipodal points on a sphere n great circles of supporting planes. Intersection points are all features of the Gmap. Upper bound Based on duality transformation of segments into 3D wedges Upper Gmap = upper envelope of 3D wedges (roofs) Use the fact that the upper envelope of 2D wedges is linear [Edelsbrunner, Maurer, Preparata, Rosenberg, Welzl, Wood, BIT 82] 37 Complexity of Gmap is O(n2) Complexity of the upper envelope of 3D wedges (roofs) Count the complexity of envelopes on each slope. There are O(n) slopes On a given slope we essentially have the envelope of 2D wedges (almost), which is O(n) On slope of wedge w: Intersection with another wedge is a 2D wedge (full or trimmed by apex a) Another wedge w’ may partially or fully contain a (w’ takes over w). But then features are counted on the slope of w’ 38 Algorithms Compute the Gmap: D&C O(n2logn) time O(n2) seems possible Compute FVD, given the Gmap: O(k log n) time, k: complexity of FVD Start with unbounded bisectors as obtained by Gmap Compute vertices in decreasing order of weight (radius) Property: Voronoi skeleton forms a DAG using the order of vertices in increasing weight (radius of implied sphere) 39 Gmap of lines in 3D – simpler one type of faces V 40 L segment Voronoi diagrams Interested in the L metric because of simplicity Straight-line skeleton (no parabolic parts) -- valuable proximity Voronoi vertices on rational coordinates (if input is rational) Lower algorithmic degree (faster computations) Ideal for VLSI applications -- majority rectilinear edges Often simpler (more efficient) algorithms L order-k VD of points in optimal O(m log n) time [Liu, Papadopoulou, Lee, 2011] Hausdorff VD (non-crossing clusters) in optimal O(nlogn) time by a simple two–pass plane sweep. [Papadopoulou & Xu 2011] 41 [] L Voronoi diagram of line segments Software submitted to CGAL(based on CGAL L2) [Cheilaris & Dey] CGAL: Computational Geometry Algorithms Library, https://www.cgal.org 42