Ch.8: Arrangements and Duality

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 8.1. Computing the Discrepancy 8.2. Duality 8.3. Arrangements of Lines 8.4. Levels and Discrepancy 8.5. Notes and Comments

66 flashcards · Mathematics · by lakesare

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

[Arrangements and Duality] In ray tracing, how is the object visible at a pixel determined?
Shoot a ray from the view point through the pixel; the first object the ray hits is the visible one. Afterwards the intensity of light that object emits towards the view point is computed (light source, reflections).
[Arrangements and Duality] With one ray through each pixel center, what goes wrong near the edges of objects, and what is the visible result?
A pixel is an area, not a point: an object covering 49% of the pixel is missed, one covering 51% counts as covering all of it. This gives jaggies. Better would be a pixel intensity of, say, 0.49 times the object intensity.
[Arrangements and Duality] What is supersampling?
Shooting many rays (sample points) per pixel, and taking the fraction of rays that hit an object as the fraction of the pixel it covers. e.g. 100 rays, 35 hit: the object is visible in about 35% of the pixel area.
[Arrangements and Duality] Supersampling: why not place the sample points of a pixel in a regular grid (e.g. 10 by 10)?
The errors become regular across rows and columns of pixels, and the human visual system notices that regularity as artifacts. So the sample points are chosen somewhat randomly, but still such that the fraction of hits is close to the covered fraction of the pixel area.
[Arrangements and Duality] For a set of sample points in a pixel, what is its discrepancy with respect to an object, and what is the discrepancy of the sample set?
w.r.t. an object: |fraction of hits −-− fraction of the pixel area covered|. Of the set: the maximum of this over all objects of a given class. The worst case is taken because it is unknown in advance which objects will be visible in the pixel.
[Arrangements and Duality] How does supersampling use an algorithm computing the discrepancy of a point set?
Generate a random sample set; keep it if its discrepancy is low, otherwise generate a new one.
[Computing the Discrepancy] Ray tracing with supersampling: why is it enough to consider the discrepancy with respect to half-planes?
Scene objects project to polygons, and most pixels are crossed by at most one polygon edge, so inside a pixel a polygon behaves like a half-plane. Pixels crossed by several edges are much rarer, and they don't cause regularity in the error (the source of the annoying artifacts).
[Computing the Discrepancy] U=[0:1]×[0:1]U = [0:1] \times [0:1]U=[0:1]×[0:1] is the unit square and SSS a set of nnn sample points in UUU . For a closed half-plane hhh , what are the continuous measure μ(h)\mu(h)μ(h) and the discrete measure μS(h)\mu_S(h)μS(h) ?
μ(h)=\mu(h) = μ(h)= area of h∩Uh \cap Uh∩U ; μS(h)=\ \mu_S(h) = μS(h)= fraction of the points of SSS in hhh , i.e. card⁡(S∩h)/card⁡(S)\operatorname{card}(S \cap h)/\operatorname{card}(S)card(S∩h)/card(S) . UUU models a pixel. A half-plane covering UUU has μ(h)=1\mu(h) = 1μ(h)=1 .
[Computing the Discrepancy] UUU is the unit square, SSS a set of sample points in UUU , and hhh a closed half-plane. What is the discrepancy ΔS(h)\Delta_S(h)ΔS(h) of hhh with respect to SSS ?
ΔS(h)=∣μ(h)−μS(h)∣\boldsymbol{\Delta_S(h) = |\mu(h) - \mu_S(h)|}ΔS(h)=∣μ(h)−μS(h)∣ μ(h)\mu(h)μ(h) = area of h∩Uh \cap Uh∩U (continuous measure), μS(h)\mu_S(h)μS(h) = fraction of SSS inside hhh (discrete measure).
[Computing the Discrepancy] UUU is the unit square with 10 sample points. A half-plane hhh covers a quarter of the area of UUU and contains 3 of the points. What is the discrepancy of hhh ?
∣0.25−0.3∣=0.05\boldsymbol{|0.25 - 0.3| = 0.05}∣0.25−0.3∣=0.05 Discrepancy = |area of h∩Uh \cap Uh∩U −-− fraction of the points in hhh |.
[Computing the Discrepancy] H\mathcal{H}H is the set of all closed half-planes and SSS a set of points in the unit square UUU . What is the half-plane discrepancy ΔH(S)\Delta_{\mathcal{H}}(S)ΔH(S) ?
ΔH(S)=sup⁡h∈HΔS(h)\boldsymbol{\Delta_{\mathcal{H}}(S) = \sup_{h \in \mathcal{H}} \Delta_S(h)}ΔH(S)=suph∈HΔS(h) where ΔS(h)=∣μ(h)−μS(h)∣\Delta_S(h) = |\mu(h) - \mu_S(h)|ΔS(h)=∣μ(h)−μS(h)∣ = |area of h∩Uh \cap Uh∩U −-− fraction of SSS in hhh |.
[Computing the Discrepancy] To compute the half-plane discrepancy sup⁡hΔS(h)\sup_h \Delta_S(h)suphΔS(h) of a point set SSS (a sup over infinitely many half-planes), which finite set of candidate half-planes is used?
The half-planes with locally maximal discrepancy: translating or rotating them slightly decreases their discrepancy. The global maximum is one of them.
[Computing the Discrepancy] SSS is a set of points in the unit square UUU . Why does a half-plane of maximum discrepancy ∣μ(h)−μS(h)∣|\mu(h) - \mu_S(h)|∣μ(h)−μS(h)∣ always have a point of SSS on its boundary?
Otherwise a slight translation changes the area μ(h)\mu(h)μ(h) while the fraction μS(h)\mu_S(h)μS(h) of points stays the same, and one of the two directions increases the discrepancy.
[Computing the Discrepancy] SSS is a set of points in the unit square UUU , and hhh a half-plane with exactly one point p∈Sp \in Sp∈S on its boundary. Why can rotating hhh around ppp fail to increase the discrepancy ∣μ(h)−μS(h)∣|\mu(h) - \mu_S(h)|∣μ(h)−μS(h)∣ ?
hhh can be at a local extremum of the area μ(h)\mu(h)μ(h) as a function of the angle. At a local maximum with μS(h)<μ(h)\mu_S(h) < \mu(h)μS(h)<μ(h) , every slight rotation lowers μ(h)\mu(h)μ(h) and so the discrepancy (likewise at a local minimum with μS(h)>μ(h)\mu_S(h) > \mu(h)μS(h)>μ(h) ). So a maximum-discrepancy half-plane need not have two points of SSS on its boundary.
[Computing the Discrepancy] p∈Sp \in Sp∈S lies in the unit square UUU , and hp(ϕ)h_p(\phi)hp(ϕ) is the half-plane above the line ℓp(ϕ)\ell_p(\phi)ℓp(ϕ) through ppp at angle ϕ\phiϕ with the xxx -axis. Why does ϕ↦μ(hp(ϕ))\phi \mapsto \mu(h_p(\phi))ϕ↦μ(hp(ϕ)) (the area of hp(ϕ)∩Uh_p(\phi) \cap Uhp(ϕ)∩U ) have only O(1)O(1)O(1) local extrema?
It changes form only when ℓp(ϕ)\ell_p(\phi)ℓp(ϕ) passes a vertex of UUU (at most 8 times), and each piece has at most two local extrema. e.g. while ℓp(ϕ)\ell_p(\phi)ℓp(ϕ) crosses the top and left sides of UUU : μ(hp(ϕ))=12(1−py+pxtan⁡ϕ)(px+1−pytan⁡ϕ)\mu(h_p(\phi)) = \frac{1}{2}(1 - p_y + p_x \tan\phi)(p_x + \frac{1 - p_y}{\tan\phi})μ(hp(ϕ))=21(1−py+pxtanϕ)(px+tanϕ1−py) . The extrema can be found in O(1)O(1)O(1) time per point.
[Computing the Discrepancy] Lemma 8.1 Let SSS be a set of nnn points in the unit square UUU . A half-plane hhh that achieves the maximum discrepancy with respect to SSS is of one of which two types?
(i) hhh has exactly one point of SSS on its boundary; (ii) hhh has two or more points of SSS on its boundary. There are O(n)O(n)O(n) candidates of type (i), and they can be found in O(n)O(n)O(n) time.
[Computing the Discrepancy] Computing the half-plane discrepancy of nnn points SSS : how are the O(n)O(n)O(n) candidate half-planes with exactly one point of SSS on their boundary handled, and in what time?
Brute force: area μ(h)\mu(h)μ(h) in O(1)O(1)O(1) , fraction of points μS(h)\mu_S(h)μS(h) in O(n)O(n)O(n) per candidate, so O(n2)O(n^2)O(n2) in total.
[Computing the Discrepancy] Computing the half-plane discrepancy of nnn points SSS : why can't the candidates with two or more points of SSS on their boundary be handled by brute force?
There are Θ(n2)\Theta(n^2)Θ(n2) of them (one per line through two points), and counting the points in each takes O(n)O(n)O(n) , which gives O(n3)O(n^3)O(n3) . Instead, duality and arrangements give all their discrete measures in O(n2)O(n^2)O(n2) time in total.
[Computing the Discrepancy] Theorem 8.2. In what time can the half-plane discrepancy of a set SSS of nnn points in the unit square be computed?
O(n2)\boldsymbol{O(n^2)}O(n2) O(n2)O(n^2)O(n2) for the O(n)O(n)O(n) half-planes with one point of SSS on their boundary, and O(n2)O(n^2)O(n2) for all discrete measures of half-planes bounded by lines through two points (via levels in the dual arrangement).
[Duality] Why can points in the plane be mapped one-to-one to non-vertical lines?
Both have two parameters: a point its xxx - and yyy -coordinate, a line its slope and its intersection with the yyy -axis. Such a mapping is a duality transform; the image of an object is its dual.
[Duality] What is the dual p∗p^*p∗ of a point p=(px,py)p = (p_x, p_y)p=(px,py) , and the dual ℓ∗\ell^*ℓ∗ of a line ℓ:y=mx+b\ell : y = mx + bℓ:y=mx+b ?
p∗:y=pxx−py\boldsymbol{p^* : y = p_x x - p_y}p∗:y=pxx−py and ℓ∗=(m,−b)\boldsymbol{\ell^* = (m, -b)}ℓ∗=(m,−b) ℓ∗\ell^*ℓ∗ is the point whose dual is ℓ\ellℓ . The transform maps the primal plane to the dual plane.
[Duality] For which lines is the duality transform ℓ:y=mx+b ↦ ℓ∗=(m,−b)\ell : y = mx + b \ \mapsto \ \ell^* = (m, -b)ℓ:y=mx+b ↦ ℓ∗=(m,−b) not defined, and how is that dealt with?
Vertical lines. Handle them separately, or rotate the scene so that there are none.
[Duality] Observation 8.3. Which two properties does the duality transform p=(px,py)↦p∗:y=pxx−pyp = (p_x, p_y) \mapsto p^* : y = p_x x - p_yp=(px,py)↦p∗:y=pxx−py , ℓ:y=mx+b↦ℓ∗=(m,−b)\ \ell : y = mx + b \mapsto \ell^* = (m, -b) ℓ:y=mx+b↦ℓ∗=(m,−b) have, for a point ppp and a non-vertical line ℓ\ellℓ ?
Incidence preserving: p∈ℓ ⟺ ℓ∗∈p∗p \in \ell \iff \ell^* \in p^*p∈ℓ⟺ℓ∗∈p∗ . Order preserving: ppp lies above ℓ ⟺ ℓ∗\ell \iff \ell^*ℓ⟺ℓ∗ lies above p∗p^*p∗ . p1,p2,p3p_1, p_2, p_3p1,p2,p3 on ℓ\ellℓ become lines p1∗,p2∗,p3∗p_1^*, p_2^*, p_3^*p1∗,p2∗,p3∗ through ℓ∗\ell^*ℓ∗ ; p4p_4p4 above ℓ\ellℓ becomes a line p4∗p_4^*p4∗ below ℓ∗\ell^*ℓ∗ .
[Duality] Duality: (px,py)∗:y=pxx−py(p_x, p_y)^* : y = p_x x - p_y(px,py)∗:y=pxx−py and (y=mx+b)∗=(m,−b)(y = mx + b)^* = (m, -b)(y=mx+b)∗=(m,−b) .What is the dual of the point (2,3)(2, 3)(2,3) ? Does the point (1,1)(1, 1)(1,1) lie on the line y=2x−1y = 2x - 1y=2x−1 , and what does that give in the dual plane?
y=2x−3\boldsymbol{y = 2x - 3}y=2x−3 . Yes, so the dual point (2,1)(2, 1)(2,1) lies on the dual line y=x−1y = x - 1y=x−1 . Check: 1=2−11 = 2 - 11=2−1 . Incidence is preserved.
[Duality] What is the dual s∗s^*s∗ of a line segment s=pq‾s = \overline{pq}s=pq (the union of the duals of its points)?
The left-right double wedge bounded by the lines p∗p^*p∗ and q∗q^*q∗ . All points of sss lie on one line, so their dual lines all pass through one point (the dual of the line containing sss ). p∗p^*p∗ and q∗q^*q∗ define two double wedges: a left-right one and a top-bottom one.
[Duality] s=pq‾s = \overline{pq}s=pq is a segment, and its dual s∗s^*s∗ is the left-right double wedge bounded by p∗p^*p∗ and q∗q^*q∗ . Why does every line ℓ\ellℓ intersecting sss have its dual point ℓ∗\ell^*ℓ∗ in s∗s^*s∗ ?
ℓ\ellℓ has one of p,qp, qp,q above it and the other below it, so by order preservation ℓ∗\ell^*ℓ∗ lies above one of p∗,q∗p^*, q^*p∗,q∗ and below the other.
[Duality] U\mathcal{U}U is the parabola y=x2/2y = x^2/2y=x2/2 . For a point p∈Up \in \mathcal{U}p∈U , what is its dual line p∗:y=pxx−pyp^* : y = p_x x - p_yp∗:y=pxx−py geometrically?
The tangent line of U\mathcal{U}U at ppp . The derivative of U\mathcal{U}U at ppp is pxp_xpx , the slope of p∗p^*p∗ , and the tangent meets the yyy -axis at (0,−px2/2)=(0,−py)(0, -p_x^2/2) = (0, -p_y)(0,−px2/2)=(0,−py) .
[Duality] U\mathcal{U}U is the parabola y=x2/2y = x^2/2y=x2/2 , and qqq a point not on U\mathcal{U}U . How can its dual line q∗q^*q∗ be found geometrically?
The line through q′q'q′ parallel to the tangent of U\mathcal{U}U at ppp , where p∈Up \in \mathcal{U}p∈U has the same xxx -coordinate as qqq , and q′q'q′ is qqq mirrored in ppp . Points with the same xxx -coordinate have parallel duals, and the vertical distance between the duals equals the difference of the points' yyy -coordinates.
[Duality] A problem in the dual plane can be solved by mimicking its solution in the primal plane. What then is the advantage of dualizing?
A new perspective: looking at the problem from a different angle can give the insight needed to solve it. In particular, a point set becomes an arrangement of lines, whose structure is more explicit.
[Duality] SSS is a set of points and S∗S^*S∗ the set of their dual lines. For p,q∈Sp, q \in Sp,q∈S , what does the number of points of SSS strictly below the line ℓ(p,q)\ell(p, q)ℓ(p,q) through ppp and qqq correspond to in the dual plane?
The number of lines of S∗S^*S∗ strictly above the point ℓ(p,q)∗=p∗∩q∗\ell(p, q)^* = p^* \cap q^*ℓ(p,q)∗=p∗∩q∗ . For the closed half-plane, also count the lines through ℓ(p,q)∗\ell(p, q)^*ℓ(p,q)∗ ; for the half-plane above ℓ(p,q)\ell(p, q)ℓ(p,q) , count the lines below ℓ(p,q)∗\ell(p, q)^*ℓ(p,q)∗ .
[Duality] Computing discrete measures of half-planes bounded by lines through two points of SSS via the dual lines S∗S^*S∗ : which such lines don't appear as vertices p∗∩q∗p^* \cap q^*p∗∩q∗ in the dual, and how are they handled?
Vertical lines through two or more points of SSS ; there are only O(n)O(n)O(n) of them, so brute force, O(n2)O(n^2)O(n2) in total. Points with the same xxx -coordinate have parallel dual lines, which don't intersect.
[Arrangements of Lines] What is the arrangement A(L)\mathcal{A}(L)A(L) of a set LLL of lines in the plane?
The subdivision of the plane induced by LLL into vertices, edges and faces (some edges and faces unbounded).
[Arrangements of Lines] An arrangement of lines in which no three lines pass through one point and no two lines are parallel is called simple.
A simple arrangement attains the maximum numbers of vertices, edges and faces.
[Arrangements of Lines] What is the (combinatorial) complexity of an arrangement?
The total number of its vertices, edges and faces.
[Arrangements of Lines] Theorem 8.4. For an arrangement A(L)\mathcal{A}(L)A(L) of nnn lines, what are the upper bounds on the number of vertices, edges and faces, and when are they attained?
Vertices ≤n(n−1)/2\le n(n-1)/2≤n(n−1)/2 , edges ≤n2\le n^2≤n2 , faces ≤n2/2+n/2+1\le n^2/2 + n/2 + 1≤n2/2+n/2+1 ; equality in all three if and only if A(L)\mathcal{A}(L)A(L) is simple. Vertices: every pair of lines meets at most once.
[Arrangements of Lines] Why does an arrangement of nnn lines have at most n2n^2n2 edges?
Each line carries at most n−1n - 1n−1 vertices, hence at most nnn edges. The edges on a line are one more than the vertices on it.
[Arrangements of Lines] Why does an arrangement of nnn lines ℓ1,…,ℓn\ell_1, \dots, \ell_nℓ1,…,ℓn have at most n2/2+n/2+1n^2/2 + n/2 + 1n2/2+n/2+1 faces?
Add the lines one by one: each edge on ℓi\ell_iℓi splits a face in two, and ℓi\ell_iℓi carries at most iii edges. So at most 1+∑i=1ni1 + \sum_{i=1}^n i1+∑i=1ni faces. 1+n(n+1)2=n2/2+n/2+11 + \frac{n(n+1)}{2} = n^2/2 + n/2 + 11+2n(n+1)=n2/2+n/2+1 .
[Arrangements of Lines] A simple arrangement of 4 lines: how many vertices, edges and faces?
6 vertices, 16 edges, 11 faces. n(n−1)/2=6n(n-1)/2 = 6n(n−1)/2=6 , n2=16n^2 = 16n2=16 , n2/2+n/2+1=11n^2/2 + n/2 + 1 = 11n2/2+n/2+1=11 .
[Arrangements of Lines] Why is a line arrangement A(L)\mathcal{A}(L)A(L) stored in a doubly-connected edge list together with a bounding box B(L)\mathcal{B}(L)B(L) , and which bounding box?
A doubly-connected edge list stores only bounded edges. So take a box B(L)\mathcal{B}(L)B(L) containing all vertices of A(L)\mathcal{A}(L)A(L) in its interior, and store the subdivision induced by B(L)\mathcal{B}(L)B(L) and the part of A(L)\mathcal{A}(L)A(L) inside it.
[Arrangements of Lines] How is a bounding box B(L)\mathcal{B}(L)B(L) containing all vertices of the arrangement of nnn lines LLL computed, and in what time?
The axis-parallel rectangle through the leftmost, rightmost, bottom and top intersection point of two lines: O(n2)\boldsymbol{O(n^2)}O(n2) . Compute all O(n2)O(n^2)O(n2) intersection points of pairs of lines.
[Arrangements of Lines] Constructing the doubly-connected edge list of the arrangement of nnn lines by adapting the plane sweep for line segment intersection: what running time, and is that optimal?
O(n2log⁡n)\boldsymbol{O(n^2 \log n)}O(n2logn) , not optimal: there are Θ(n2)\Theta(n^2)Θ(n2) intersection points, and O(n2)O(n^2)O(n2) is possible.
[Arrangements of Lines] What does the incremental algorithm for constructing the arrangement of lines ℓ1,…,ℓn\ell_1, \dots, \ell_nℓ1,…,ℓn (inside a bounding box B(L)\mathcal{B}(L)B(L) ) do in step iii ?
Walk along ℓi\ell_iℓi from left to right through the current subdivision, splitting every face that ℓi\ell_iℓi intersects. The current subdivision Ai−1\mathcal{A}_{i-1}Ai−1 is induced by B(L)\mathcal{B}(L)B(L) and the part of the arrangement of ℓ1,…,ℓi−1\ell_1, \dots, \ell_{i-1}ℓ1,…,ℓi−1 inside B(L)\mathcal{B}(L)B(L) , stored as a doubly-connected edge list.
[Arrangements of Lines] Incremental arrangement construction: the walk along the new line ℓi\ell_iℓi entered a face fff through an edge eee . How is the next face intersected by ℓi\ell_iℓi found?
Follow Next()\mathit{Next}()Next() pointers along the boundary of fff until the half-edge of the edge e′e'e′ where ℓi\ell_iℓi leaves fff ; its Twin()\mathit{Twin}()Twin() is in the next face. Time proportional to the complexity of fff . If ℓi\ell_iℓi leaves fff through a vertex vvv , walk around vvv instead, in time proportional to the degree of vvv .
[Arrangements of Lines] Incremental arrangement construction inside a bounding box B(L)\mathcal{B}(L)B(L) : how is the first face split by the new line ℓi\ell_iℓi found, and in what time?
The leftmost intersection of ℓi\ell_iℓi with the current subdivision lies on an edge of B(L)\mathcal{B}(L)B(L) ; test every edge on B(L)\mathcal{B}(L)B(L) . At most 2i+22i + 22i+2 such edges: O(n)\boldsymbol{O(n)}O(n) per line. The face inside B(L)\mathcal{B}(L)B(L) incident to that edge is the first face. If the intersection is a corner of B(L)\mathcal{B}(L)B(L) , it is the unique face at that corner; a vertical ℓi\ell_iℓi starts at its bottom intersection point.
[Arrangements of Lines] Incremental arrangement construction: how is a face fff split by the new line ℓi\ell_iℓi in the doubly-connected edge list ( ℓi\ell_iℓi leaves fff through the edge e′e'e′ )?
New faces for the parts above and below ℓi\ell_iℓi , a new vertex ℓi∩e′\ell_i \cap e'ℓi∩e′ splitting e′e'e′ , half-edges for ℓi∩f\ell_i \cap fℓi∩f ; fix pointers, destroy fff and e′e'e′ . If ℓi\ell_iℓi leaves fff through a vertex, no edge is split. Time linear in the complexity of fff .
[Arrangements of Lines] Incremental arrangement construction for a simple arrangement: the time to insert a line ℓi\ell_iℓi is linear in what?
The sum of the complexities of the faces intersected by ℓi\ell_iℓi . If the arrangement is not simple, the walk around a vertex also visits edges of faces whose closure is intersected by ℓi\ell_iℓi . This leads to zones.
[Arrangements of Lines] What is the zone of a line ℓ\ellℓ in an arrangement A(L)\mathcal{A}(L)A(L) , and what is its complexity?
Zone: the faces of A(L)\mathcal{A}(L)A(L) whose closure intersects ℓ\ellℓ . Complexity: the sum of the numbers of edges and vertices of these faces. A zone of nine faces. A vertex can be counted once, twice, three or even four times.
[Arrangements of Lines] Zone Theorem (Theorem 8.5). What is the complexity of the zone of a line in an arrangement of mmm lines?
O(m)\boldsymbol{O(m)}O(m) The proof shows at most 5m5m5m left bounding edges and 5m5m5m right bounding edges.
[Arrangements of Lines] Zone Theorem proof: what are left bounding and right bounding edges of a face?
An edge is a left bounding edge of the face to its right and a right bounding edge of the face to its left. So each edge bounds two faces, once in each role. The proof shows that the faces of the zone of ℓ\ellℓ in an arrangement of mmm lines have at most 5m5m5m left bounding edges; by symmetry, also at most 5m5m5m right bounding edges.
[Arrangements of Lines] Zone Theorem proof setup: LLL is a set of mmm lines, ℓ\ellℓ is the xxx -axis, no line of LLL is horizontal. Claim: the zone of ℓ\ellℓ has at most 5m5m5m left bounding edges (edges with the zone face to their right).How does the induction on mmm proceed, and which line is removed?
Remove the line ℓ1\ell_1ℓ1 with the rightmost intersection with ℓ\ellℓ , use induction, and show that adding ℓ1\ell_1ℓ1 back adds at most 3 left bounding edges. By induction the zone of ℓ\ellℓ in A(L∖{ℓ1})\mathcal{A}(L \setminus \{\ell_1\})A(L∖{ℓ1}) has at most 5(m−1)5(m-1)5(m−1) , and 5(m−1)+3<5m5(m-1) + 3 < 5m5(m−1)+3<5m . If several lines pass through the rightmost intersection point, pick any of them as ℓ1\ell_1ℓ1 : the increase is at most 5, and 5(m−1)+5=5m5(m-1) + 5 = 5m5(m−1)+5=5m .
[Arrangements of Lines] Zone Theorem proof: ℓ\ellℓ is the xxx -axis, and ℓ1∈L\ell_1 \in Lℓ1∈L is the line with the (unique) rightmost intersection with ℓ\ellℓ . vvv is the first intersection of ℓ1\ell_1ℓ1 with another line above ℓ\ellℓ , and www the first one below ℓ\ellℓ .Which 3 new left bounding edges of the zone of ℓ\ellℓ can adding ℓ1\ell_1ℓ1 create?
The edge vwvwvw on ℓ1\ell_1ℓ1 , plus one extra from splitting a left bounding edge at vvv and one at www . If vvv or www doesn't exist, the increase is even smaller.
[Arrangements of Lines] Zone Theorem proof: ℓ\ellℓ is the xxx -axis, and ℓ1\ell_1ℓ1 is the line with the rightmost intersection with ℓ\ellℓ . vvv is the first intersection of ℓ1\ell_1ℓ1 with another line ℓ2\ell_2ℓ2 above ℓ\ellℓ .Why does the part of ℓ1\ell_1ℓ1 above vvv add no left bounding edges to the zone of ℓ\ellℓ ?
The region above vvv between ℓ1\ell_1ℓ1 and ℓ2\ell_2ℓ2 is not in the zone, and it lies to the right of ℓ1\ell_1ℓ1 (because ℓ2\ell_2ℓ2 crosses ℓ1\ell_1ℓ1 from left to right at vvv ). And a left bounding edge that ℓ1\ell_1ℓ1 cuts above vvv loses its part right of ℓ1\ell_1ℓ1 from the zone, so the count doesn't grow. The part below www is symmetric.
[Arrangements of Lines] Zone Theorem proof: how are horizontal lines of LLL (the line ℓ\ellℓ being the xxx -axis) handled?
Other horizontal lines: rotate slightly (only increases the zone). A line ℓi\ell_iℓi equal to ℓ\ellℓ : adds at most 4m−24m - 24m−2 edges to the ≤10m−10\le 10m - 10≤10m−10 without it. At most mmm edges on ℓi\ell_iℓi for the faces above, mmm for the faces below, and at most m−1m - 1m−1 edges split in two, each counted as left and as right bounding edge.
[Arrangements of Lines] Why does the incremental algorithm construct the arrangement of nnn lines in O(n2)O(n^2)O(n2) time?
Inserting ℓi\ell_iℓi takes time linear in the complexity of the zone of ℓi\ell_iℓi in the arrangement of ℓ1,…,ℓi−1\ell_1, \dots, \ell_{i-1}ℓ1,…,ℓi−1 , which is O(i)O(i)O(i) by the Zone Theorem; ∑i=1nO(i)=O(n2)\sum_{i=1}^n O(i) = O(n^2)∑i=1nO(i)=O(n2) . Plus O(n2)O(n^2)O(n2) for the bounding box and O(n)O(n)O(n) per line to find its first face.
[Arrangements of Lines] Theorem 8.6. In what time can a doubly-connected edge list for the arrangement of nnn lines in the plane be constructed, and why is that optimal?
O(n2)\boldsymbol{O(n^2)}O(n2) ; optimal because a simple arrangement has complexity Θ(n2)\Theta(n^2)Θ(n2) . By the incremental algorithm, using the Zone Theorem.
[Levels and Discrepancy] What is the level of a point in an arrangement of lines?
The number of lines strictly above the point.
[Levels and Discrepancy] Half-plane discrepancy of nnn points SSS : what must be computed for every vertex of the arrangement A(S∗)\mathcal{A}(S^*)A(S∗) of the dual lines, and why are two of those numbers enough?
The number of lines above, through and below the vertex; the three add up to nnn . The number through each vertex is known from the doubly-connected edge list, so it remains to compute the levels.
[Levels and Discrepancy] How are the levels of all vertices of an arrangement of nnn lines computed, and in what time?
Per line ℓ\ellℓ : level of its leftmost vertex by brute force, then walk right along ℓ\ellℓ updating the level at each vertex: O(n2)\boldsymbol{O(n^2)}O(n2) in total. O(n)O(n)O(n) per line; the update at a vertex inspects its incident edges (doubly-connected edge list). The level along ℓ\ellℓ only changes at vertices.
[Levels and Discrepancy] Walking right along a line ℓ\ellℓ to compute levels (= number of lines strictly above): at a vertex, a line crosses ℓ\ellℓ coming from above. What is the level of the vertex and after it, compared to before?
Both one lower: the crossing line is no longer strictly above, neither at the vertex nor after it. A line crossing from below instead: the vertex keeps the old level, and the level increases by one after the vertex.
[Levels and Discrepancy] Computing levels in the arrangement A(S∗)\mathcal{A}(S^*)A(S∗) of dual lines: why are vertical lines no problem here?
S∗S^*S∗ consists of duals of points, which are never vertical.
[Levels and Discrepancy] How do the levels in the dual arrangement finish the O(n2)O(n^2)O(n2) half-plane discrepancy algorithm for nnn points SSS ?
The lines above, through and below each vertex p∗∩q∗p^* \cap q^*p∗∩q∗ count the points of SSS below, on and above the line through p,qp, qp,q . So all discrete measures of half-planes bounded by lines through two points of SSS take O(n2)O(n^2)O(n2) in total.A point strictly below the line through p,qp, qp,q dualizes to a line strictly above p∗∩q∗p^* \cap q^*p∗∩q∗ .
[Notes and Comments] U\mathcal{U}U is the parabola y=x2/2y = x^2/2y=x2/2 and qqq a point below U\mathcal{U}U . How can its dual line q∗q^*q∗ be constructed without measuring distances?
Draw the two tangents of U\mathcal{U}U through qqq ; q∗q^*q∗ is the line through their two points of tangency. qqq lies on both tangents, so q∗q^*q∗ passes through their duals, which are the points of tangency.
[Notes and Comments] What does the lifting (inversion) transform p=(px,py)↦p∘=(px,py,px2+py2)p = (p_x, p_y) \mapsto p^\circ = (p_x, p_y, p_x^2 + p_y^2)p=(px,py)↦p∘=(px,py,px2+py2) turn the relation "point ppp inside circle CCC " into?
p∘p^\circp∘ lies below the plane C∘C^\circC∘ through the lifted circle. For C:(x−a)2+(y−b)2=r2C : (x-a)^2 + (y-b)^2 = r^2C:(x−a)2+(y−b)2=r2 : C∘:z=a(x−a)+b(y−b)+r2\ C^\circ : z = a(x-a) + b(y-b) + r^2 C∘:z=a(x−a)+b(y−b)+r2 . Points are lifted to the paraboloid z=x2+y2z = x^2 + y^2z=x2+y2 .
[Notes and Comments] What are the worst-case complexity of an arrangement of nnn hyperplanes in Rd\mathbb{R}^dRd , and of the zone of a hyperplane in it?
Arrangement Θ(nd)\Theta(n^d)Θ(nd) , zone O(nd−1)O(n^{d-1})O(nd−1) . The higher-dimensional Zone Theorem makes incremental construction optimal there too.
[Notes and Comments] What is a kkk -set of nnn points in the plane, and what are the best known bounds (as of the book) on the maximum number of kkk -sets?
A subset of kkk points that a line separates from the other n−kn - kn−k . Bounds: Ω(nlog⁡(k+1))\boldsymbol{\Omega(n \log(k+1))}Ω(nlog(k+1)) (Erdős et al., 1973) and O(nk1/3)\boldsymbol{O(n k^{1/3})}O(nk1/3) (Dey, 1997). Dually the same bounds hold for the complexity of kkk -levels. For (≤k)(\le k)(≤k) -sets the maximum is known exactly: Θ(nk)\Theta(nk)Θ(nk) in the plane.
[Notes and Comments] What is the maximum complexity of a single face in an arrangement of nnn line segments?
Θ(nα(n))\boldsymbol{\Theta(n \alpha(n))}Θ(nα(n)) , slightly superlinear ( α\alphaα = inverse Ackermann function). Faces can be non-convex, so a segment can appear several times on the boundary. The upper bound uses Davenport-Schinzel sequences.