Ch.4: Linear Programming
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 4.1. The Geometry of Casting 4.2. Half-Plane Intersection 4.3. Incremental Linear Programming 4.4. Randomized Linear Programming 4.5. Unbounded Linear Programs 4.6. Linear Programming in Higher Dimensions 4.7. Smallest Enclosing Discs 4.8. Notes and Comments
110 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Linear Programming] Which manufacturing question motivates the chapter on linear programming?
Casting: given an object, is there a mold from which the object can be removed? Liquid metal is poured into a mold, solidifies, and the object is taken out. The last step can fail: the object can be stuck in the mold.
[Linear Programming] Which three restrictions does the casting problem in the book make?
The object is polyhedral, the mold is one piece, and the object is removed by a single translation. A sphere has no one-piece mold (a two-piece mold works); a screw can't be removed by a translation.
[The Geometry of Casting] In the casting problem, what is the top facet of the polyhedron P\mathcal{P}P , and how many potential molds does P\mathcal{P}P have?
The horizontal facet that is not in contact with the mold; there is one potential mold per facet of P\mathcal{P}P . Each facet can be chosen as the top facet, and each orientation gives a different mold. The top facet is coplanar with the topmost facet of the mold, which is parallel to the xyxyxy -plane.
[The Geometry of Casting] When is a polyhedron castable?
It can be removed from its mold for at least one choice of the top facet. The same object in two orientations: stuck in one mold, removable from the other.
[The Geometry of Casting] A facet of the polyhedron P\mathcal{P}P that is not the top facet is called an ordinary facet.
Every ordinary facet fff has a corresponding facet f^\hat ff^ in the mold.
[The Geometry of Casting] P\mathcal{P}P sits in its mold with its top facet parallel to the xyxyxy -plane. Which removal directions d⃗\vec dd can be ruled out at once?
Those without a positive zzz -component: d⃗\vec dd must point upward. The top facet is the only facet not touching the mold. This condition is necessary, not sufficient. (Sliding along the mold is allowed.)
[The Geometry of Casting] Lemma 4.1 The polyhedron P\mathcal{P}P can be removed from its mold by a translation in direction d⃗\vec dd if and only if … ?
d⃗\vec dd makes an angle of at least 90∘90^\circ90∘ with the outward normal of every ordinary facet of P\mathcal{P}P . The angle of two vectors (rooted at the origin) is the smaller of the two angles in the plane they span.
[The Geometry of Casting] P\mathcal{P}P can be removed from its mold by a translation in direction d⃗\vec dd iff d⃗\vec dd makes an angle ≥90∘\ge 90^\circ≥90∘ with the outward normal η⃗(f)\vec\eta(f)η(f) of every ordinary facet fff .Why is the condition necessary?
If d⃗\vec dd made an angle below 90∘90^\circ90∘ with some η⃗(f)\vec\eta(f)η(f) , every point in the interior of fff would collide with the mold facet f^\hat ff^ . The mold facet f^\hat ff^ blocks any translation making an angle less than 90∘90^\circ90∘ with η⃗(f)\vec\eta(f)η(f) .
[The Geometry of Casting] P\mathcal{P}P can be removed from its mold by a translation in direction d⃗\vec dd iff d⃗\vec dd makes an angle ≥90∘\ge 90^\circ≥90∘ with the outward normal η⃗(f)\vec\eta(f)η(f) of every ordinary facet fff .Why is the condition sufficient?
If P\mathcal{P}P collides, some point ppp of P\mathcal{P}P hits a mold facet f^\hat ff^ , so d⃗\vec dd makes an angle above 90∘90^\circ90∘ with η⃗(f^)\vec\eta(\hat f)η(f^) , hence below 90∘90^\circ90∘ with η⃗(f)\vec\eta(f)η(f) . ppp is about to move into the interior of the mold; the ordinary facet fff corresponding to f^\hat ff^ then violates the condition. ppp is about to enter the mold through f^\hat ff^ .
[The Geometry of Casting] Can a polyhedron that is removable from its mold by a sequence of small translations always be removed by a single translation?
Yes. The direction of the first small translation makes an angle ≥90∘\ge 90^\circ≥90∘ with every outward normal of an ordinary facet (otherwise it would collide at once), so a single translation in that direction removes the polyhedron.
[The Geometry of Casting] How does the casting algorithm represent all directions with a positive zzz -component?
As the points of the plane z=1z = 1z=1 : the point (x,y,1)(x, y, 1)(x,y,1) stands for the direction of the vector (x,y,1)(x, y, 1)(x,y,1) . Every such direction corresponds to exactly one point of the plane.
[The Geometry of Casting] An ordinary facet of P\mathcal{P}P has outward normal η⃗=(ηx,ηy,ηz)\vec\eta = (\eta_x, \eta_y, \eta_z)η=(ηx,ηy,ηz) . Which constraint does the facet put on a removal direction d⃗=(dx,dy,1)\vec d = (d_x, d_y, 1)d=(dx,dy,1) , and what is it geometrically?
ηxdx+ηydy+ηz≤0\boldsymbol{\eta_x d_x + \eta_y d_y + \eta_z \le 0}ηxdx+ηydy+ηz≤0 , a closed half-plane in the plane z=1z = 1z=1 . d⃗\vec dd makes an angle ≥90∘\ge 90^\circ≥90∘ with η⃗\vec\etaη iff d⃗⋅η⃗≤0\vec d \cdot \vec\eta \le 0d⋅η≤0 .
[The Geometry of Casting] Which ordinary facets of P\mathcal{P}P do not give a half-plane on the plane z=1z = 1z=1 of directions, and what do they give instead?
Horizontal facets ( ηx=ηy=0\eta_x = \eta_y = 0ηx=ηy=0 ): the constraint is either impossible or always satisfied. Both cases are easy to test.
[The Geometry of Casting] To which planar problem does the book reduce "can P\mathcal{P}P (with nnn facets) be removed from a given mold"?
Given at most n−1n - 1n−1 half-planes, find a point in their common intersection or decide that the intersection is empty. One half-plane per ordinary facet (the top facet gives none). Any point of the intersection is a valid removal direction.
[The Geometry of Casting] Theorem 4.2. P\mathcal{P}P is a polyhedron with nnn facets. In what time and storage can you decide whether P\mathcal{P}P is castable?
O(n2)\boldsymbol{O(n^2)}O(n2) expected time, O(n)\boldsymbol{O(n)}O(n) storage. Try each of the nnn facets as top facet; each try is a 2-dimensional linear program with at most n−1n - 1n−1 constraints, solved in O(n)O(n)O(n) expected time. A mold and a removal direction are found in the same time.
[Half-Plane Intersection] What does a linear constraint aix+biy≤cia_i x + b_i y \le c_iaix+biy≤ci (with aia_iai or bib_ibi non-zero) describe geometrically?
A closed half-plane in R2\mathbb{R}^2R2 , bounded by the line aix+biy=cia_i x + b_i y = c_iaix+biy=ci .
[Half-Plane Intersection] Why is the common intersection of nnn half-planes a convex polygonal region with at most nnn edges?
Intersections of convex sets are convex, and by convexity each bounding line contributes at most one edge. Every boundary point of the intersection lies on the bounding line of some half-plane.
[Half-Plane Intersection] Besides a bounded convex polygon, what can the intersection of a set of half-planes look like?
Unbounded, degenerate (a line segment or a point), or empty. (i) bounded; (ii), (iii) unbounded; (iv) a single point; (v) empty.
[Half-Plane Intersection] How does the divide-and-conquer algorithm IntersectHalfplanes compute the intersection CCC of a set HHH of nnn half-planes?
Split HHH into halves of size ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ and ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ , intersect each recursively, then intersect the two convex regions. If HHH has one half-plane, CCC is that half-plane.
[Half-Plane Intersection] IntersectHalfplanes splits nnn half-planes into two halves, recursively computes their intersections C1C_1C1 and C2C_2C2 , and then intersects C1C_1C1 and C2C_2C2 .Chapter 2's overlay algorithm intersects C1C_1C1 and C2C_2C2 in O((n+k)logn)O((n + k) \log n)O((n+k)logn) time, where kkk is the number of intersections between edges of C1C_1C1 and edges of C2C_2C2 . Why is k≤nk \le nk≤n ?
Each such intersection point is a vertex of C1∩C2C_1 \cap C_2C1∩C2 , which is an intersection of nnn half-planes and so has at most nnn vertices. The crossing vvv of edges e1e_1e1 of C1C_1C1 and e2e_2e2 of C2C_2C2 is a vertex of C1∩C2C_1 \cap C_2C1∩C2 .
[Half-Plane Intersection] What running time does IntersectHalfplanes (divide and conquer over nnn half-planes) get when the merge step uses Chapter 2's map overlay algorithm?
O(nlog2n)\boldsymbol{O(n \log^2 n)}O(nlog2n) Merging takes O(nlogn)O(n \log n)O(nlogn) , so T(n)=O(nlogn)+2T(n/2)T(n) = O(n \log n) + 2T(n/2)T(n)=O(nlogn)+2T(n/2) .
[Half-Plane Intersection] How does the linear-time algorithm for intersecting two convex polygonal regions represent a convex region CCC ?
By two sorted lists of half-planes, Lleft(C)\mathcal{L}_{\text{left}}(C)Lleft(C) and Lright(C)\mathcal{L}_{\text{right}}(C)Lright(C) : the bounding lines of the left and of the right boundary, in order from top to bottom. Vertices aren't stored; they are the intersections of consecutive bounding lines.
[Half-Plane Intersection] A convex region is stored as a left and a right boundary list. Which list does a horizontal edge belong to?
The left list if the edge bounds the region from above, the right list if it bounds the region from below. The algorithm description assumes there are no horizontal edges; this convention needs only a few adaptations.
[Half-Plane Intersection] The intersection of two convex regions C1,C2C_1, C_2C1,C2 is computed by sweeping a line downward. What does the sweep maintain instead of a status structure?
Four pointers: left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. They point to the edges of C1C_1C1 and C2C_2C2 crossing the sweep line (nil if the line misses that boundary). By convexity at most four edges cross the sweep line.
[Half-Plane Intersection] When two convex regions C1,C2C_1, C_2C1,C2 are intersected by a downward sweep, where does the sweep line start?
At ystart=min(y1,y2)y_{\text{start}} = \min(y_1, y_2)ystart=min(y1,y2) , where yiy_iyi is the yyy -coordinate of the topmost vertex of CiC_iCi ( yi=∞y_i = \inftyyi=∞ if CiC_iCi has an edge going up to infinity). Above ystarty_{\text{start}}ystart the two regions don't meet.
[Half-Plane Intersection] Why does the sweep that intersects two convex regions need no event queue?
The next event is the highest of the lower endpoints of the at most four edges crossing the sweep line, found in constant time. Events are where edges of C1C_1C1 or C2C_2C2 start or stop crossing the sweep line. Endpoints at equal height: leftmost edge first.
[Half-Plane Intersection] Sweeping downward to intersect convex regions C1,C2C_1, C_2C1,C2 into CCC ; a new edge eee of the left boundary of C1C_1C1 starts at its upper endpoint ppp .Which three edges of CCC might start because of eee ?
The edge starting at ppp , the edge starting at e∩e \cape∩ left_edge_C2, and the edge starting at e∩e \cape∩ right_edge_C2. Tested in this order: ppp between the two edges of C2C_2C2 ; eee crossing right_edge_C2; eee crossing left_edge_C2.
[Half-Plane Intersection] Sweeping downward to intersect convex regions C1,C2C_1, C_2C1,C2 into CCC ; a new edge eee of the left boundary of C1C_1C1 starts at its upper endpoint ppp .When does eee contribute an edge of CCC starting at ppp , and what is recorded?
When ppp lies between left_edge_C2 and right_edge_C2; then the half-plane bounded by eee is added to Lleft(C)\mathcal{L}_{\text{left}}(C)Lleft(C) .
[Half-Plane Intersection] Sweeping downward to intersect convex regions C1,C2C_1, C_2C1,C2 into CCC ; a new edge eee of the left boundary of C1C_1C1 , with upper endpoint ppp , crosses right_edge_C2.How is the crossing handled?
ppp right of right_edge_C2: two edges of CCC start at the crossing. ppp left of it: two edges end there, do nothing. In the first case add eee 's half-plane to Lleft(C)\mathcal{L}_{\text{left}}(C)Lleft(C) and right_edge_C2's to Lright(C)\mathcal{L}_{\text{right}}(C)Lright(C) . Edges ending at the crossing were discovered earlier. (i) ppp right of right_edge_C2; (ii) ppp left of it.
[Half-Plane Intersection] Sweeping downward to intersect convex regions C1,C2C_1, C_2C1,C2 into CCC ; a new edge eee of the left boundary of C1C_1C1 , with upper endpoint ppp , crosses left_edge_C2.Which edge of CCC starts at the crossing?
Part of eee if ppp lies left of left_edge_C2, otherwise part of left_edge_C2; its half-plane goes to Lleft(C)\mathcal{L}_{\text{left}}(C)Lleft(C) . Here ppp is left of left_edge_C2, so eee continues the boundary of CCC below the crossing.
[Half-Plane Intersection] Intersecting convex regions C1,C2C_1, C_2C1,C2 into CCC by a downward sweep, handling a new left edge eee of C1C_1C1 can add two half-planes to Lleft(C)\mathcal{L}_{\text{left}}(C)Lleft(C) : eee 's and that of left_edge_C2.In which order, and why is that order automatic?
eee 's half-plane first, which the order of the tests (first ppp , then the crossing with right_edge_C2, then left_edge_C2) guarantees. eee 's edge of CCC starts at ppp or at the crossing with right_edge_C2, both above the edge of left_edge_C2 starting at the crossing with eee .
[Half-Plane Intersection] Why does the downward sweep that intersects two convex regions C1,C2C_1, C_2C1,C2 find every edge of C=C1∩C2C = C_1 \cap C_2C=C1∩C2 ?
Each edge of CCC starts at an upper endpoint of an edge of C1C_1C1 or C2C_2C2 , or at a crossing of two edges e,e′e, e'e,e′ , and the sweep handles every such point. A crossing of eee (of C1C_1C1 ) and e′e'e′ (of C2C_2C2 ) is found when the lower of the upper endpoints of eee and e′e'e′ is reached. So the half-planes of all edges of CCC are added; that they are added in the right order is not hard to prove either.
[Half-Plane Intersection] Theorem 4.3. In what time can the intersection of two convex polygonal regions in the plane be computed?
O(n)\boldsymbol{O(n)}O(n) , with nnn the total number of edges. A downward sweep keeps four edge pointers and handles each edge in constant time.
[Half-Plane Intersection] Corollary 4.4. In what time and storage can the common intersection of nnn half-planes in the plane be computed?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) time, linear storage. Divide and conquer with a linear-time merge: T(n)=O(n)+2T(n/2)T(n) = O(n) + 2T(n/2)T(n)=O(n)+2T(n/2) . The problem is closely related to convex hulls (by duality); an almost identical algorithm to the convex hull algorithm of Chapter 1 also works.
[Incremental Linear Programming] Computing the intersection of nnn half-planes takes Ω(nlogn)\Omega(n \log n)Ω(nlogn) time in the worst case. Why can the casting problem still be solved faster?
Casting needs only one point of the intersection, not all of the intersection. The Ω(nlogn)\Omega(n \log n)Ω(nlogn) lower bound is like the one for sorting.
[Incremental Linear Programming] What is a linear program, and what is its dimension?
A linear objective function c1x1+⋯+cdxdc_1x_1 + \dots + c_dx_dc1x1+⋯+cdxd to maximize, together with a set of linear constraints ai,1x1+⋯+ai,dxd≤bia_{i,1}x_1 + \dots + a_{i,d}x_d \le b_iai,1x1+⋯+ai,dxd≤bi . The dimension is the number ddd of variables. "Programming" here predates its meaning of instructing a computer. Also called linear optimization.
[Incremental Linear Programming] For a linear program in ddd variables, what are the feasible region, feasible points, and an infeasible linear program?
Feasible region: the intersection of the constraint half-spaces in Rd\mathbb{R}^dRd ; its points are feasible; the linear program is infeasible if the region is empty. The feasible region can also be unbounded.
[Incremental Linear Programming] Geometrically, what does maximizing c1x1+⋯+cdxdc_1x_1 + \dots + c_dx_dc1x1+⋯+cdxd over the feasible region mean?
Finding a point of the feasible region that is extreme in the direction c⃗=(c1,…,cd)\vec c = (c_1, \dots, c_d)c=(c1,…,cd) . fc⃗f_{\vec c}fc denotes the objective function given by the direction c⃗\vec cc .
[Incremental Linear Programming] Why not use the simplex algorithm for the linear programs from casting?
They are low-dimensional (only 2 variables), and traditional methods are not efficient for low-dimensional linear programming. In operations research both the number of constraints and of variables are large. Computational geometry methods do better when ddd is small.
[Incremental Linear Programming] (H,c⃗)(H, \vec c)(H,c) is a 2-dimensional linear program with feasible region CCC . Which four kinds of solution are possible?
Infeasible; unbounded in direction c⃗\vec cc ; an optimal edge (solution not unique); a unique optimal vertex. c⃗\vec cc points down. (ii) a ray ρ⊆C\rho \subseteq Cρ⊆C along which fc⃗f_{\vec c}fc gets arbitrarily large; (iii) an edge eee whose outward normal points in direction c⃗\vec cc ; (iv) the vertex vvv extreme in direction c⃗\vec cc .
[Incremental Linear Programming] For the incremental 2D linear programming algorithm, how do the constraints m1,m2m_1, m_2m1,m2 make every intermediate linear program bounded?
m1m_1m1 : px≤Mp_x \le Mpx≤M if cx>0c_x > 0cx>0 , else −px≤M-p_x \le M−px≤M ; m2m_2m2 : py≤Mp_y \le Mpy≤M if cy>0c_y > 0cy>0 , else −py≤M-p_y \le M−py≤M , for a large MMM . m1,m2m_1, m_2m1,m2 depend only on c⃗\vec cc , not on HHH . MMM must be so large that m1,m2m_1, m_2m1,m2 don't change the solution of a bounded program. C0=m1∩m2C_0 = m_1 \cap m_2C0=m1∩m2 is an orthogonal wedge.
[Incremental Linear Programming] Why is a bound like ∣px∣,∣py∣≤M|p_x|, |p_y| \le M∣px∣,∣py∣≤M natural in the casting application?
The polyhedron can't be removed in a nearly horizontal direction, e.g. at less than 1 degree to the xyxyxy -plane. Directions are points (px,py)(p_x, p_y)(px,py) of the plane z=1z = 1z=1 , so a minimum angle bounds ∣px∣|p_x|∣px∣ and ∣py∣|p_y|∣py∣ .
[Incremental Linear Programming] If a 2D linear program has several optimal points, which one does the book's convention choose?
The lexicographically smallest one (smallest xxx , then smallest yyy ). Conceptually this rotates c⃗\vec cc a little, so that c⃗\vec cc is no longer normal to any half-plane.
[Incremental Linear Programming] Can a bounded linear program fail to have a lexicographically smallest solution?
Yes, e.g. maximize yyy subject to y≤0y \le 0y≤0 : the optimal points form the line y=0y = 0y=0 , with no smallest xxx . The constraints m1,m2m_1, m_2m1,m2 are chosen so that this can't happen.
[Incremental Linear Programming] With the bounding constraints m1,m2m_1, m_2m1,m2 and the lexicographic rule, every feasible 2D linear program has a unique solution, a vertex of the feasible region called the optimal vertex.
[Incremental Linear Programming] In incremental 2D linear programming with half-planes h1,…,hnh_1, \dots, h_nh1,…,hn and bounding constraints m1,m2m_1, m_2m1,m2 , what are HiH_iHi , CiC_iCi and viv_ivi ?
Hi={m1,m2,h1,…,hi}H_i = \{m_1, m_2, h_1, \dots, h_i\}Hi={m1,m2,h1,…,hi} , Ci=m1∩m2∩h1∩⋯∩hiC_i = m_1 \cap m_2 \cap h_1 \cap \dots \cap h_iCi=m1∩m2∩h1∩⋯∩hi , viv_ivi = optimal vertex of CiC_iCi . C0⊇C1⊇⋯⊇Cn=CC_0 \supseteq C_1 \supseteq \dots \supseteq C_n = CC0⊇C1⊇⋯⊇Cn=C , so once some Ci=∅C_i = \emptysetCi=∅ the algorithm can stop: the program is infeasible.
[Incremental Linear Programming] Lemma 4.5. CiC_iCi is the feasible region after adding half-plane hih_ihi , with optimal vertex viv_ivi , and ℓi\ell_iℓi bounds hih_ihi . What happens to the optimal vertex when hih_ihi is added?
If vi−1∈hiv_{i-1} \in h_ivi−1∈hi , then vi=vi−1v_i = v_{i-1}vi=vi−1 . Otherwise Ci=∅C_i = \emptysetCi=∅ or vi∈ℓiv_i \in \ell_ivi∈ℓi . (i) v4∈h5v_4 \in h_5v4∈h5 , so v5=v4v_5 = v_4v5=v4 . (ii) v5∉h6v_5 \notin h_6v5∈/h6 , so v6v_6v6 lies on the line bounding h6h_6h6 .
[Incremental Linear Programming] Ci=Ci−1∩hiC_i = C_{i-1} \cap h_iCi=Ci−1∩hi and viv_ivi is the optimal vertex of CiC_iCi .Why does vi−1∈hiv_{i-1} \in h_ivi−1∈hi imply vi=vi−1v_i = v_{i-1}vi=vi−1 ?
vi−1v_{i-1}vi−1 lies in CiC_iCi , and no point of Ci⊆Ci−1C_i \subseteq C_{i-1}Ci⊆Ci−1 is better than the optimum of Ci−1C_{i-1}Ci−1 .
[Incremental Linear Programming] Ci=Ci−1∩hiC_i = C_{i-1} \cap h_iCi=Ci−1∩hi , viv_ivi is the optimal vertex of CiC_iCi , and ℓi\ell_iℓi bounds hih_ihi . Claim: if vi−1∉hiv_{i-1} \notin h_ivi−1∈/hi , then Ci=∅C_i = \emptysetCi=∅ or vi∈ℓiv_i \in \ell_ivi∈ℓi .How does the proof get a contradiction from Ci≠∅C_i \ne \emptysetCi=∅ and vi∉ℓiv_i \notin \ell_ivi∈/ℓi ?
The segment vi−1vi‾\overline{v_{i-1}v_i}vi−1vi lies in Ci−1C_{i-1}Ci−1 and crosses ℓi\ell_iℓi at a point q∈Ciq \in C_iq∈Ci with fc⃗(q)>fc⃗(vi)f_{\vec c}(q) > f_{\vec c}(v_i)fc(q)>fc(vi) . Ci−1C_{i-1}Ci−1 is convex, vi−1v_{i-1}vi−1 is its optimum, and fc⃗f_{\vec c}fc is linear, so fc⃗f_{\vec c}fc increases from viv_ivi towards vi−1v_{i-1}vi−1 .
[Incremental Linear Programming] In incremental 2D linear programming the optimal vertex vi−1v_{i-1}vi−1 is not in the new half-plane hih_ihi with bounding line ℓi\ell_iℓi . Which problem is solved to find viv_ivi ?
A 1-dimensional linear program: find the point ppp on ℓi\ell_iℓi maximizing fc⃗(p)f_{\vec c}(p)fc(p) subject to p∈hp \in hp∈h for all h∈Hi−1h \in H_{i-1}h∈Hi−1 . Hi−1H_{i-1}Hi−1 : the earlier half-planes together with the bounding constraints m1,m2m_1, m_2m1,m2 .
[Incremental Linear Programming] Finding the best point on a line ℓi\ell_iℓi (not vertical) subject to half-planes hhh : what is σ(h,ℓi)\sigma(h, \ell_i)σ(h,ℓi) , and what constraint does hhh give?
σ(h,ℓi)\sigma(h, \ell_i)σ(h,ℓi) is the xxx -coordinate of ℓi∩\ell_i \capℓi∩ (bounding line of hhh ); hhh gives x≥σ(h,ℓi)x \ge \sigma(h, \ell_i)x≥σ(h,ℓi) or x≤σ(h,ℓi)x \le \sigma(h, \ell_i)x≤σ(h,ℓi) , as ℓi∩h\ell_i \cap hℓi∩h is bounded to the left or to the right. If the bounding line of hhh is parallel to ℓi\ell_iℓi , either all of ℓi\ell_iℓi satisfies hhh (ignore hhh ) or none does (infeasible).
[Incremental Linear Programming] How is a 1-dimensional linear program with constraints x≥σx \ge \sigmax≥σ and x≤σ′x \le \sigma'x≤σ′ solved?
xleftx_{\text{left}}xleft = max of the left bounds, xrightx_{\text{right}}xright = min of the right bounds; infeasible if xleft>xrightx_{\text{left}} > x_{\text{right}}xleft>xright , otherwise the optimum is xleftx_{\text{left}}xleft or xrightx_{\text{right}}xright , depending on the objective. In incremental 2D linear programming it can't be unbounded, due to the bounding constraints m1,m2m_1, m_2m1,m2 .
[Incremental Linear Programming] Lemma 4.6. In incremental 2D linear programming the optimal vertex vi−1v_{i-1}vi−1 violates the new half-plane hih_ihi . In what time is the new optimal vertex viv_ivi found (or infeasibility detected)?
O(i)\boldsymbol{O(i)}O(i) It is a 1-dimensional linear program on the line bounding hih_ihi with i+1i + 1i+1 constraints, solvable in linear time.
[Incremental Linear Programming] What are the steps of 2dBoundedLP, for half-planes h1,…,hnh_1, \dots, h_nh1,…,hn , objective c⃗\vec cc , and bounding constraints m1,m2m_1, m_2m1,m2 ?
Start at the corner v0v_0v0 of m1∩m2m_1 \cap m_2m1∩m2 . For i=1,…,ni = 1, \dots, ni=1,…,n : if vi−1∈hiv_{i-1} \in h_ivi−1∈hi keep vi=vi−1v_i = v_{i-1}vi=vi−1 ; else viv_ivi = best point on ℓi\ell_iℓi subject to Hi−1H_{i-1}Hi−1 , and if none exists report infeasible. Return vnv_nvn . ℓi\ell_iℓi bounds hih_ihi ; Hi−1={m1,m2,h1,…,hi−1}H_{i-1} = \{m_1, m_2, h_1, \dots, h_{i-1}\}Hi−1={m1,m2,h1,…,hi−1} . The output is the lexicographically smallest optimal point.
[Incremental Linear Programming] Lemma 4.7. In what time and storage does 2dBoundedLP (add the nnn half-planes one by one, solving a 1D linear program whenever the optimum changes) solve a bounded 2D linear program?
O(n2)\boldsymbol{O(n^2)}O(n2) time, linear storage. Stage iii costs O(i)O(i)O(i) , and ∑i=1nO(i)=O(n2)\sum_{i=1}^{n} O(i) = O(n^2)∑i=1nO(i)=O(n2) . Correctness: after each stage viv_ivi is the optimum of CiC_iCi , by how the optimum changes when a half-plane is added.
[Incremental Linear Programming] Is the O(n2)O(n^2)O(n2) bound of 2dBoundedLP (add half-planes in the given order, solve a 1D program in O(i)O(i)O(i) time whenever the optimum changes) tight?
Yes: in some configurations every new half-plane makes the previous optimum infeasible, so the algorithm takes Θ(n2)\Theta(n^2)Θ(n2) . Stage iii takes Θ(i)\Theta(i)Θ(i) only when vi−1∉hiv_{i-1} \notin h_ivi−1∈/hi ; here that happens at every stage.
[Randomized Linear Programming] In this configuration, adding h1,h2,…,hnh_1, h_2, \dots, h_nh1,h2,…,hn in that order changes the optimal vertex every time. What happens with the order hn,hn−1,…,h3h_n, h_{n-1}, \dots, h_3hn,hn−1,…,h3 , and does every set of half-planes have a good order?
The optimum no longer changes after hnh_nhn , so O(n)O(n)O(n) time; a good order always exists, but there is no easy way to find it. The order must be chosen before anything is known about the intersection.
[Randomized Linear Programming] What is the only difference between 2dRandomizedBoundedLP and 2dBoundedLP (incremental 2D linear programming)?
The half-planes are put into a random order before they are added one by one. Computed by RandomPermutation.
[Randomized Linear Programming] How does RandomPermutation rearrange an array A[1…n]A[1 \dots n]A[1…n] , and how long does it take?
For k=nk = nk=n down to 2: pick rndindex=Random(k)\text{rndindex} = \text{Random}(k)rndindex=Random(k) and swap A[k]A[k]A[k] with A[rndindex]A[\text{rndindex}]A[rndindex] . O(n)O(n)O(n) time. Random(k)\text{Random}(k)Random(k) returns a random integer between 1 and kkk in constant time.
[Randomized Linear Programming] An algorithm whose running time depends on random choices it makes is a randomized algorithm.
[Randomized Linear Programming] What is the expected running time of 2dRandomizedBoundedLP on a set HHH of nnn half-planes?
The average running time over all n!n!n! possible permutations of HHH . No assumption on the input: the expectation is only over the algorithm's random order, and the bound holds for every HHH . There are no bad inputs.
[Randomized Linear Programming] Lemma 4.8. In what time and storage can the 2-dimensional linear programming problem with nnn constraints be solved (with bounding constraints m1,m2m_1, m_2m1,m2 )?
O(n)\boldsymbol{O(n)}O(n) randomized expected time, worst-case linear storage. By inserting the half-planes in random order (2dRandomizedBoundedLP).
[Randomized Linear Programming] 2dRandomizedBoundedLP adds half-planes h1,…,hnh_1, \dots, h_nh1,…,hn in random order; when the optimal vertex vi−1v_{i-1}vi−1 is not in hih_ihi it solves a 1D linear program in O(i)O(i)O(i) time.How does the proof of the O(n)O(n)O(n) expected time write the total time of the 1D linear programs?
∑i=1nO(i)⋅Xi\boldsymbol{\sum_{i=1}^{n} O(i) \cdot X_i}∑i=1nO(i)⋅Xi , with Xi=1X_i = 1Xi=1 if vi−1∉hiv_{i-1} \notin h_ivi−1∈/hi , else 0; by linearity of expectation its expectation is ∑O(i)⋅E[Xi]\sum O(i) \cdot E[X_i]∑O(i)⋅E[Xi] . Linearity of expectation holds even for dependent random variables.
[Randomized Linear Programming] 2dRandomizedBoundedLP adds half-planes h1,…,hnh_1, \dots, h_nh1,…,hn in random order; viv_ivi is the optimal vertex after adding hih_ihi .Using backwards analysis, why is the probability that vi−1∉hiv_{i-1} \notin h_ivi−1∈/hi at most 2/i2/i2/i ?
Fix the set {h1,…,hi}\{h_1, \dots, h_i\}{h1,…,hi} ; removing hih_ihi changes viv_ivi only if hih_ihi is one of the ≤2\le 2≤2 half-planes defining viv_ivi . hih_ihi is a random one of the iii half-planes in the fixed set. The two half-planes whose bounding lines meet at vnv_nvn . The bound holds for every fixed subset, so unconditionally.
[Randomized Linear Programming] Backwards analysis for randomized incremental 2D linear programming: removing the last added half-plane hih_ihi changes the optimal vertex viv_ivi only if hih_ihi is one of the half-planes defining viv_ivi .Why is the probability of a change at most 2/i2/i2/i , not exactly 2/i2/i2/i ?
More than two bounding lines may pass through viv_ivi (removing one need not change viv_ivi ), or viv_ivi may be defined by m1m_1m1 or m2m_2m2 , which are never the random hih_ihi .
[Randomized Linear Programming] In randomized incremental 2D linear programming, stage iii solves a 1D linear program in O(i)O(i)O(i) time with probability at most 2/i2/i2/i .What is the expected total time of these 1D linear programs?
∑i=1nO(i)⋅2i=O(n)\displaystyle\boldsymbol{\sum_{i=1}^{n} O(i) \cdot \frac{2}{i} = O(n)}i=1∑nO(i)⋅i2=O(n) The rest of the algorithm (random permutation, the O(1)O(1)O(1) tests vi−1∈hiv_{i-1} \in h_ivi−1∈hi ) also takes O(n)O(n)O(n) .
[Randomized Linear Programming] Analysing a randomized incremental algorithm by fixing the first iii objects and asking how likely the last insertion changed the result is called backwards analysis.
The algorithm is viewed "backwards": one step back in time removes a random one of the iii objects.
[Unbounded Linear Programs] Why not always handle unbounded 2D linear programs by adding artificial constraints ∣px∣,∣py∣≤M|p_x|, |p_y| \le M∣px∣,∣py∣≤M ?
A large enough MMM may not be known, and unbounded linear programs occur in practice and must be solved correctly.
[Unbounded Linear Programs] A ray ρ={p+λd⃗:λ>0}\rho = \{p + \lambda \vec d : \lambda > 0\}ρ={p+λd:λ>0} lies in the feasible region of (H,c⃗)(H, \vec c)(H,c) and fc⃗f_{\vec c}fc is unbounded along ρ\rhoρ . Which two conditions must d⃗\vec dd satisfy?
d⃗⋅c⃗>0\boldsymbol{\vec d \cdot \vec c > 0}d⋅c>0 and d⃗⋅η⃗(h)≥0\boldsymbol{\vec d \cdot \vec\eta(h) \ge 0}d⋅η(h)≥0 for all h∈Hh \in Hh∈H . η⃗(h)\vec\eta(h)η(h) is the normal of hhh pointing to the feasible side of its bounding line.
[Unbounded Linear Programs] Lemma 4.9. A linear program (H,c⃗)(H, \vec c)(H,c) is unbounded if and only if … ?
There is a d⃗\vec dd with d⃗⋅c⃗>0\vec d \cdot \vec c > 0d⋅c>0 and d⃗⋅η⃗(h)≥0\vec d \cdot \vec\eta(h) \ge 0d⋅η(h)≥0 for all h∈Hh \in Hh∈H , such that (H′,c⃗)(H', \vec c)(H′,c) is feasible, where H′={h∈H:η⃗(h)⋅d⃗=0}H' = \{h \in H : \vec\eta(h) \cdot \vec d = 0\}H′={h∈H:η(h)⋅d=0} . η⃗(h)\vec\eta(h)η(h) : the normal of hhh towards its feasible side. H′H'H′ are the half-planes whose bounding lines are parallel to d⃗\vec dd .
[Unbounded Linear Programs] d⃗⋅c⃗>0\vec d \cdot \vec c > 0d⋅c>0 , d⃗⋅η⃗(h)≥0\vec d \cdot \vec\eta(h) \ge 0d⋅η(h)≥0 for all h∈Hh \in Hh∈H , and the half-planes H′={h:η⃗(h)⋅d⃗=0}H' = \{h : \vec\eta(h) \cdot \vec d = 0\}H′={h:η(h)⋅d=0} have a common point p0p_0p0 .How does the proof find a ray in the feasible region of (H,c⃗)(H, \vec c)(H,c) along which fc⃗f_{\vec c}fc is unbounded?
Start at p=p0+λ′d⃗p = p_0 + \lambda' \vec dp=p0+λ′d , where λ′\lambda'λ′ is large enough that the ray {p+λd⃗}\{p + \lambda \vec d\}{p+λd} has entered every h∈H∖H′h \in H \setminus H'h∈H∖H′ . The ray from p0p_0p0 stays in each h∈H′h \in H'h∈H′ (parallel to its boundary). For h∈H∖H′h \in H \setminus H'h∈H∖H′ , d⃗⋅η⃗(h)>0\vec d \cdot \vec\eta(h) > 0d⋅η(h)>0 , so p0+λd⃗∈hp_0 + \lambda\vec d \in hp0+λd∈h for all λ≥λh\lambda \ge \lambda_hλ≥λh ; take λ′=maxλh\lambda'…
[Unbounded Linear Programs] How is "is there a d⃗\vec dd with d⃗⋅c⃗>0\vec d \cdot \vec c > 0d⋅c>0 and d⃗⋅η⃗(h)≥0\vec d \cdot \vec\eta(h) \ge 0d⋅η(h)≥0 for all h∈Hh \in Hh∈H " decided for a 2D linear program (H,c⃗)(H, \vec c)(H,c) ?
Rotate so that c⃗=(0,1)\vec c = (0, 1)c=(0,1) and write d⃗=(dx,1)\vec d = (d_x, 1)d=(dx,1) ; each hhh gives dxηx+ηy≥0d_x \eta_x + \eta_y \ge 0dxηx+ηy≥0 : a 1-dimensional linear program H‾\overline{H}H in dxd_xdx . Any d⃗\vec dd with d⃗⋅c⃗>0\vec d \cdot \vec c > 0d⋅c>0 can be normalized to (dx,1)(d_x, 1)(dx,1) , represented by the point dxd_xdx on the line y=1y = 1y=1 (like the plane z=1z = 1z=1 for casting). Only feasibility matters, so no objective.
[Unbounded Linear Programs] Testing whether a 2D linear program (H,c⃗)(H, \vec c)(H,c) with c⃗=(0,1)\vec c = (0, 1)c=(0,1) is unbounded: the 1D constraints dxηx(h)+ηy(h)≥0d_x \eta_x(h) + \eta_y(h) \ge 0dxηx(h)+ηy(h)≥0 ( h∈Hh \in Hh∈H ) have a solution dx∗d_x^*dx∗ .What is checked next, and how?
Whether H′={h:dx∗ηx+ηy=0}H' = \{h : d_x^* \eta_x + \eta_y = 0\}H′={h:dx∗ηx+ηy=0} is feasible: its bounding lines are all parallel to d⃗=(dx∗,1)\vec d = (d_x^*, 1)d=(dx∗,1) , so intersecting them with the xxx -axis gives another 1D linear program. If H′H'H′ is feasible, (H,c⃗)(H, \vec c)(H,c) is unbounded and a ray is built in O(n)O(n)O(n) ; otherwise HHH is infeasible.
[Unbounded Linear Programs] Testing whether a 2D linear program (H,c⃗)(H, \vec c)(H,c) with c⃗=(0,1)\vec c = (0, 1)c=(0,1) is unbounded: the 1D constraints dxηx(h)+ηy(h)≥0d_x \eta_x(h) + \eta_y(h) \ge 0dxηx(h)+ηy(h)≥0 ( h∈Hh \in Hh∈H ) have no solution.What does the algorithm extract from this?
Two certificates h1,h2h_1, h_2h1,h2 : the half-planes giving the largest left bound and the smallest right bound of the 1D program, with empty intersection; so ({h1,h2},c⃗)(\{h_1, h_2\}, \vec c)({h1,h2},c) is bounded. A linear program is unbounded only if a direction d⃗\vec dd with d⃗⋅c⃗>0\vec d \cdot \vec c > 0d⋅c>0 and d⃗⋅η⃗(h)≥0\vec d \cdot \vec\eta(h) \ge 0d⋅η(h)≥0 for all hhh exists, so (H,c⃗)(H, \vec c)(H,c) is then bounded.
[Unbounded Linear Programs] What are the certificates h1,h2h_1, h_2h1,h2 of a bounded 2D linear program (H,c⃗)(H, \vec c)(H,c) used for?
They replace the artificial constraints m1,m2m_1, m_2m1,m2 in 2dRandomizedBoundedLP (random-order incremental algorithm for bounded programs), so no artificial restriction on the solution is needed. ({h1,h2},c⃗)(\{h_1, h_2\}, \vec c)({h1,h2},c) is bounded, which proves that (H,c⃗)(H, \vec c)(H,c) is.
[Unbounded Linear Programs] When is ({h1,h2},c⃗)(\{h_1, h_2\}, \vec c)({h1,h2},c) bounded but without a lexicographically smallest solution ( c⃗=(0,1)\vec c = (0, 1)c=(0,1) ), and what does the algorithm do then?
When one constraint h1h_1h1 with η⃗(h1)=−c⃗=(0,−1)\vec\eta(h_1) = -\vec c = (0, -1)η(h1)=−c=(0,−1) makes the 1D program infeasible: then look for an h2h_2h2 with ηx(h2)>0\eta_x(h_2) > 0ηx(h2)>0 . If there is such an h2h_2h2 , h1,h2h_1, h_2h1,h2 guarantee a unique lexicographically smallest solution. If not, solve the 1D program of all hhh with ηx(h)=0\eta_x(h) = 0ηx(h)=0 ; if feasible, report a ray in direction (−1,0)(-1, 0)(−1,0) of optimal solutions.
[Unbounded Linear Programs] What does 2dRandomizedLP (H,c⃗)(H, \vec c)(H,c) output for unbounded, infeasible and bounded feasible 2D linear programs?
A ray if unbounded; two or three certificate half-planes if infeasible; otherwise the lexicographically smallest point maximizing fc⃗f_{\vec c}fc .
[Unbounded Linear Programs] After finding certificates h1,h2h_1, h_2h1,h2 that the 2D linear program (H,c⃗)(H, \vec c)(H,c) is bounded, how does 2dRandomizedLP continue?
v2=ℓ1∩ℓ2v_2 = \ell_1 \cap \ell_2v2=ℓ1∩ℓ2 ; randomly permute the rest into h3,…,hnh_3, \dots, h_nh3,…,hn ; add them one by one as in the bounded algorithm. If the 1D program on ℓi\ell_iℓi is infeasible, there are hj,hkh_j, h_khj,hk with j,k<ij, k < ij,k<i (possibly equal) and hj∩hk∩ℓi=∅h_j \cap h_k \cap \ell_i = \emptysethj∩hk∩ℓi=∅ ; report hi,hj,hkh_i, h_j, h_khi,hj,hk as certificates of infeasibility.
[Unbounded Linear Programs] Theorem 4.10. In what time and storage can a 2-dimensional linear programming problem with nnn constraints be solved, unbounded or not?
O(n)\boldsymbol{O(n)}O(n) randomized expected time, worst-case linear storage.
[Linear Programming in Higher Dimensions] In ddd -dimensional linear programming with closed half-spaces HHH and objective c⃗\vec cc , which solution is sought if several points maximize fc⃗(p)=c1p1+⋯+cdpdf_{\vec c}(p) = c_1p_1 + \dots + c_dp_dfc(p)=c1p1+⋯+cdpd ?
The lexicographically smallest one. This makes the solution unique when the linear program is bounded.
[Linear Programming in Higher Dimensions] How does the randomized incremental ddd -dimensional linear programming algorithm make every intermediate solution unique?
It first checks boundedness and obtains ddd certificates h1,…,hd∈Hh_1, \dots, h_d \in Hh1,…,hd∈H . The certificates guarantee a bounded program with a unique lexicographically smallest solution.The other half-spaces are randomly permuted into hd+1,…,hnh_{d+1}, \dots, h_nhd+1,…,hn , and Ci=h1∩⋯∩hiC_i = h_1 \cap \dots \cap h_iCi=h1∩⋯∩hi for d≤i≤nd \le i \le nd≤i≤n .
[Linear Programming in Higher Dimensions] Lemma 4.11. In ddd -dimensional incremental linear programming, viv_ivi is the optimal vertex of Ci=h1∩⋯∩hiC_i = h_1 \cap \dots \cap h_iCi=h1∩⋯∩hi and gig_igi is the hyperplane bounding hih_ihi . How does viv_ivi relate to vi−1v_{i-1}vi−1 ?
If vi−1∈hiv_{i-1} \in h_ivi−1∈hi , then vi=vi−1v_i = v_{i-1}vi=vi−1 ; otherwise Ci=∅C_i = \emptysetCi=∅ or vi∈giv_i \in g_ivi∈gi . The proof is the same as in the plane. So viv_ivi is the optimal vertex of gi∩Ci−1g_i \cap C_{i-1}gi∩Ci−1 .
[Linear Programming in Higher Dimensions] In 3-dimensional incremental linear programming, how is the optimal vertex of gi∩Ci−1g_i \cap C_{i-1}gi∩Ci−1 found ( gig_igi the plane bounding the new half-space)?
Intersect the i−1i - 1i−1 earlier half-spaces with gig_igi and solve the resulting 2-dimensional linear program, with c⃗\vec cc projected onto gig_igi as objective. If c⃗\vec cc is orthogonal to gig_igi , project (−1,0,0)(-1, 0, 0)(−1,0,0) , (0,−1,0)(0, -1, 0)(0,−1,0) , (0,0,−1)(0, 0, -1)(0,0,−1) in turn until the projection is non-zero; this picks the lexicographically smallest solution.
[Linear Programming in Higher Dimensions] In ddd -dimensional incremental linear programming, how is the new optimum on the hyperplane gig_igi found?
By a recursive call: a (d−1)(d-1)(d−1) -dimensional linear program on gig_igi . The recursion bottoms out at 1-dimensional linear programs, solved directly in linear time.
[Linear Programming in Higher Dimensions] How does the ddd -dimensional algorithm decide whether (H,c⃗)(H, \vec c)(H,c) is bounded?
(H,c⃗)(H, \vec c)(H,c) is bounded iff a certain (d−1)(d-1)(d−1) -dimensional linear program is infeasible, solved by a recursive call. The program asks for d⃗\vec dd with d⃗⋅c⃗>0\vec d \cdot \vec c > 0d⋅c>0 and d⃗⋅η⃗(h)≥0\vec d \cdot \vec\eta(h) \ge 0d⋅η(h)≥0 for all hhh . If it is feasible, (H,c⃗)(H, \vec c)(H,c) is unbounded in direction d⃗\vec dd or infeasible: check whether H′H'H′ (boundaries parallel to d⃗\vec dd ) is feasible with a second (d−1)(d-1)(d−1) -dimensional call.
[Linear Programming in Higher Dimensions] The boundedness test of a ddd -dimensional linear program (H,c⃗)(H, \vec c)(H,c) returns only k<dk < dk<d certificates h1,…,hkh_1, \dots, h_kh1,…,hk . What then?
The optimal solutions of ({h1,…,hk},c⃗)(\{h_1, \dots, h_k\}, \vec c)({h1,…,hk},c) form a (d−k)(d-k)(d−k) -dimensional subspace; test whether the linear program restricted to it is bounded in the lexicographic order, and repeat until there are ddd certificates. If it is not bounded, report the solution.
[Linear Programming in Higher Dimensions] When RandomizedLP (in Rd\mathbb{R}^dRd ) finds the linear program infeasible while adding half-space hih_ihi , which certificates does it report?
H∗∪hiH^* \cup h_iH∗∪hi , where H∗H^*H∗ is at most ddd certificates for the infeasibility of the (d−1)(d-1)(d−1) -dimensional program on gig_igi , so at most d+1d + 1d+1 half-spaces.
[Linear Programming in Higher Dimensions] Theorem 4.12. For a fixed dimension ddd , in what time can a ddd -dimensional linear program with nnn constraints be solved?
O(n)\boldsymbol{O(n)}O(n) expected time. By the randomized incremental algorithm RandomizedLP.
[Linear Programming in Higher Dimensions] RandomizedLP in Rd\mathbb{R}^dRd : when the optimum vi−1v_{i-1}vi−1 violates hih_ihi , it projects c⃗\vec cc on gig_igi , intersects iii half-spaces with gig_igi , and recursively solves a (d−1)(d-1)(d−1) -dimensional program with i−1i - 1i−1 half-spaces.Why is the probability of this at stage iii at most d/(i−d)d/(i-d)d/(i−d) ?
Backwards: viv_ivi is defined by ddd half-spaces, and only hd+1,…,hih_{d+1}, \dots, h_ihd+1,…,hi (that is, i−di - di−d half-spaces) are in random order. The optimum changes only if the removed hih_ihi is one of the ddd defining viv_ivi .
[Linear Programming in Higher Dimensions] The expected time CdnC_d nCdn of RandomizedLP in Rd\mathbb{R}^dRd is bounded by O(dn)+dCd−1n+∑i=d+1n(O(di)+Cd−1(i−1))di−dO(dn) + dC_{d-1}n + \sum_{i=d+1}^{n} \big(O(di) + C_{d-1}(i-1)\big)\frac{d}{i-d}O(dn)+dCd−1n+∑i=d+1n(O(di)+Cd−1(i−1))i−dd .How does CdC_dCd grow with ddd ?
Cd=O(Cd−1d)\boldsymbol{C_d = O(C_{d-1} d)}Cd=O(Cd−1d) , so Cd=O(cdd!)\boldsymbol{C_d = O(c^d d!)}Cd=O(cdd!) for a constant ccc independent of ddd . O(dn)+dCd−1nO(dn) + dC_{d-1}nO(dn)+dCd−1n : at most ddd recursive programs for the certificates, computing vdv_dvd , and the O(d)O(d)O(d) tests vi−1∈hiv_{i-1} \in h_ivi−1∈hi .
[Linear Programming in Higher Dimensions] RandomizedLP solves ddd -dimensional linear programs in O(n)O(n)O(n) expected time for constant ddd . Why is "linear time" misleading here?
The constant factor Cd=O(cdd!)C_d = O(c^d d!)Cd=O(cdd!) grows so fast that the algorithm is useful only for small dimensions.
[Smallest Enclosing Discs] A robot arm with fixed base must reach a set of points on the floor. Where should the base go?
At the center of the smallest enclosing disc of the points. That point minimizes the maximum distance from the base to a point the arm must reach.
[Smallest Enclosing Discs] What is the smallest enclosing disc of a set PPP of nnn points in the plane?
The smallest disc that contains all points of PPP . It is unique.
[Smallest Enclosing Discs] Lemma 4.13. p1,…,pnp_1, \dots, p_np1,…,pn are points in random order, and DiD_iDi is the smallest enclosing disc of Pi={p1,…,pi}P_i = \{p_1, \dots, p_i\}Pi={p1,…,pi} . How does DiD_iDi relate to Di−1D_{i-1}Di−1 ?
If pi∈Di−1p_i \in D_{i-1}pi∈Di−1 , then Di=Di−1D_i = D_{i-1}Di=Di−1 ; otherwise pip_ipi lies on the boundary of DiD_iDi . pip_ipi is inside, so Di=Di−1D_i = D_{i-1}Di=Di−1 ; pi+1p_{i+1}pi+1 is outside and lies on the boundary of Di+1D_{i+1}Di+1 (dotted).
[Smallest Enclosing Discs] What are the steps of MiniDisc (P)(P)(P) (smallest enclosing disc of nnn points)?
Randomly permute PPP into p1,…,pnp_1, \dots, p_np1,…,pn ; D2D_2D2 = smallest disc enclosing p1,p2p_1, p_2p1,p2 ; for i=3,…,ni = 3, \dots, ni=3,…,n : if pi∈Di−1p_i \in D_{i-1}pi∈Di−1 keep Di=Di−1D_i = D_{i-1}Di=Di−1 , else DiD_iDi = MiniDiscWithPoint ({p1,…,pi−1},pi)(\{p_1, \dots, p_{i-1}\}, p_i)({p1,…,pi−1},pi) . MiniDiscWithPoint (P,q)(P, q)(P,q) computes the smallest disc enclosing PPP with qqq on its boundary.
[Smallest Enclosing Discs] How does MiniDiscWithPoint (P,q)(P, q)(P,q) compute the smallest disc enclosing PPP with qqq on its boundary?
Randomly permute PPP ; D1D_1D1 = smallest disc with qqq and p1p_1p1 on its boundary; for j=2,…,nj = 2, \dots, nj=2,…,n : if pj∈Dj−1p_j \in D_{j-1}pj∈Dj−1 keep it, else DjD_jDj = MiniDiscWith2Points ({p1,…,pj−1},pj,q)(\{p_1, \dots, p_{j-1}\}, p_j, q)({p1,…,pj−1},pj,q) . Same scheme as MiniDisc: a new point outside the current disc lies on the boundary of the new disc.
[Smallest Enclosing Discs] How does MiniDiscWith2Points (P,q1,q2)(P, q_1, q_2)(P,q1,q2) compute the smallest disc enclosing PPP with q1,q2q_1, q_2q1,q2 on its boundary, and why does it need no further subroutine?
D0D_0D0 = smallest disc with q1,q2q_1, q_2q1,q2 on its boundary; for each pkp_kpk outside Dk−1D_{k-1}Dk−1 , DkD_kDk = the disc with q1,q2,pkq_1, q_2, p_kq1,q2,pk on its boundary. Three boundary points determine the disc. Each iteration takes constant time, so O(n)O(n)O(n) time.
[Smallest Enclosing Discs] Lemma 4.14 (i). PPP is a set of points and RRR a set of points with P∩R=∅P \cap R = \emptysetP∩R=∅ . If some disc encloses PPP and has all points of RRR on its boundary, what can you say about the smallest such disc?
It is unique, denoted md(P,R)md(P, R)md(P,R) . For R=∅R = \emptysetR=∅ : the smallest enclosing disc of PPP is unique.
[Smallest Enclosing Discs] Lemma 4.14 (ii), (iii). md(P,R)md(P, R)md(P,R) is the smallest disc enclosing PPP with RRR on its boundary, and p∈Pp \in Pp∈P . What is md(P,R)md(P, R)md(P,R) if p∈md(P∖{p},R)p \in md(P \setminus \{p\}, R)p∈md(P∖{p},R) , and if not?
If p∈md(P∖{p},R)p \in md(P \setminus \{p\}, R)p∈md(P∖{p},R) : md(P,R)=md(P∖{p},R)md(P, R) = md(P \setminus \{p\}, R)md(P,R)=md(P∖{p},R) . Otherwise: md(P,R)=md(P∖{p},R∪{p})md(P, R) = md(P \setminus \{p\}, R \cup \{p\})md(P,R)=md(P∖{p},R∪{p}) . This shows that MiniDisc and its subroutines are correct.
[Smallest Enclosing Discs] D0,D1D_0, D_1D0,D1 are distinct discs of the same radius, with centers x0,x1x_0, x_1x0,x1 , both enclosing PPP and having RRR on their boundaries.How does the proof that the smallest such disc is unique find a smaller one?
Take the disc D(1/2)D(1/2)D(1/2) centered at the midpoint of x0x1x_0x_1x0x1 through the points of ∂D0∩∂D1\partial D_0 \cap \partial D_1∂D0∩∂D1 : it contains D0∩D1⊇PD_0 \cap D_1 \supseteq PD0∩D1⊇P , has RRR on its boundary, and has a smaller radius. D(λ)D(\lambda)D(λ) has center x(λ)=(1−λ)x0+λx1x(\lambda) = (1-\lambda)x_0 + \lambda x_1x(λ)=(1−λ)x0+λx1 and radius d(x(λ),z)d(x(\lambda), z)d(x(λ),z) for an intersection point zzz of ∂D0\partial D_0∂D0 and ∂D1\partial D_1∂D1 . R⊆∂D0∩∂D1R \s…