Computational Geometry: Farthest-Point Voronoi Diagrams

Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Farthest-Point Voronoi Diagrams Outline: I. Farthest site II. Voronoi cell III. Structure of FPVD IV. Construction V. Smallest-Width Annulus Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

I. Farthest Point Given a point ?, ?? ? is its farthest point if for all 1 ? ? ? = {?1,?2, ,??} Sites ?2 ?3 ? ?? |? ??| ?2 ?4 ?1 ?5 ?9 ?6 ?7 ?8 ?1 The farthest point of ?1 is ?1. The farthest point of ?2 is ?8.

Not Every Site Can be the Farthest Claim A point ?? ? is the farthest site of some point ? in the plane if and only if ?? is a vertex of the convex hull CH(?) of ?. ?3 ?4 ?1 ?2 ?5 ?9 ?6 ?7 ?8

Proof of Necessity Claim A point ?? ? is the farthest site of some point ?in the plane if and only if ?? is a vertex of the convex hull CH(?) of ?. ( )Suppose there exists some ? such that ?? is its farthest site. Assume that ?? is not a vertex of CH ? . ?? Then ?? is either in the interior CH ? or on one of its edge. ?1 ?? Consider the line ? through ?? and ? (clearly ?? ?). ?? ?2 ? intersects CH ? with two of its edges ?1and ?2. ?? ?? ? One of the four endpoints of ?1 and ?2 must be father from ? than ??. Contradiction. ?

Proof of Sufficiency Claim A point ?? ? is the farthest site of some point ?in the plane if and only if ?? is a vertex of the convex hull CH(?) of ?. ? ( )Suppose ?? is a vertex of CH ? . ? ?? must be extreme in some direction ?. ?? Let ? be the line through ?? in ?. Start at ??. Move on ? in the direction ?. The point ?? ? ?, for large enough ?, is farther from ??than any other site. ?? ? ?

II. Two Sites Half-plane (??, ??) = ? ? closer to ?? than to ??} (??, ??) ?? ?? ??? Perpendicular bisector

Voronoi Cell ? ?? = (??,??) 1 ? ? ? ? Open convex region ?3 ?2 ? 1 vertices ?1 ? ?1 ? 1 edges ?5 ?6 ?14 ?4 ?12 ?16 ?15 ?13

Unboundedness The cell contains a ray ? collinear with ??. ??: farthest point from ?. ? ?3 ?: the line through ??and ?. ?: half-line starting at ? and away from ??. ?2 ?1 ? ?1 ?5 ?6 All the points on ? have ?? as the farthest point! ?4 ? ?

III. Farthest-Point Voronoi Diagram ?3 Tree-like structure ? ?4 ?2 ?1 Edges include segments and half-infinite lines. ? ?5 ? ?5 ?6 No cycles ?4 A cycle would imply a bounded cell. ? ?1 ? ?3 A vertex has 3 farthest sites.

More Properties Any site that is not a vertex of the convex hull has no Voronoi cell. ?5? ?45 ? ?? ??? ?2 ?4? ? ?4 It contributes no Voronoi edge. ?1 ?3 ?4? ? ?? ?? Every Voronoi edge is part of a bisector of two convex hull vertices. ?2? ?24 ?4 ?34 ?? ?1? ?5 ? ?3 ?23 ?12 ? ?2 ?(?) vertices, edges and cells

Center of Smallest Enclosing Disk Two possibilities: ?? ?? Vertex 3 equidistant farthest sites ? Midpoint of two sites defining an edge two equidistant farthest sites ?? ?? ??

Storage Doubly-connected edge list (DCEL) with modifications Half-infinite edge ? ? ? = ( 1,0) If no origin, stores the direction of the edge ( ?) instead of coordinates. Either next(?) or prev(?) is undefined.

IV. Preprocessing for Construction 1. Compute the convex hull CH ? with vertices. 2. Order vertices of the hull randomly. ??+1 ?1,?2, ,? (new indices) ?1 ? ?? ?2 3. Remove ? ,? 1, ,?4one by one in the order. cw(??) For each ??, store its clockwise neighbor cw(??) and counterclockwise neighbor ccw(??) at the time of removal. ccw(??) ?? cannot be a neighbor of any point removed later. ??

