Ch.11: Convex Hulls

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 11.1. The Complexity of Convex Hulls in 3-Space 11.2. Computing Convex Hulls in 3-Space 11.3. The Analysis 11.4. Convex Hulls and Half-Space Intersection 11.5. Voronoi Diagrams Revisited 11.6. Notes and Comments

70 flashcards · Mathematics · by lakesare

Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses

[Convex Hulls] Oil from different wells is a mixture of components in different proportions. Given base mixtures, how does geometry tell whether a desired mixture can be produced by mixing them?
Represent each mixture as a point (its proportions of the components); the desired mixture can be made iff its point lies in the convex hull of the base points. With ddd components the points live in ddd -dimensional space, and the convex hull (a convex polytope) is the set of all producible mixtures.
[Convex Hulls] Mixture ξ1\xi_1ξ1 has 10% of component AAA and 35% of BBB ; mixture ξ2\xi_2ξ2 has 16% of AAA and 20% of BBB . What do you get by mixing ξ1\xi_1ξ1 and ξ2\xi_2ξ2 in the ratio 2:12 : 12:1 ?
12% of AAA and 30% of BBB . q=23(0.1,0.35)+13(0.16,0.2)=(0.12,0.3)q = \frac{2}{3}(0.1, 0.35) + \frac{1}{3}(0.16, 0.2) = (0.12, 0.3)q=32(0.1,0.35)+31(0.16,0.2)=(0.12,0.3) , the point on segment p1p2‾\overline{p_1 p_2}p1p2 with dist⁡(p2,q):dist⁡(q,p1)=2:1\operatorname{dist}(p_2, q) : \operatorname{dist}(q, p_1) = 2 : 1dist(p2,q):dist(q,p1)=2:1 . A third mixture (0.07,0.15)(0.07, 0.15)(0.07,0.15) makes every point of the triangle producible, e.g. (0.13,0.22)(0.13, 0.22)(0.13,0.22) by the ra…
[Convex Hulls] What is a convex combination of points p1,…,pnp_1, \dots, p_np1,…,pn ?
A point ∑i=1nλipi\displaystyle\sum_{i=1}^n \lambda_i p_ii=1∑nλipi with all λi≥0\lambda_i \ge 0λi≥0 and ∑i=1nλi=1\displaystyle\sum_{i=1}^n \lambda_i = 1i=1∑nλi=1 . Mixing base mixtures in the ratio l1:⋯:lnl_1 : \dots : l_nl1:⋯:ln gives the convex combination with λi=li/L\lambda_i = l_i / Lλi=li/L , where L=∑jljL = \sum_j l_jL=∑jlj .
[Convex Hulls] The convex hull of a point set is defined as the intersection of all convex sets containing the points. Which equivalent description in terms of the points themselves does the chapter use?
The set of all convex combinations of the points.
[Convex Hulls] How are convex hulls used to speed up collision detection between objects P1,P2\mathcal{P}_1, \mathcal{P}_2P1,P2 in computer animation?
First test the simpler containing objects P1undefined,P2undefined\widehat{\mathcal{P}_1}, \widehat{\mathcal{P}_2}P1,P2 (e.g. the convex hulls) for intersection; only if they intersect, test the originals. This pays off when the answer is negative most of the time.
[Convex Hulls] For collision detection, why are convex hulls preferred over bounding spheres as approximating objects, and what is the price?
Convex hulls approximate most objects much better, but their intersection tests cost more than for spheres. A better approximation means the originals need testing less often. Convex hull tests are still cheaper than tests on non-convex objects. An object, its bounding sphere (dashed) and its convex hull (dotted).
[The Complexity of Convex Hulls in 3-Space] What is a facet of a convex polytope, and what is an edge?
Facet: a maximal subset of coplanar points on its boundary (necessarily a convex polygon). Edge: an edge of one of its facets.
[The Complexity of Convex Hulls in 3-Space] In the plane, the convex hull of nnn points has at most nnn vertices, which makes its complexity linear at once. Why doesn't the same argument work in 3-space?
A 3-dimensional polytope can have more edges (and facets) than vertices, while a polygon has exactly as many edges as vertices. The convex hull in 3-space still has at most nnn vertices, all of them points of the input.
[The Complexity of Convex Hulls in 3-Space] Theorem 11.1 Let P\mathcal{P}P be a convex polytope with nnn vertices. How many edges and how many facets can P\mathcal{P}P have at most?
At most 3n−6\boldsymbol{3n - 6}3n−6 edges and at most 2n−4\boldsymbol{2n - 4}2n−4 facets.
[The Complexity of Convex Hulls in 3-Space] A convex polytope with nnn vertices has at most 3n−63n - 63n−6 edges and 2n−42n - 42n−4 facets.Which formula does the proof start from, and why does it apply to a polytope?
Euler's formula n−ne+nf=2n - n_e + n_f = 2n−ne+nf=2 (vertices, edges, faces of a connected planar graph): the boundary of a convex polytope can be drawn as a planar graph. One facet maps to the unbounded face. Euler originally stated the formula for polytopes.
[The Complexity of Convex Hulls in 3-Space] Euler: n−ne+nf=2n - n_e + n_f = 2n−ne+nf=2 for the nnn vertices, nen_ene edges, nfn_fnf facets of a convex polytope.How does this give nf≤2n−4n_f \le 2n - 4nf≤2n−4 and ne≤3n−6n_e \le 3n - 6ne≤3n−6 ?
Every face has at least 3 edges and every edge lies on 2 faces, so 2ne≥3nf2 n_e \ge 3 n_f2ne≥3nf . Substituting ne=n+nf−2n_e = n + n_f - 2ne=n+nf−2 : n+nf−2≥32nfn + n_f - 2 \ge \frac{3}{2} n_fn+nf−2≥23nf , so nf≤2n−4n_f \le 2n - 4nf≤2n−4 ; then Euler again gives ne≤3n−6n_e \le 3n - 6ne≤3n−6 .
[The Complexity of Convex Hulls in 3-Space] What is a simplicial polytope, and what is special about it with respect to the bounds 3n−63n - 63n−6 edges and 2n−42n - 42n−4 facets ( nnn vertices)?
Every facet is a triangle; then both bounds are attained exactly, because 2ne=3nf2 n_e = 3 n_f2ne=3nf .
[The Complexity of Convex Hulls in 3-Space] The bounds of at most 3n−63n - 63n−6 edges and 2n−42n - 42n−4 facets for nnn vertices also hold for non-convex polytopes of genus zero, i.e. without holes or tunnels.
For larger genus similar bounds hold.
[The Complexity of Convex Hulls in 3-Space] Corollary 11.2. What is the complexity of the convex hull of a set of nnn points in 3-space?
O(n)\boldsymbol{O(n)}O(n) Its vertices are points of the set, so at most nnn of them, hence at most 3n−63n - 63n−6 edges and 2n−42n - 42n−4 facets.
[Computing Convex Hulls in 3-Space] What is the overall approach of the algorithm for the convex hull CH(P)\mathcal{CH}(P)CH(P) of a set PPP of nnn points in 3-space?
Randomized incremental: start with the tetrahedron of 4 points, then add the other points in random order, maintaining the hull of the points added so far. With Pr={p1,…,pr}P_r = \{p_1, \dots, p_r\}Pr={p1,…,pr} , step rrr turns CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) into CH(Pr)\mathcal{CH}(P_r)CH(Pr) .
[Computing Convex Hulls in 3-Space] How does the 3D convex hull algorithm find its 4 starting points, and what if it can't?
Take any p1,p2p_1, p_2p1,p2 ; walk through PPP for a p3p_3p3 not on line p1p2p_1 p_2p1p2 , then for a p4p_4p4 not in plane p1p2p3p_1 p_2 p_3p1p2p3 . If no such p4p_4p4 exists, all points are coplanar: use a planar convex hull algorithm.
[Computing Convex Hulls in 3-Space] Adding point prp_rpr to the convex hull CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) : what happens if prp_rpr lies inside the hull or on its boundary?
Nothing: CH(Pr)=CH(Pr−1)\mathcal{CH}(P_r) = \mathcal{CH}(P_{r-1})CH(Pr)=CH(Pr−1) .
[Computing Convex Hulls in 3-Space] When is a facet fff of a convex polytope visible from a point xxx ?
When xxx lies in the open half-space bounded by the plane hfh_fhf of fff on the side not containing the polytope. By convexity, the polytope lies in one closed half-space of hfh_fhf . fff is visible from ppp , but not from qqq , which lies on the polytope's side of hfh_fhf .
[Computing Convex Hulls in 3-Space] What are the visible region and the horizon of a point prp_rpr outside the convex polytope CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) ?
Visible region: the connected region formed by the facets visible from prp_rpr . Horizon: the closed curve of edges enclosing it. Projecting the polytope from center prp_rpr onto a plane gives a convex polygon whose boundary is the projection of the horizon.
[Computing Convex Hulls in 3-Space] Point prp_rpr lies outside CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) . How is CH(Pr)\mathcal{CH}(P_r)CH(Pr) obtained?
Remove the facets visible from prp_rpr and add facets connecting prp_rpr to its horizon. The horizon is the border between the kept (invisible) and the replaced (visible) part of the boundary.
[Computing Convex Hulls in 3-Space] How does the 3D convex hull algorithm store the hull, and with which orientation convention?
As a doubly-connected edge list (with 3D vertices); the half-edges of each face form a counterclockwise cycle as seen from outside the polytope. This works because the boundary of a convex polytope is a planar graph.
[Computing Convex Hulls in 3-Space] If the facets of CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) visible from prp_rpr are known, how long does the update to CH(Pr)\mathcal{CH}(P_r)CH(Pr) take in the doubly-connected edge list?
Linear in the total complexity of the facets that disappear.
[Computing Convex Hulls in 3-Space] Adding prp_rpr to the 3D convex hull: what goes wrong when prp_rpr lies in the plane of a facet fff , and how is it handled?
fff is not visible, so it stays, but the new triangles from prp_rpr to fff 's horizon edges are coplanar with fff : they are merged with fff into one facet.
[Computing Convex Hulls in 3-Space] Why does testing every facet for visibility from each new point prp_rpr give only an O(n2)O(n^2)O(n2) convex hull algorithm?
Each test is O(1)O(1)O(1) (which side of a plane), but there are O(r)O(r)O(r) facets at step rrr , so ∑rO(r)=O(n2)\sum_r O(r) = O(n^2)∑rO(r)=O(n2) .
[Computing Convex Hulls in 3-Space] In the 3D convex hull algorithm after inserting p1,…,prp_1, \dots, p_rp1,…,pr , what are the conflict lists Pconflict(f)P_{\text{conflict}}(f)Pconflict(f) and Fconflict(pt)F_{\text{conflict}}(p_t)Fconflict(pt) ?
Pconflict(f)P_{\text{conflict}}(f)Pconflict(f) : the points among pr+1,…,pnp_{r+1}, \dots, p_npr+1,…,pn that can see facet fff ; Fconflict(pt)F_{\text{conflict}}(p_t)Fconflict(pt) ( t>rt > rt>r ): the facets of CH(Pr)\mathcal{CH}(P_r)CH(Pr) visible from ptp_tpt . A point ppp is in conflict with fff because once ppp is added, fff must go.
[Computing Convex Hulls in 3-Space] What is the conflict graph G\mathcal{G}G of the 3D convex hull algorithm, and what does it answer quickly?
A bipartite graph: one node per point not yet inserted, one node per facet of the current hull, and an arc for each visible point-facet pair. It reports Fconflict(pt)F_{\text{conflict}}(p_t)Fconflict(pt) (or Pconflict(f)P_{\text{conflict}}(f)Pconflict(f) ) in time linear in its size, so the facets visible from the next point are found at once.
[Computing Convex Hulls in 3-Space] How is the conflict graph initialized for the starting tetrahedron CH(P4)\mathcal{CH}(P_4)CH(P4) , and in what time?
Walk through the points and test which of the 4 faces each one sees: linear time.
[Computing Convex Hulls in 3-Space] After inserting prp_rpr into the 3D convex hull, which parts of the conflict graph G\mathcal{G}G change?
Remove the node of prp_rpr and the nodes of the facets visible from prp_rpr (its neighbors in G\mathcal{G}G ); add nodes for the new facets and find their conflict lists. All other facets keep their conflict lists unchanged.
[Computing Convex Hulls in 3-Space] Inserting prp_rpr into the 3D convex hull, a new triangle is merged with a coplanar old facet f′f'f′ . What is the conflict list of the merged facet?
The conflict list of f′f'f′ , since merging does not change the plane of the facet.
[Computing Convex Hulls in 3-Space] Inserting prp_rpr creates a new triangle fff on horizon edge eee . Old facets f1,f2f_1, f_2f1,f2 were incident to eee in CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) . Where are the points that can see fff found?
Among P(e)=Pconflict(f1)∪Pconflict(f2)P(e) = P_{\text{conflict}}(f_1) \cup P_{\text{conflict}}(f_2)P(e)=Pconflict(f1)∪Pconflict(f2) : test each of these points against fff .
[Computing Convex Hulls in 3-Space] New triangle fff connects prp_rpr to horizon edge eee ; f1,f2f_1, f_2f1,f2 were the facets incident to eee in CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) .Why must every point ptp_tpt that sees fff also see f1f_1f1 or f2f_2f2 ?
ptp_tpt sees fff , so it sees the edge eee ; since CH(Pr−1)⊂CH(Pr)\mathcal{CH}(P_{r-1}) \subset \mathcal{CH}(P_r)CH(Pr−1)⊂CH(Pr) , eee was visible from ptp_tpt before, which needs one of its two facets f1,f2f_1, f_2f1,f2 to be visible.
[Computing Convex Hulls in 3-Space] Algorithm CONVEXHULL (3D): what does the main loop do for a point prp_rpr with Fconflict(pr)≠∅F_{\text{conflict}}(p_r) \neq \emptysetFconflict(pr)=∅ ?
Delete the visible facets, connect prp_rpr to each horizon edge by a triangle, and find the new triangles' conflicts; then update the conflict graph G\mathcal{G}G . In detail: walk the visible region's boundary to list the horizon edges eee in order; for each, create triangle fff ; if fff is coplanar with its neighbor f′f'f′ along eee , merge them (conflicts of f′f'f′ ), else test the points of P(e)=Pconflict(f1)∪Pconflict(f2)P(e) = P_{\text{conflict}}(f_1) \cup P_{\text{conflict}}(f…
[The Analysis] Lemma 11.3. What is the expected number of facets created by the randomized incremental 3D convex hull algorithm on nnn points?
At most 6n−20\boldsymbol{6n - 20}6n−20 . 4+6(n−4)4 + 6(n - 4)4+6(n−4) : the tetrahedron's 4 facets, then at most 6 per inserted point in expectation.
[The Analysis] Inserting prp_rpr into CH(Pr−1)\mathcal{CH}(P_{r-1})CH(Pr−1) creates triangles connecting prp_rpr to its horizon.By backwards analysis, how many facets are created by inserting prp_rpr ?
deg⁡(pr,CH(Pr))\boldsymbol{\deg(p_r, \mathcal{CH}(P_r))}deg(pr,CH(Pr)) : the number of edges incident to prp_rpr in CH(Pr)\mathcal{CH}(P_r)CH(Pr) . Removing prp_rpr from CH(Pr)\mathcal{CH}(P_r)CH(Pr) deletes exactly the facets incident to prp_rpr , the same ones its insertion created.
[The Analysis] Why is E[deg⁡(pr,CH(Pr))]≤6\mathbf{E}[\deg(p_r, \mathcal{CH}(P_r))] \le 6E[deg(pr,CH(Pr))]≤6 in the randomized 3D convex hull algorithm ( p1,…,p4p_1, \dots, p_4p1,…,p4 fixed, p5,…,pnp_5, \dots, p_np5,…,pn in random order)?
Degrees sum to at most 2(3r−6)=6r−122(3r - 6) = 6r - 122(3r−6)=6r−12 ; p1,…,p4p_1, \dots, p_4p1,…,p4 take at least 12; prp_rpr is random among the other r−4r - 4r−4 : 6r−12−12r−4=6\displaystyle\frac{6r - 12 - 12}{r - 4} = 6r−46r−12−12=6 . Each of p1,…,p4p_1, \dots, p_4p1,…,p4 has degree at least 3. They must be subtracted since they are not part of the random permutation.
[The Analysis] Lemma 11.4. What is the expected running time of the randomized incremental algorithm for the convex hull of nnn points in R3\mathbb{R}^3R3 ?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) , expectation over the random permutation.
[The Analysis] 3D convex hull analysis: why is the total expected time for deleting the visible facets Fconflict(pr)F_{\text{conflict}}(p_r)Fconflict(pr) over all stages only O(n)O(n)O(n) ?
Each facet is deleted at most once after being created, and only O(n)O(n)O(n) facets are created in expectation. So E[∑r=5ncard⁡(Fconflict(pr))]=O(n)\mathbf{E}\left[\sum_{r=5}^n \operatorname{card}(F_{\text{conflict}}(p_r))\right] = O(n)E[∑r=5ncard(Fconflict(pr))]=O(n) . Deleting nodes and arcs of the conflict graph is likewise charged to their creation.
[The Analysis] In the 3D convex hull algorithm, each new facet on horizon edge eee gets its conflict list by testing the points of P(e)=Pconflict(f1)∪Pconflict(f2)P(e) = P_{\text{conflict}}(f_1) \cup P_{\text{conflict}}(f_2)P(e)=Pconflict(f1)∪Pconflict(f2) , f1,f2f_1, f_2f1,f2 the old facets at eee .Which quantity determines the running time beyond O(n)O(n)O(n) , and what is its bound?
∑ecard⁡(P(e))\boldsymbol{\sum_e \operatorname{card}(P(e))}∑ecard(P(e)) over all horizon edges ever appearing: O(nlog⁡n)O(n \log n)O(nlogn) expected.
[The Analysis] In the analysis of the 3D convex hull algorithm, what is a flap Δ\DeltaΔ , and what is its defining set?
An ordered 4-tuple (p,q,s,t)(p, q, s, t)(p,q,s,t) of points not all in one plane; defining set D(Δ)={p,q,s,t}D(\Delta) = \{p, q, s, t\}D(Δ)={p,q,s,t} . It is a hull edge pqpqpq with a half-edge attached on each side ( pspsps and qtqtqt ), used instead of plain edges to handle degenerate cases correctly.
[The Analysis] Flap Δ=(p,q,s,t)\Delta = (p, q, s, t)Δ=(p,q,s,t) , ℓ\ellℓ the line through p,qp, qp,q , h(ℓ,x)h(\ell, x)h(ℓ,x) the half-plane bounded by ℓ\ellℓ containing xxx . What is the main region of the killing set K(Δ)K(\Delta)K(Δ) ?
The points outside the closed convex 3D wedge formed by h(ℓ,s)h(\ell, s)h(ℓ,s) and h(ℓ,t)h(\ell, t)h(ℓ,t) . The other parts cover degenerate positions: points inside h(ℓ,s)h(\ell, s)h(ℓ,s) , h(ℓ,t)h(\ell, t)h(ℓ,t) , ℓ\ellℓ or the rays ρ(p,s)\rho(p, s)ρ(p,s) , ρ(q,t)\rho(q, t)ρ(q,t) (from ppp through sss , from qqq through ttt ), but outside the flap's own 2D wedges and segments pq‾\overline{pq}pq , ps‾\overline{ps}ps , qt‾\overline{qt}qt .
[The Analysis] In a configuration space, when is a configuration Δ\DeltaΔ active over a subset SSS , i.e. Δ∈T(S)\Delta \in \mathcal{T}(S)Δ∈T(S) ?
When D(Δ)⊆SD(\Delta) \subseteq SD(Δ)⊆S and K(Δ)∩S=∅K(\Delta) \cap S = \emptysetK(Δ)∩S=∅ : all its defining points are present and none of its killing points.
[The Analysis] Lemma 11.5. When is the flap Δ=(p,q,s,t)\Delta = (p, q, s, t)Δ=(p,q,s,t) active over SSS , i.e. Δ∈T(S)\Delta \in \mathcal{T}(S)Δ∈T(S) ?
Iff pq‾\overline{pq}pq , ps‾\overline{ps}ps , qt‾\overline{qt}qt are edges of CH(S)\mathcal{CH}(S)CH(S) , a facet f1f_1f1 is incident to pq‾\overline{pq}pq and ps‾\overline{ps}ps , and a different facet f2f_2f2 to pq‾\overline{pq}pq and qt‾\overline{qt}qt . Moreover, every point that sees f1f_1f1 or f2f_2f2 lies in K(Δ)K(\Delta)K(Δ) .
[The Analysis] Theorem 9.15: for configurations with defining sets of size at most ddd and RrR_rRr the first rrr objects of a random order, E[∑Δcard⁡(K(Δ))]≤∑r=1nd2(n−rr)(E[card⁡(T(Rr))]r)\mathbf{E}\left[\sum_\Delta \operatorname{card}(K(\Delta))\right] \le \sum_{r=1}^n d^2 \left(\frac{n-r}{r}\right)\left(\frac{\mathbf{E}[\operatorname{card}(\mathcal{T}(R_r))]}{r}\right)E[∑Δcard(K(Δ))]≤∑r=1nd2(rn−r)(rE[card(T(Rr))]) , summed over all Δ\DeltaΔ ever active.How does this prove E[∑ecard⁡(P(e)…
P(e)⊆K(Δ)P(e) \subseteq K(\Delta)P(e)⊆K(Δ) for a flap Δ\DeltaΔ on eee active in T(Pr−1)\mathcal{T}(P_{r-1})T(Pr−1) ; flaps have d=4d = 4d=4 , and card⁡(T(Pr))≤6r−12\operatorname{card}(\mathcal{T}(P_r)) \le 6r - 12card(T(Pr))≤6r−12 . ∑r=1n16(n−rr)(6r−12r)≤96nln⁡n\displaystyle\sum_{r=1}^n 16 \left(\frac{n-r}{r}\right)\left(\frac{6r - 12}{r}\right) \le 96 n \ln nr=1∑n16(rn−r)(r6r−12)≤96nlnn .
[The Analysis] Why is the number of active flaps over PrP_rPr at most 6r−126r - 126r−12 ?
There are two flaps per edge of CH(Pr)\mathcal{CH}(P_r)CH(Pr) , and at most 3r−63r - 63r−6 edges.
[The Analysis] Theorem 11.7. In what time can the convex hull of nnn points in R3\mathbb{R}^3R3 be computed?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) randomized expected time.
[Convex Hulls and Half-Space Intersection] Point-line duality ( p↦p \mapstop↦ line p∗p^*p∗ , line ℓ↦\ell \mapstoℓ↦ point ℓ∗\ell^*ℓ∗ ): which two properties does it preserve?
Incidence: p∈ℓp \in \ellp∈ℓ iff ℓ∗∈p∗\ell^* \in p^*ℓ∗∈p∗ . Order: ppp lies above ℓ\ellℓ iff ℓ∗\ell^*ℓ∗ lies above p∗p^*p∗ .
[Convex Hulls and Half-Space Intersection] What is the upper convex hull UH(P)\mathcal{UH}(P)UH(P) of a planar point set PPP ?
The convex hull edges that have PPP below their supporting line: a polygonal chain from the leftmost to the rightmost point. Assuming no two points have the same xxx -coordinate.
[Convex Hulls and Half-Space Intersection] What is the lower envelope LE(L)\mathcal{LE}(L)LE(L) of a set LLL of non-vertical lines?
The boundary of the bottom cell of the arrangement A(L)\mathcal{A}(L)A(L) , i.e. the graph of the minimum of the linear functions. An xxx -monotone chain; the bottom cell is the intersection of the half-planes below the lines.
[Convex Hulls and Half-Space Intersection] PPP is a planar point set, P∗P^*P∗ its dual lines. What does UH(P)\mathcal{UH}(P)UH(P) (upper convex hull) correspond to in the dual?
The lower envelope LE(P∗)\mathcal{LE}(P^*)LE(P∗) : ppp is a vertex of UH(P)\mathcal{UH}(P)UH(P) iff p∗p^*p∗ contributes an edge to LE(P∗)\mathcal{LE}(P^*)LE(P∗) .
[Convex Hulls and Half-Space Intersection] Why is a point p∈Pp \in Pp∈P a vertex of the upper convex hull UH(P)\mathcal{UH}(P)UH(P) exactly when the dual line p∗p^*p∗ contributes an edge to the lower envelope LE(P∗)\mathcal{LE}(P^*)LE(P∗) ?
ppp is on UH(P)\mathcal{UH}(P)UH(P) iff some non-vertical line ℓ\ellℓ through ppp has all other points below it; dually, the point ℓ∗\ell^*ℓ∗ on p∗p^*p∗ lies below all other lines.
[Convex Hulls and Half-Space Intersection] In which order do the vertices of the upper convex hull UH(P)\mathcal{UH}(P)UH(P) correspond to the edges of the lower envelope LE(P∗)\mathcal{LE}(P^*)LE(P∗) ?
Left-to-right on UH(P)\mathcal{UH}(P)UH(P) is right-to-left on LE(P∗)\mathcal{LE}(P^*)LE(P∗) . The slope of p∗p^*p∗ equals the xxx -coordinate of ppp , and lines appear on the lower envelope in order of decreasing slope.
[Convex Hulls and Half-Space Intersection] When are p,q∈Pp, q \in Pp,q∈P an edge of the upper convex hull UH(P)\mathcal{UH}(P)UH(P) , in dual terms?
Iff p∗∩q∗p^* \cap q^*p∗∩q∗ is a vertex of the lower envelope LE(P∗)\mathcal{LE}(P^*)LE(P∗) . All other points lie below line pqpqpq , i.e. all other dual lines lie above the point (pq)∗=p∗∩q∗(pq)^* = p^* \cap q^*(pq)∗=p∗∩q∗ .
[Convex Hulls and Half-Space Intersection] Under point-line duality, what does the lower convex hull of PPP correspond to?
The upper envelope of P∗P^*P∗ .
[Convex Hulls and Half-Space Intersection] How can the intersection of an arbitrary set HHH of half-planes be computed with convex hull algorithms?
Split HHH into upper half-planes H+H_+H+ and lower ones H−H_-H− ; get ⋂H+\bigcap H_+⋂H+ from the lower hull of H+∗H_+^*H+∗ , ⋂H−\bigcap H_-⋂H− from the upper hull of H−∗H_-^*H−∗ ; intersect. Lower half-planes are bounded from above by a non-vertical line.
[Convex Hulls and Half-Space Intersection] Why does point-line duality turn half-plane intersection into two separate hulls (upper and lower) rather than one full convex hull?
The duality can't handle vertical lines, and near-vertical lines with opposite slopes map to points far apart.
[Convex Hulls and Half-Space Intersection] Why can no general duality in the Euclidean plane turn every half-plane intersection into a convex hull?
A half-plane intersection can be empty, but a convex hull of points never is. Such a duality exists once a point inside the intersection is known (or in oriented projective space).
[Convex Hulls and Half-Space Intersection] What is the algorithmic consequence of convex hulls and half-plane (half-space) intersections being dual concepts?
Intersecting half-planes in the plane, or half-spaces in 3-space, can be done by dualizing a convex hull algorithm.
[Voronoi Diagrams Revisited] For p=(px,py,0)p = (p_x, p_y, 0)p=(px,py,0) and the unit paraboloid U:z=x2+y2\mathcal{U}: z = x^2 + y^2U:z=x2+y2 , what is the plane h(p)h(p)h(p) ?
z=2pxx+2pyy−(px2+py2)\boldsymbol{z = 2 p_x x + 2 p_y y - (p_x^2 + p_y^2)}z=2pxx+2pyy−(px2+py2) : the tangent plane to U\mathcal{U}U at p′=(px,py,px2+py2)p' = (p_x, p_y, p_x^2 + p_y^2)p′=(px,py,px2+py2) .
[Voronoi Diagrams Revisited] U:z=x2+y2\mathcal{U}: z = x^2 + y^2U:z=x2+y2 ; h(p):z=2pxx+2pyy−(px2+py2)h(p): z = 2 p_x x + 2 p_y y - (p_x^2 + p_y^2)h(p):z=2pxx+2pyy−(px2+py2) for p=(px,py,0)p = (p_x, p_y, 0)p=(px,py,0) .For another point q=(qx,qy,0)q = (q_x, q_y, 0)q=(qx,qy,0) , what is the vertical distance from U\mathcal{U}U down to h(p)h(p)h(p) above qqq ?
dist⁡(p,q)2\boldsymbol{\operatorname{dist}(p, q)^2}dist(p,q)2 qx2+qy2−2pxqx−2pyqy+px2+py2=(qx−px)2+(qy−py)2q_x^2 + q_y^2 - 2 p_x q_x - 2 p_y q_y + p_x^2 + p_y^2 = (q_x - p_x)^2 + (q_y - p_y)^2qx2+qy2−2pxqx−2pyqy+px2+py2=(qx−px)2+(qy−py)2 .
[Voronoi Diagrams Revisited] Why is h(p):z=2pxx+2pyy−(px2+py2)h(p): z = 2 p_x x + 2 p_y y - (p_x^2 + p_y^2)h(p):z=2pxx+2pyy−(px2+py2) tangent to the paraboloid z=x2+y2z = x^2 + y^2z=x2+y2 at p′=(px,py,px2+py2)p' = (p_x, p_y, p_x^2 + p_y^2)p′=(px,py,px2+py2) ?
The paraboloid lies dist⁡(p,q)2≥0\operatorname{dist}(p, q)^2 \ge 0dist(p,q)2≥0 above h(p)h(p)h(p) at every qqq , and p′∈h(p)p' \in h(p)p′∈h(p) .
[Voronoi Diagrams Revisited] Theorem 11.8 PPP is a set of points in the plane z=0z = 0z=0 , and H={h(p)∣p∈P}H = \{h(p) \mid p \in P\}H={h(p)∣p∈P} with h(p):z=2pxx+2pyy−(px2+py2)h(p): z = 2 p_x x + 2 p_y y - (p_x^2 + p_y^2)h(p):z=2pxx+2pyy−(px2+py2) . What is the projection of the upper envelope UE(H)\mathcal{UE}(H)UE(H) onto z=0z = 0z=0 ?
The Voronoi diagram of PPP . The facet of UE(H)\mathcal{UE}(H)UE(H) on h(p)h(p)h(p) projects to the Voronoi cell of ppp .
[Voronoi Diagrams Revisited] The vertical line through qqq meets the plane h(r)h(r)h(r) (tangent to z=x2+y2z = x^2 + y^2z=x2+y2 above r∈Pr \in Pr∈P ) at q(r)=(qx,qy,qx2+qy2−dist⁡(q,r)2)q(r) = (q_x, q_y, q_x^2 + q_y^2 - \operatorname{dist}(q, r)^2)q(r)=(qx,qy,qx2+qy2−dist(q,r)2) .Why does the projection of the upper envelope of the planes h(r)h(r)h(r) give the Voronoi diagram of PPP ?
The highest q(r)q(r)q(r) belongs to the point rrr nearest to qqq , so above qqq in the Voronoi cell of ppp the envelope lies on h(p)h(p)h(p) .
[Voronoi Diagrams Revisited] What is the one-dimension-lower version of the correspondence between Voronoi diagrams and upper envelopes?
For points pip_ipi on the line y=0y = 0y=0 , the Voronoi diagram is the projection of the upper envelope of the tangent lines h(pi)h(p_i)h(pi) to the parabola y=x2y = x^2y=x2 .
[Voronoi Diagrams Revisited] How can the 3D convex hull algorithm compute the Voronoi diagram of a planar point set PPP ?
Compute the upper envelope of the planes h(p)h(p)h(p) , p∈Pp \in Pp∈P , via the lower convex hull of their dual points H∗H^*H∗ , and project onto z=0z = 0z=0 . The upper envelope of planes in 3-space corresponds one-to-one to the lower convex hull of the dual points.
[Voronoi Diagrams Revisited] HHH is the set of planes tangent to z=x2+y2z = x^2 + y^2z=x2+y2 above the points of a planar set PPP . What does the projection of the lower convex hull of the dual points H∗H^*H∗ onto z=0z = 0z=0 give?
The Delaunay graph of PPP .
[Notes and Comments] What is the running time of the "gift wrapping" algorithm (Chand and Kapur) for 3D convex hulls with fff facets on nnn points?
O(nf)\boldsymbol{O(nf)}O(nf) , which is O(n2)O(n^2)O(n2) in the worst case. It finds facet after facet by rotating a plane over known hull edges until it hits the first point.
[Notes and Comments] Which algorithm first computed 3D convex hulls in O(nlog⁡n)O(n \log n)O(nlogn) time?
The divide-and-conquer algorithm of Preparata and Hong.
[Notes and Comments] How much storage does the randomized incremental 3D convex hull algorithm with a conflict graph need, as presented in the book?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) space; the original paper of Clarkson and Shor improves it to linear space. The randomized algorithm and the conflict graph are due to Clarkson and Shor; the analysis via configuration spaces is due to Mulmuley.
[Notes and Comments] Upper Bound Theorem. What is the worst-case complexity of the convex hull of nnn points in ddd -dimensional space (equivalently, of the intersection of nnn half-spaces)?
Θ(n⌊d/2⌋)\boldsymbol{\Theta(n^{\lfloor d/2 \rfloor})}Θ(n⌊d/2⌋) The randomized incremental algorithm generalizes to ddd dimensions with expected running time Θ(n⌊d/2⌋)\Theta(n^{\lfloor d/2 \rfloor})Θ(n⌊d/2⌋) , optimal in the worst case.
[Notes and Comments] The Voronoi diagram of points in Rd\mathbb{R}^dRd is the projection of an upper envelope of hyperplanes in Rd+1\mathbb{R}^{d+1}Rd+1 . What does an arbitrary upper envelope of hyperplanes project to?
A power diagram: a generalization of the Voronoi diagram whose sites are spheres instead of points.