Ch.7: Voronoi Diagrams
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 7.1. Definition and Basic Properties 7.2. Computing the Voronoi Diagram 7.3. Voronoi Diagrams of Line Segments 7.4. Farthest-Point Voronoi Diagrams 7.5. Notes and Comments
98 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Voronoi Diagrams] Supermarkets, post offices or provincial capitals are sites. What does the Voronoi assignment model predict about who uses which site?
Everyone goes to the nearest site. So the trading area of a site is the set of points closer to it than to any other site. Predicted trading areas of the capitals of the twelve Dutch provinces.
[Voronoi Diagrams] Which four simplifying assumptions lead to the Voronoi assignment model (everyone goes to the nearest site)?
Same price at every site; cost = price + transport; transport cost = Euclidean distance times a fixed price per unit distance; consumers minimize cost. Then minimizing cost means minimizing distance.
[Voronoi Diagrams] The subdivision of the plane into the trading areas of the sites (every point assigned to its nearest site) is the Voronoi diagram of the sites.
The chapter's subtitle, "The Post Office Problem", comes from the traditional view of the sites as post offices where customers post their letters.
[Definition and Basic Properties] P={p1,…,pn}P = \{p_1, \dots, p_n\}P={p1,…,pn} is a set of nnn distinct points in the plane (the sites). What is the Voronoi diagram Vor(P)\operatorname{Vor}(P)Vor(P) ?
The subdivision of the plane into nnn cells, one per site: qqq is in the cell of pip_ipi iff dist(q,pi)<dist(q,pj)\operatorname{dist}(q, p_i) < \operatorname{dist}(q, p_j)dist(q,pi)<dist(q,pj) for all j≠ij \neq ij=i . The cell of pip_ipi is written V(pi)\mathcal{V}(p_i)V(pi) , the Voronoi cell of pip_ipi . Vor(P)\operatorname{Vor}(P)Vor(P) is also used for just the edges and vertices, e.g. in " Vor(P)\operatorname{Vor}(P)Vor(P) is connected".
[Definition and Basic Properties] For two points p,qp, qp,q in the plane, what is their bisector, and what is h(p,q)h(p, q)h(p,q) ?
Bisector: the perpendicular bisector of the segment pq‾\overline{pq}pq . h(p,q)h(p,q)h(p,q) : the open half-plane of the bisector that contains ppp . So r∈h(p,q)r \in h(p, q)r∈h(p,q) iff dist(r,p)<dist(r,q)\operatorname{dist}(r, p) < \operatorname{dist}(r, q)dist(r,p)<dist(r,q) .
[Definition and Basic Properties] Observation 7.1 For sites P={p1,…,pn}P = \{p_1, \dots, p_n\}P={p1,…,pn} and h(p,q)h(p, q)h(p,q) the open half-plane of the bisector of p,qp, qp,q containing ppp : V(pi)= ?\mathcal{V}(p_i) = \; ?V(pi)=?
V(pi)=⋂1≤j≤n, j≠ih(pi,pj)\boldsymbol{\mathcal{V}(p_i) = \bigcap_{1 \le j \le n, \, j \neq i} h(p_i, p_j)}V(pi)=⋂1≤j≤n,j=ih(pi,pj) The cell of the middle site: the intersection of four half-planes.
[Definition and Basic Properties] For nnn sites, what kind of region is a Voronoi cell V(pi)\mathcal{V}(p_i)V(pi) , and how many vertices and edges can it have?
A (possibly unbounded) open convex polygonal region with at most n−1n-1n−1 vertices and at most n−1n-1n−1 edges. It is the intersection of n−1n-1n−1 open half-planes, one per other site.
[Definition and Basic Properties] Can a single Voronoi cell of nnn sites have n−1n - 1n−1 vertices? Give a configuration.
Yes: one site in the centre, the other n−1n-1n−1 sites around it on a circle. The centre cell is bounded by all n−1n-1n−1 bisectors with the outer sites.
[Definition and Basic Properties] Theorem 7.2 Let PPP be a set of nnn point sites in the plane. If all sites are collinear, Vor(P)\operatorname{Vor}(P)Vor(P) consists of … ? Otherwise … ?
Collinear: n−1n-1n−1 parallel lines. Otherwise: Vor(P)\operatorname{Vor}(P)Vor(P) is connected and its edges are segments or half-lines.
[Definition and Basic Properties] Sites PPP , not all collinear. Suppose an edge eee of Vor(P)\operatorname{Vor}(P)Vor(P) is a full line, separating the cells V(pi)\mathcal{V}(p_i)V(pi) and V(pj)\mathcal{V}(p_j)V(pj) .How does the proof get a contradiction?
Take a site pkp_kpk not collinear with pi,pjp_i, p_jpi,pj : the bisector of pj,pkp_j, p_kpj,pk crosses eee , and beyond it eee is closer to pkp_kpk than to pjp_jpj , so not on the boundary of V(pj)\mathcal{V}(p_j)V(pj) . The bisector of pj,pkp_j, p_kpj,pk is not parallel to eee (the bisector of pi,pjp_i, p_jpi,pj ), so it must intersect eee .
[Definition and Basic Properties] Known: if the sites are not all collinear, no edge of the Voronoi diagram is a full line.Why is the Voronoi diagram then connected?
Otherwise some cell would split the plane into two parts; a convex cell can only do that as a strip between two parallel full lines. But edges are not full lines, a contradiction.
[Definition and Basic Properties] Theorem 7.3 For n≥3n \ge 3n≥3 point sites in the plane, the Voronoi diagram has at most … vertices and at most … edges?
At most 2n−5\boldsymbol{2n - 5}2n−5 vertices and 3n−6\boldsymbol{3n - 6}3n−6 edges. So the complexity is linear, although there are quadratically many bisectors and bisector intersections.
[Definition and Basic Properties] The bound of at most 2n−52n-52n−5 vertices and 3n−63n-63n−6 edges for the Voronoi diagram of n≥3n \ge 3n≥3 non-collinear sites is proved with Euler's formula mv−me+mf=2m_v - m_e + m_f = 2mv−me+mf=2 for connected planar graphs.Why can't Euler's formula be applied to Vor(P)\operatorname{Vor}(P)Vor(P) directly, and what is the fix?
Vor(P)\operatorname{Vor}(P)Vor(P) has half-infinite edges. Fix: add a vertex v∞v_\inftyv∞ "at infinity" and connect all half-infinite edges to it.
[Definition and Basic Properties] Vor(P)\operatorname{Vor}(P)Vor(P) of n≥3n \ge 3n≥3 non-collinear sites has nvn_vnv vertices and nen_ene edges. Adding a vertex v∞v_\inftyv∞ at infinity, joined to all half-infinite edges, gives a connected planar graph with nnn faces.Which two relations prove nv≤2n−5n_v \le 2n - 5nv≤2n−5 and ne≤3n−6n_e \le 3n - 6ne≤3n−6 ?
Euler: (nv+1)−ne+n=2(n_v + 1) - n_e + n = 2(nv+1)−ne+n=2 . Degrees: 2ne≥3(nv+1)2n_e \ge 3(n_v + 1)2ne≥3(nv+1) , as every vertex (also v∞v_\inftyv∞ ) has degree at least 3. Substituting ne=nv+n−1n_e = n_v + n - 1ne=nv+n−1 : 2nv+2n−2≥3nv+32n_v + 2n - 2 \ge 3n_v + 32nv+2n−2≥3nv+3 , so nv≤2n−5n_v \le 2n - 5nv≤2n−5 , and then ne≤3n−6n_e \le 3n - 6ne≤3n−6 .
[Definition and Basic Properties] The Voronoi diagram of n≥3n \ge 3n≥3 sites has at most 3n−63n - 63n−6 edges.Why is the average number of vertices of a Voronoi cell less than six?
Summed over all cells, the vertex counts are at most 2ne≤6n−122n_e \le 6n - 122ne≤6n−12 . Each edge bounds two cells, and a cell has at most as many vertices as edges. Divide by nnn cells: less than 6.
[Definition and Basic Properties] For a set of sites PPP and a point qqq , what is the largest empty circle CP(q)C_P(q)CP(q) of qqq with respect to PPP ?
The largest circle centred at qqq that contains no site of PPP in its interior.
[Definition and Basic Properties] Theorem 7.4 (i) For sites PPP and CP(q)C_P(q)CP(q) the largest circle centred at qqq with no site in its interior: a point qqq is a vertex of Vor(P)\operatorname{Vor}(P)Vor(P) iff … ?
CP(q)C_P(q)CP(q) contains three or more sites on its boundary. Empty circles at a vertex (three sites on it) and at a point of an edge (two sites).
[Definition and Basic Properties] Theorem 7.4 (ii) For sites PPP and CP(q)C_P(q)CP(q) the largest circle centred at qqq with no site in its interior: the bisector of sites pi,pjp_i, p_jpi,pj defines an edge of Vor(P)\operatorname{Vor}(P)Vor(P) iff … ?
Some point qqq on the bisector has CP(q)C_P(q)CP(q) with pip_ipi and pjp_jpj on its boundary and no other site.
[Definition and Basic Properties] CP(q)C_P(q)CP(q) is the largest circle centred at qqq with no site of PPP in its interior.Why is qqq a vertex of Vor(P)\operatorname{Vor}(P)Vor(P) exactly when CP(q)C_P(q)CP(q) has three or more sites on its boundary?
Three sites on an empty CP(q)C_P(q)CP(q) are nearest sites of qqq , so qqq lies on the boundary of their three cells. Conversely, a vertex lies on at least three cells, so it is equidistant from three sites and no site is closer. A closer site would mean the three cells don't meet at qqq .
[Definition and Basic Properties] CP(q)C_P(q)CP(q) is the largest circle centred at qqq with no site of PPP in its interior. Known: qqq is a Voronoi vertex iff CP(q)C_P(q)CP(q) has ≥3\ge 3≥3 sites on its boundary.If CP(q)C_P(q)CP(q) has exactly the sites pi,pjp_i, p_jpi,pj on its boundary, why is qqq on a Voronoi edge of the bisector of pi,pjp_i, p_jpi,pj ?
dist(q,pi)=dist(q,pj)≤dist(q,pk)\operatorname{dist}(q, p_i) = \operatorname{dist}(q, p_j) \le \operatorname{dist}(q, p_k)dist(q,pi)=dist(q,pj)≤dist(q,pk) for all kkk , so qqq is on an edge or vertex of Vor(P)\operatorname{Vor}(P)Vor(P) , and with only two sites on CP(q)C_P(q)CP(q) it is not a vertex.
[Computing the Voronoi Diagram] V(pi)\mathcal{V}(p_i)V(pi) is the intersection of the n−1n-1n−1 half-planes h(pi,pj)h(p_i, p_j)h(pi,pj) , j≠ij \neq ij=i .How fast does computing each cell this way (half-plane intersection) build the Voronoi diagram of nnn sites?
O(n2logn)\boldsymbol{O(n^2 \log n)}O(n2logn) O(nlogn)O(n \log n)O(nlogn) per cell for the half-plane intersection, times nnn cells.
[Computing the Voronoi Diagram] The plane sweep algorithm that computes the Voronoi diagram of nnn point sites in O(nlogn)O(n \log n)O(nlogn) time is called Fortune's algorithm.
[Computing the Voronoi Diagram] Why does every algorithm computing the Voronoi diagram of nnn point sites need Ω(nlogn)\Omega(n \log n)Ω(nlogn) time in the worst case?
Sorting nnn real numbers is reducible to computing a Voronoi diagram. So Fortune's algorithm, with O(nlogn)O(n \log n)O(nlogn) time, is optimal.
[Computing the Voronoi Diagram] Sweeping a horizontal line ℓ\ellℓ downwards over the sites, why can't one maintain the intersection of the Voronoi diagram with ℓ\ellℓ ?
The part of the Voronoi diagram above ℓ\ellℓ depends on sites below ℓ\ellℓ . e.g. ℓ\ellℓ reaches the topmost vertex of V(pi)\mathcal{V}(p_i)V(pi) before it reaches pip_ipi . Fortune's algorithm instead maintains the part of the diagram above ℓ\ellℓ that sites below ℓ\ellℓ can no longer change.
[Computing the Voronoi Diagram] ℓ\ellℓ is a horizontal sweep line and ℓ+\ell^+ℓ+ the closed half-plane above it. For which points q∈ℓ+q \in \ell^+q∈ℓ+ is the nearest site already certain?
Those at least as close to some site pi∈ℓ+p_i \in \ell^+pi∈ℓ+ as to ℓ\ellℓ . Every site below ℓ\ellℓ is farther from qqq than ℓ\ellℓ is. The points closer to pip_ipi than to ℓ\ellℓ are bounded by a parabola.
[Computing the Voronoi Diagram] What is the beach line in Fortune's algorithm (sweep line ℓ\ellℓ moving down)?
The sequence of parabolic arcs bounding the points that are closer to some site above ℓ\ellℓ than to ℓ\ellℓ . Equivalently: each site pip_ipi above ℓ\ellℓ defines a parabola βi\beta_iβi (the points equidistant from pip_ipi and ℓ\ellℓ ), and the beach line takes, at each xxx , the lowest point of all these parabolas.
[Computing the Voronoi Diagram] The sweep line is y=ℓyy = \ell_yy=ℓy and the site pj=(pj,x,pj,y)p_j = (p_{j,x}, p_{j,y})pj=(pj,x,pj,y) lies above it. Which points form the parabola βj\beta_jβj , and what is its equation?
The points equidistant from pjp_jpj and ℓ\ellℓ : y=12(pj,y−ℓy)(x2−2pj,xx+pj,x2+pj,y2−ℓy2)\displaystyle y = \frac{1}{2(p_{j,y} - \ell_y)} \left( x^2 - 2p_{j,x}x + p_{j,x}^2 + p_{j,y}^2 - \ell_y^2 \right)y=2(pj,y−ℓy)1(x2−2pj,xx+pj,x2+pj,y2−ℓy2) From (x−pj,x)2+(y−pj,y)2=(y−ℓy)2(x - p_{j,x})^2 + (y - p_{j,y})^2 = (y - \ell_y)^2(x−pj,x)2+(y−pj,y)2=(y−ℓy)2 .
[Computing the Voronoi Diagram] Observation 7.5: the beach line is x-monotone, i.e. every vertical line intersects it in exactly one point.
[Computing the Voronoi Diagram] What do the breakpoints between consecutive arcs of the beach line do as the sweep line moves down?
They trace out the edges of the Voronoi diagram. A breakpoint between the arcs of pip_ipi and pjp_jpj is equidistant from pip_ipi , pjp_jpj and ℓ\ellℓ , with no site closer. One parabola can contribute several arcs to the beach line.
[Computing the Voronoi Diagram] In Fortune's algorithm, what is a site event, and what happens to the beach line there?
The sweep line reaches a new site; its parabola appears with zero width (a vertical segment from the site up to the beach line) and then widens. The arc above the site is split, and the new arc grows in between.
[Computing the Voronoi Diagram] What happens to the Voronoi diagram under construction at a site event of Fortune's algorithm?
Two new breakpoints appear at the same point and move apart in opposite directions, tracing out one new edge. The new edge is at first not connected to the rest of the diagram above ℓ\ellℓ ; it gets connected later when it runs into another edge.
[Computing the Voronoi Diagram] Lemma 7.6 In Fortune's algorithm (beach line of parabolic arcs above the sweep line ℓ\ellℓ ), the only way a new arc can appear on the beach line is … ?
Through a site event (the sweep line reaching a new site).
[Computing the Voronoi Diagram] Beach line: lower envelope of the parabolas βi\beta_iβi (points equidistant from site pip_ipi and the sweep line ℓ\ellℓ ) of the sites above ℓ\ellℓ .Why can't an existing parabola βj\beta_jβj break through the beach line in the middle of an arc of βi\beta_iβi ?
At that moment βi\beta_iβi and βj\beta_jβj would be tangent (exactly one common point), which is impossible for two such parabolas. Both sites lie above ℓ\ellℓ : pi,y,pj,y>ℓyp_{i,y}, p_{j,y} > \ell_ypi,y,pj,y>ℓy .
[Computing the Voronoi Diagram] Beach line: lower envelope of the parabolas βi\beta_iβi (points equidistant from site pip_ipi and the sweep line ℓ\ellℓ ) of the sites above ℓ\ellℓ .Why can't an existing parabola βj\beta_jβj appear on the beach line at the breakpoint qqq between arcs of βi\beta_iβi and βk\beta_kβk ?
The circle CCC centred at qqq through pi,pj,pkp_i, p_j, p_kpi,pj,pk is tangent to ℓ\ellℓ ; as ℓ\ellℓ moves down, pip_ipi or pkp_kpk enters CCC , so it is closer than pjp_jpj near qqq . CCC cannot stay tangent to ℓ\ellℓ , keep an empty interior and still pass through pjp_jpj . Left: the moment βj\beta_jβj would appear. Right: the circle through pjp_jpj tangent to ℓ\ellℓ once ℓ\ellℓ has moved down.
[Computing the Voronoi Diagram] With nnn point sites, at most how many arcs does the beach line of Fortune's algorithm have, and why?
2n−1\boldsymbol{2n - 1}2n−1 Arcs appear only at site events, and each site event creates one new arc and splits at most one existing arc into two.
[Computing the Voronoi Diagram] In Fortune's algorithm, what is a circle event?
The sweep line reaches the lowest point of a circle through three sites that define consecutive arcs of the beach line; the middle arc shrinks to a point and disappears. The arc α′\alpha'α′ of pjp_jpj disappears at qqq ; the two breakpoints meet and so do two Voronoi edges.
[Computing the Voronoi Diagram] At the moment an arc α′\alpha'α′ of the beach line shrinks to a point qqq , between its neighbour arcs α\alphaα and α′′\alpha''α′′ (defined by distinct sites pip_ipi , pkp_kpk ; α′\alpha'α′ by pjp_jpj ).Why is qqq a vertex of the Voronoi diagram?
The circle centred at qqq through pi,pj,pkp_i, p_j, p_kpi,pj,pk has its lowest point on ℓ\ellℓ and has no site inside: by the empty circle criterion, qqq is a vertex. qqq is on all three parabolas, so equidistant from ℓ\ellℓ and the three sites. A site inside the circle would be closer to qqq than ℓ\ellℓ is, but qqq is on the beach line.
[Computing the Voronoi Diagram] Lemma 7.7 In Fortune's algorithm, the only way an existing arc can disappear from the beach line is … ?
Through a circle event.
[Computing the Voronoi Diagram] In Fortune's algorithm, what happens to the beach line and to the Voronoi diagram at a site event, and at a circle event?
Site event: a new arc appears and a new edge starts to grow. Circle event: an arc disappears and two growing edges meet in a vertex.
[Computing the Voronoi Diagram] Fortune's algorithm stores the Voronoi diagram in a doubly-connected edge list. Why does it add a bounding box?
The Voronoi diagram has half-lines (or full lines), which a doubly-connected edge list can't represent. The box is large enough to contain all Voronoi vertices; the result is the box plus the diagram inside it.
[Computing the Voronoi Diagram] Fortune's algorithm keeps the beach line in a balanced binary search tree T\mathcal{T}T . What do its leaves and its internal nodes represent?
Leaves: the arcs, left to right, each storing the site defining it. Internal nodes: the breakpoints, as tuples ⟨pi,pj⟩\langle p_i, p_j \rangle⟨pi,pj⟩ ( pip_ipi 's parabola left of the breakpoint, pjp_jpj 's to the right). The parabolas themselves are not stored.
[Computing the Voronoi Diagram] Fortune's algorithm: the beach line is a balanced search tree T\mathcal{T}T , leaves = arcs, internal nodes = breakpoints stored as tuples ⟨pi,pj⟩\langle p_i, p_j \rangle⟨pi,pj⟩ of sites.How is the arc vertically above a new site found in O(logn)O(\log n)O(logn) time?
Descend T\mathcal{T}T , comparing the site's xxx -coordinate with that of the breakpoint at each internal node. The breakpoint's xxx -coordinate is computed in constant time from ⟨pi,pj⟩\langle p_i, p_j \rangle⟨pi,pj⟩ and the position of the sweep line.
[Computing the Voronoi Diagram] Fortune's algorithm: the beach line is a balanced search tree T\mathcal{T}T , leaves = arcs, internal nodes = breakpoints.Which pointers do the leaves and the internal nodes of T\mathcal{T}T store?
Leaf of arc α\alphaα : the circle event in the event queue where α\alphaα disappears (nil if none is known). Internal node: one half-edge of the Voronoi edge its breakpoint traces.
[Computing the Voronoi Diagram] What does the event queue Q\mathcal{Q}Q of Fortune's algorithm store, and with what priority?
Priority = yyy -coordinate. Site event: the site. Circle event: the lowest point of the circle, with a pointer to the leaf of T\mathcal{T}T whose arc will disappear. All site events are known in advance; circle events are detected during the sweep.
[Computing the Voronoi Diagram] In Fortune's algorithm, which triples of consecutive beach-line arcs define a potential circle event?
Those whose two breakpoints converge. If the breakpoints move away from each other along their bisectors, they never meet and there is no event. Diverging breakpoints: no circle event.
[Computing the Voronoi Diagram] A circle event of Fortune's algorithm that never takes place, because its triple of consecutive arcs disappears first (e.g. a new site's arc appears between them), is a false alarm.
When a triple disappears, its circle event is deleted from the event queue, found via the pointer from the leaf in T\mathcal{T}T .
[Computing the Voronoi Diagram] At a site event in Fortune's algorithm, three new triples of consecutive arcs appear (new arc on the left, middle, right). Which one can never cause a circle event, and why?
The one with the new arc in the middle. Its left and right arcs come from the same parabola (the split arc), so its breakpoints diverge.
[Computing the Voronoi Diagram] Lemma 7.8 In Fortune's algorithm, every Voronoi vertex is … ?
Detected by means of a circle event.
[Computing the Voronoi Diagram] A Voronoi vertex qqq is the centre of an empty circle C(pi,pj,pk)C(p_i, p_j, p_k)C(pi,pj,pk) through three sites, met in this order clockwise from its lowest point.Why are there, just before the sweep line reaches the lowest point of CCC , three consecutive beach-line arcs of pi,pj,pkp_i, p_j, p_kpi,pj,pk ?
Some empty circle through pi,pjp_i, p_jpi,pj touches the sweep line, so their arcs are adjacent; likewise for pj,pkp_j, p_kpj,pk ; and the two arcs of pjp_jpj are the same arc. So the circle event is in the queue just before it happens, and the vertex is detected. (Proved for the case of no further sites on CCC , lowest point not a site.)
[Computing the Voronoi Diagram] What is the overall structure of Fortune's algorithm for the Voronoi diagram of nnn point sites?
Put all site events into Q\mathcal{Q}Q ; repeatedly remove the event with the largest yyy and handle it as a site or circle event; then attach the half-infinite edges to a bounding box and add the cell records. Start: empty tree T\mathcal{T}T and empty doubly-connected edge list. At the end, the internal nodes still in T\mathcal{T}T are the half-infinite edges.
[Computing the Voronoi Diagram] Fortune's algorithm: tree T\mathcal{T}T (leaves = arcs, internal nodes = breakpoints ⟨pi,pj⟩\langle p_i, p_j \rangle⟨pi,pj⟩ ), event queue Q\mathcal{Q}Q .At a site event for pip_ipi , how is T\mathcal{T}T updated?
Find the arc α\alphaα above pip_ipi and delete α\alphaα 's circle event (a false alarm); replace α\alphaα 's leaf by three leaves pj,pi,pjp_j, p_i, p_jpj,pi,pj ( pjp_jpj the site of α\alphaα ), with breakpoints ⟨pj,pi⟩\langle p_j, p_i \rangle⟨pj,pi⟩ , ⟨pi,pj⟩\langle p_i, p_j \rangle⟨pi,pj⟩ ; rebalance. If T\mathcal{T}T is empty, pip_ipi simply becomes its only leaf.
[Computing the Voronoi Diagram] Fortune's algorithm, site event for pip_ipi : the arc α\alphaα of site pjp_jpj above pip_ipi has been split and the arc of pip_ipi inserted in between.What else does the site event handler do?
Create half-edge records for the edge between V(pi)\mathcal{V}(p_i)V(pi) and V(pj)\mathcal{V}(p_j)V(pj) ; check the two triples with the new arc on the left and on the right, and insert a circle event for each with converging breakpoints. Pointers are set between the leaf in T\mathcal{T}T and the event in Q\mathcal{Q}Q .
[Computing the Voronoi Diagram] Fortune's algorithm: tree T\mathcal{T}T (leaves = arcs, internal nodes = breakpoints), event queue Q\mathcal{Q}Q , doubly-connected edge list D\mathcal{D}D .What does the circle event handler do when the arc α\alphaα (leaf γ\gammaγ ) disappears?
Delete γ\gammaγ (update breakpoints, rebalance) and all circle events involving α\alphaα ; add the circle's centre as a vertex to D\mathcal{D}D with half-edges for the new breakpoint; check the new triples with α\alphaα 's former left and right neighbour in the middle. The other circle events involving α\alphaα are found via the predecessor and successor of γ\gammaγ in T\mathcal{T}T .
[Computing the Voronoi Diagram] Lemma 7.9 / Theorem 7.10 The Voronoi diagram of nnn point sites in the plane is computed with Fortune's sweep line algorithm in … time using … storage?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) time, O(n)\boldsymbol{O(n)}O(n) storage
[Computing the Voronoi Diagram] Why does Fortune's algorithm on nnn point sites handle only O(n)O(n)O(n) events, each in O(logn)O(\log n)O(logn) time?
nnn site events, and every processed circle event creates a Voronoi vertex, of which there are at most 2n−52n - 52n−5 . Each event needs a constant number of O(logn)O(\log n)O(logn) operations on T\mathcal{T}T and Q\mathcal{Q}Q . False alarms are deleted before being processed; their cost is charged to the event that created or deleted them.
[Computing the Voronoi Diagram] In Fortune's algorithm, events with the same yyy -coordinate can be handled in any order, except in which situation?
At the very start: if the second site has the same yyy as the first, special code is needed, since there is no arc above the second site yet.
[Computing the Voronoi Diagram] In Fortune's algorithm, four or more sites lie on a common empty circle. What does the algorithm produce, handling the coinciding circle events in arbitrary order?
Two vertices of degree three at the same location, joined by a zero-length edge, instead of one vertex of degree four. Zero-length edges can be removed in post-processing.
[Computing the Voronoi Diagram] In Fortune's algorithm, a new site lies exactly below the breakpoint between two arcs. How is this degenerate case handled?
Split either arc; the zero-length piece is the middle of a triple whose circle event has its lowest point at the new site. Handling this circle event correctly creates the Voronoi vertex, and the zero-length arc is deleted later.
[Computing the Voronoi Diagram] In Fortune's algorithm, three consecutive beach-line arcs are defined by three collinear sites. Is there a circle event?
No: collinear sites define no circle.
[Voronoi Diagrams of Line Segments] For the Voronoi diagram of line segments, what is the distance from a point to a segment?
The distance to the closest point of the segment.
[Voronoi Diagrams of Line Segments] What does the bisector of two disjoint line segments look like?
Up to seven parts, each a line segment or a parabolic arc. A part is parabolic when the closest point of one segment is an endpoint and that of the other is in its interior; otherwise it is straight.
[Voronoi Diagrams of Line Segments] Why does the book assume the line segment sites are strictly disjoint, not just non-crossing?
With a shared endpoint, a whole region can be equally close to two segments, so bisectors are not even curves. In applications the segments can often be shortened slightly. Grey: points equally close to two segments via their common endpoint.
[Voronoi Diagrams of Line Segments] What is the complexity (vertices, edges, faces) of the Voronoi diagram of nnn disjoint line segments?
O(n)\boldsymbol{O(n)}O(n) As for points, although the bisectors are more complex.
[Voronoi Diagrams of Line Segments] Sweep line ℓ\ellℓ over disjoint line segment sites: what pieces form the beach line?
Parabolic arcs where the beach line is closest to a site endpoint, straight segments where it is closest to a site interior. Only the parts of sites above ℓ\ellℓ count. A site interior crossing ℓ\ellℓ gives two straight segments ending at the crossing. The breakpoints trace the dashed arcs, which include the Voronoi edges.
[Voronoi Diagrams of Line Segments] Sweep over disjoint line segment sites: what are the five types of beach-line breakpoint ppp (equidistant from its closest site part(s) and ℓ\ellℓ )?
Closest to two endpoints; to two interiors; to an endpoint and an interior of different sites; to an endpoint via a perpendicular to its own segment; or a site interior crossing ℓ\ellℓ . They trace, in this order: a segment, a segment, a parabolic arc, a segment, and the site interior itself.
[Voronoi Diagrams of Line Segments] Sweep over disjoint line segment sites. Breakpoint types (4): closest to a site endpoint, with the shortest distance perpendicular to that endpoint's own segment; (5): a site interior crossing the sweep line.Why do types (4) and (5) not trace Voronoi edges?
Only one site is involved. The algorithm still has to handle these breakpoints and their events.
[Voronoi Diagrams of Line Segments] Sweeping over disjoint line segment sites: what happens at a site event at an upper endpoint, and at a lower endpoint?
Upper: the arc above it is split and four new arcs appear in between. Lower: the breakpoint where the site interior crosses ℓ\ellℓ is replaced by two breakpoints with a new parabolic arc (for the endpoint) between them. The four new arcs at an upper endpoint have breakpoints of the types "closest to an endpoint via a perpendicular" and "site interior crossing ℓ\ellℓ ".
[Voronoi Diagrams of Line Segments] Sweeping over disjoint line segment sites: when do circle events occur, and how many sites define one?
When ℓ\ellℓ reaches the bottom of an empty circle defined by two or three sites above ℓ\ellℓ ; an arc of the beach line disappears. Two sites when one of the meeting breakpoints is of the "endpoint via a perpendicular" type, else three. Breakpoints where a site interior crosses ℓ\ellℓ are never involved, the segments being disjoint.
[Voronoi Diagrams of Line Segments] The Voronoi diagram of line segments has parabolic edges. How can a plain doubly-connected edge list store it?
Store with each face its site: an edge's shape follows in O(1)O(1)O(1) from its two sites and two vertices. For a half-edge e⃗\vec{e}e : sites via IncidentFace(e⃗)IncidentFace(\vec{e})IncidentFace(e) , IncidentFace(Twin(e⃗))IncidentFace(Twin(\vec{e}))IncidentFace(Twin(e)) ; vertices via Origin(e⃗)Origin(\vec{e})Origin(e) , Origin(Twin(e⃗))Origin(Twin(\vec{e}))Origin(Twin(e)) .
[Voronoi Diagrams of Line Segments] Theorem 7.11 The Voronoi diagram of nnn disjoint line segment sites can be computed in … time using … storage?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) time, O(n)\boldsymbol{O(n)}O(n) storage The sweep for points, with more cases; still O(n)O(n)O(n) events, each in O(logn)O(\log n)O(logn) time.
[Voronoi Diagrams of Line Segments] What is the idea of the retraction technique for moving a disc-shaped robot among line segment obstacles?
Move along the edges of the Voronoi diagram of the obstacles: they lie in the middle between the segments, so give the most clearance. Voronoi diagram of segments and the sides of a box, with start and end disc positions.
[Voronoi Diagrams of Line Segments] Retraction: how is a collision-free path for a disc of radius rrr from qstartq_{\mathrm{start}}qstart to qendq_{\mathrm{end}}qend among disjoint segments SSS found?
Compute Vor(S)\operatorname{Vor}(S)Vor(S) in a box; move qstart,qendq_{\mathrm{start}}, q_{\mathrm{end}}qstart,qend away from their nearest segment onto it ( pstart,pendp_{\mathrm{start}}, p_{\mathrm{end}}pstart,pend ); delete edges whose distance to the nearest sites is ≤r\le r≤r ; search a path pstart→pendp_{\mathrm{start}} \to p_{\mathrm{end}}pstart→pend by depth-first search. pstart,pendp_{\mathrm{start}}, p_{\mathrm{end}}pstart,pend are added as vertices, splitting their edges. Th…
[Voronoi Diagrams of Line Segments] Retraction: move the disc from qstartq_{\mathrm{start}}qstart straight away from its nearest segment onto the Voronoi diagram, then along Voronoi edges with enough clearance.Why does this find a path whenever a collision-free path exists?
Moving away from the nearest obstacle can't cause a collision, and a collision-free path exists iff one exists on the Voronoi diagram.
[Voronoi Diagrams of Line Segments] Theorem 7.12 Given nnn disjoint line segment obstacles and a disc-shaped robot, whether a collision-free path between two positions exists can be determined in … time using … storage?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) time, O(n)\boldsymbol{O(n)}O(n) storage
[Farthest-Point Voronoi Diagrams] What is the roundness of a set of points PPP (e.g. sampled from a manufactured disc by a coordinate measurement machine)?
The width of the smallest-width annulus containing PPP . An annulus is the region between two concentric circles; its width is the difference of their radii.
[Farthest-Point Voronoi Diagrams] How many points of PPP lie on the outer circle CouterC_{\mathrm{outer}}Couter and inner circle CinnerC_{\mathrm{inner}}Cinner of a smallest-width annulus of PPP ? (Three cases.)
≥3\ge 3≥3 outer and ≥1\ge 1≥1 inner; ≥1\ge 1≥1 outer and ≥3\ge 3≥3 inner; or 2 and 2. With fewer points on the circles, a narrower annulus exists.
[Farthest-Point Voronoi Diagrams] Why doesn't the randomized incremental technique for the smallest enclosing disc work for the smallest-width annulus?
A newly added point outside the current optimal annulus need not lie on the boundary of the new optimal annulus.
[Farthest-Point Voronoi Diagrams] What is the farthest-point Voronoi diagram of a point set PPP , and what is the cell of pip_ipi ?
The subdivision of the plane into cells in which the same point of PPP is the farthest. Cell of pip_ipi : the intersection of n−1n-1n−1 half-planes, taking the side of each bisector where pip_ipi is farther. So all cells are convex; some cells are empty.
[Farthest-Point Voronoi Diagrams] Observation 7.13 A point of PPP has a (non-empty) cell in the farthest-point Voronoi diagram of PPP iff … ?
It is a vertex of the convex hull of PPP . The farthest point of PPP from any point in the plane lies on the convex hull.
[Farthest-Point Voronoi Diagrams] Why is every cell of the farthest-point Voronoi diagram unbounded?
If pip_ipi is the farthest point from qqq , it is also the farthest from every point on the half-line from qqq directed away from pip_ipi .
[Farthest-Point Voronoi Diagrams] Why do the vertices and edges of the farthest-point Voronoi diagram form a tree?
The diagram is connected and has no cycles: a cycle would enclose a bounded cell, but all cells are unbounded.
[Farthest-Point Voronoi Diagrams] What is the complexity of the farthest-point Voronoi diagram of nnn points?
O(n)\boldsymbol{O(n)}O(n) vertices, edges and cells; at most 2n−32n - 32n−3 edges.
[Farthest-Point Voronoi Diagrams] Where does the centre of the smallest enclosing disc of PPP lie, in terms of the farthest-point Voronoi diagram of PPP ?
At a vertex, or at the midpoint of the two points defining an edge. The centre has three, respectively two, equidistant farthest points; it cannot have just one.
[Farthest-Point Voronoi Diagrams] The farthest-point Voronoi diagram has half-infinite edges. How is the doubly-connected edge list adapted to store it?
A vertex-like record, storing the direction of the half-infinite edge instead of coordinates, serves as its origin. Half-edges of half-infinite edges have NextNextNext or PrevPrevPrev undefined.
[Farthest-Point Voronoi Diagrams] Computing the farthest-point Voronoi diagram of nnn points: what is done before inserting the cells one by one?
Compute the convex hull, put its hhh vertices in random order p1,…,php_1, \dots, p_hp1,…,ph , and remove ph,…,p4p_h, \dots, p_4ph,…,p4 from the cyclic order, storing each pip_ipi 's clockwise and counterclockwise neighbours cw(pi),ccw(pi)cw(p_i), ccw(p_i)cw(pi),ccw(pi) at removal. Then build the diagram of p1,p2,p3p_1, p_2, p_3p1,p2,p3 and insert p4,…,php_4, \dots, p_hp4,…,ph .
[Farthest-Point Voronoi Diagrams] Farthest-point Voronoi diagram, randomized incremental: inserting pip_ipi into the diagram of p1,…,pi−1p_1, \dots, p_{i-1}p1,…,pi−1 ; cw(pi),ccw(pi)cw(p_i), ccw(p_i)cw(pi),ccw(pi) are pip_ipi 's hull neighbours among p1,…,pi−1p_1, \dots, p_{i-1}p1,…,pi−1 .How is the cell of pip_ipi traced?
Start at the half-infinite edge between the cells of cw(pi)cw(p_i)cw(pi) and ccw(pi)ccw(p_i)ccw(pi) . The bisector of pip_ipi and ccw(pi)ccw(p_i)ccw(pi) gives a new half-infinite edge; walk clockwise around each cell to where the next bisector with pip_ipi leaves it, until the bisector with cw(pi)cw(p_i)cw(pi) . Add the new edges, then delete the old edges inside the new cell. Left: tracing the new cell of pip_ipi . Right: after the obsolete edges are removed.
[Farthest-Point Voronoi Diagrams] Building the farthest-point Voronoi diagram incrementally, what pointer is stored for each inserted point pjp_jpj , and why?
A pointer to the most counterclockwise half-infinite half-edge on the boundary of pjp_jpj 's cell. When pip_ipi is inserted, ccw(pi)ccw(p_i)ccw(pi) thus points to the half-infinite edge between the cells of cw(pi)cw(p_i)cw(pi) and ccw(pi)ccw(p_i)ccw(pi) , where tracing starts.
[Farthest-Point Voronoi Diagrams] Theorem 7.14 The farthest-point Voronoi diagram of nnn points in the plane can be computed in … time using … storage?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) expected time, O(n)\boldsymbol{O(n)}O(n) storage O(nlogn)O(n \log n)O(nlogn) is for the convex hull; given the hhh hull vertices in order, the rest takes O(h)O(h)O(h) expected time.
[Farthest-Point Voronoi Diagrams] Farthest-point Voronoi diagram: cells of the hhh convex hull vertices inserted in random order. Inserting a cell with kkk edges visits kkk old cells with at most 4k−64k - 64k−6 edges in total.Why is the expected time per insertion O(1)O(1)O(1) ?
Backwards analysis: the diagram of p1,…,pip_1, \dots, p_ip1,…,pi has at most 2i−32i - 32i−3 edges, each on two cells, and each pjp_jpj is equally likely to be last, so the expected size of the last cell is less than 4. 2(2i−3)/i<42(2i - 3) / i < 42(2i−3)/i<4 .
[Farthest-Point Voronoi Diagrams] Smallest-width annulus of PPP : either CinnerC_{\mathrm{inner}}Cinner has ≥3\ge 3≥3 points of PPP , or CouterC_{\mathrm{outer}}Couter has ≥3\ge 3≥3 , or both have 2.In each case, where does the centre lie?
≥3\ge 3≥3 inner: a vertex of the Voronoi diagram. ≥3\ge 3≥3 outer: a vertex of the farthest-point Voronoi diagram. 2 and 2: an edge of both diagrams at once. The candidate centres are the vertices of the overlay of the two diagrams.
[Farthest-Point Voronoi Diagrams] How is the smallest-width annulus of nnn points PPP found from the Voronoi and the farthest-point Voronoi diagram?
Each vertex of the farthest-point diagram with its closest point of PPP , each vertex of the Voronoi diagram with its farthest point, and each intersecting pair of edges (one per diagram) gives a candidate; take the narrowest. Each candidate is determined by four points and computed in O(1)O(1)O(1) ; the overlay itself is not computed.
[Farthest-Point Voronoi Diagrams] Theorem 7.15 The smallest-width annulus (and so the roundness) of nnn points in the plane can be determined in … time using … storage?
O(n2)\boldsymbol{O(n^2)}O(n2) time, O(n)\boldsymbol{O(n)}O(n) storage Quadratic because every pair of edges of the two diagrams is tested for intersection.
[Notes and Comments] Which triangulation of a point set is obtained by connecting every two sites whose Voronoi cells are adjacent?
The Delaunay triangulation.
[Notes and Comments] How do Voronoi diagrams relate to convex polyhedra in E3\mathbb{E}^3E3 ?
Map each site ppp to the plane h(p):z=2pxx+2pyy−(px2+py2)h(p): z = 2p_xx + 2p_yy - (p_x^2 + p_y^2)h(p):z=2pxx+2pyy−(px2+py2) , tangent to z=x2+y2z = x^2 + y^2z=x2+y2 above ppp ; projecting the intersection of the half-spaces above these planes onto the xyxyxy -plane gives the Voronoi diagram.
[Notes and Comments] Which was the first optimal O(nlogn)O(n \log n)O(nlogn) algorithm for the Voronoi diagram of nnn point sites in the plane?
A divide-and-conquer algorithm by Shamos and Hoey. The plane sweep algorithm is due to Fortune.
[Notes and Comments] What is the maximum combinatorial complexity of the Voronoi diagram of nnn point sites in Ed\mathbb{E}^dEd ?
Θ(n⌈d/2⌉)\boldsymbol{\Theta(n^{\lceil d/2 \rceil})}Θ(n⌈d/2⌉) It can be computed in O(nlogn+n⌈d/2⌉)O(n \log n + n^{\lceil d/2 \rceil})O(nlogn+n⌈d/2⌉) optimal time.
[Notes and Comments] What is the medial axis (skeleton) of a simple polygon?
The Voronoi diagram of the polygon's edges, inside the polygon. Computable in time linear in the number of edges; used in shape analysis.
[Notes and Comments] What is the order- kkk Voronoi diagram of nnn points, and its maximum complexity?
The partition of the plane by the kkk closest sites; complexity Θ(k(n−k))\Theta(k(n-k))Θ(k(n−k)) . Order 1 is the ordinary Voronoi diagram; order n−1n-1n−1 is the farthest-point Voronoi diagram.