Construction 1. Initialize with the FPVD of ?1,?2,?3. ? ?3 ?2 ?1 ? ?1 ? ?2 ?3

Construction (contd) 2. Insert ?4,?5, ,? one by one in the order. ????? 1 for ?1, ,?? 1: ?? ? (??) most counterclockwise half-edge in a traversal of the boundary of ? (??)

How to Add ??? The cell ? (??) of ??will come in between the adjacent cells ? (cw(??)) and ? (ccw(??)). ?? cw(??) ccw(??) has a pointer to bisector ? (most counterclockwise edge in its cell. ccw(??) ? (??) ? Bisector of ccw(??) and ?? will contribute a half-edge ? to ? (??). ? ? ? (ccw(??)) Traverse the boundary of ? (ccw(??)), starting at ?, in a clockwise way to find the intersection ? of ? with a boundary edge ? between ? (ccw(??)) and, say, ? (??) of another site ??. ? (cw(??)) ? Move along ? to ? and cross into the cell of ??.

Moving on ?? At ? start a clockwise traversal of the boundary of the cell ? (??). cw(??) ccw(??) ? (??) ? Traversal stops at an edge ? that intersects the bisector of ??and ??. ? ? ? Exit the cell ? (??), and so on. ? (ccw(??)) ? (cw(??)) Last bisector will be between ?? and cw(??). ? Trace out the boundary of ? (??) by traversing a sequence of cells, each in a clockwise way.

Summary ?? All new edges are added to DCEL. cw(??) ccw(??) Afterward, all the edges lying inside the cell of ??are removed. ? (ccw(??)) ? (??) Theorem FPVD can be constructed in ?(?log?) expected time using ?(?) storage. ?(?log?) time to compute the convex hull. ?(?) time to construct FPVD (backward analysis).

V. Roundness of a Point Set The roundness of a set of points is measured by the minimum width of any annulus that contains the points. Observation: There must be one point each on ?????? and ??????. ?????? Otherwise, we can always reduce the size of ??????, or increase that of ??????. But one point on each bounding circle does not yield the smallest- width annulus. ? ? ?????? ? Four degrees of freedom: Center ? = ??,?? Outer radius ? Inner radius ? Need 4 constraints!

Only Three Different Cases (a) (b) (c) 3 points on ?????? 1 point on ?????? 1 point on ?????? 3 points on ?????? 2 points on ?????? 2 points on ??????

Smallest-Width Annulus Case (a) The problem is equivalent to finding the center point ? of the annulus. In case (a) 3 points on ?????? ? ? must be a vertex of the farthest-point Voronoi diagram. (a) 3 points on ?????? 1 point on ??????

Case (b) 3 points on ?????? ? ? must be a vertex of the (nearest-point) Voronoi diagram. (b) 1 point on ?????? 3 points on ??????

Case (c) ? must be at the intersection of an VD edge with an FPVD edge. (c) 2 points on ?????? 2 points on ?????? ? must be on an edge of the FPVD. ? must be on an edge of the VD.

Overlay of VD and FPVD Site Vertex of VD Vertices of the overlay Vertex of FPVD Intersection of VD and FPVD Exactly the candidate centers of the smallest-width annulus. No need to compute the overlay!

Smallest-Width Annulus Algorithm 1. Construct the Voronoi diagram and farthest-point Voronoi diagram. 2. For every vertex ? of the FPVD (?(?) vertices) Its farthest sites ??,??,?? (equidistant) are known (??????). Determine its closest site ?? using VD (??????in ?(log?) time). This yields a candidate annulus. 3. For every vertex ? of the VD (?(?) vertices) Its closest sites ??,??,?? (equidistant) are known (??????). Determine its farthest site ?? using FPVD (??????in ?(log?) time). This yields a candidate annulus.

Algorithm (contd) 4. For every pair of edges, one from VD and the other form FPVD (?(?2) pairs) Test if they intersect. If so, the two closest sites ??,?? and two farthest sites ??,?? are known. Construct the annulus in ?(1) time. 5. Choose the smallest-width annulus of all constructed annuli. Theorem Given a set of ? points in the plane, the smallest-width annulus can be determined in ?(?2) time using ?(?) storage.