Shortest Paths in Line ArrangementsbyAnton LikhtarovB.Sc., The University of British Columbia, 2008A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)April 2020c© Anton Likhtarov, 2020The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Shortest Paths in Line Arrangementssubmitted by Anton Likhtarov in partial fulfillment of the requirements for thedegree of Master of Science in Computer Science.Examining Committee:William Evans, Associate Professor, Department of Computer Science, UBCSupervisorDavid Kirkpatrick, Professor Emeritus, Department of Computer Science, UBCSupervisory Committee MemberiiAbstractThe problem of finding a shortest Euclidean path in an arrangement of lines be-tween two points in the arrangement has been extensively studied; however, thebest known exact solution takes quadratic time, and it’s not known if a subquadratictime algorithm exists. While I did not succeed in improving these bounds, I exam-ined instead the problem of efficiently finding the approximate shortest path wherethe runtime depends on the bound of the relative error in the path length. I presentan algorithm for computing this approximate shortest path. The algorithm uses thegeometric structure of the arrangement; I show that certain lines are never usedby the shortest path, while other lines could be ignored without making the pathmuch longer. My work includes a number of lemmas that provide simple proofsfor related problems (such as shortest path in two intersecting pencils of lines), andcould have applications in future work on this problem.iiiLay SummaryImagine a city where every street is a straight line that extends to infinity in bothdirections. It is not known in general how quickly one can find the shortest possibleroute from one intersection to another in such a city.I present a general method of finding a good enough route between two inter-sections that’s in a certain sense guaranteed to not take too many calculations tofind. I also present a number of new geometric theorems that will help to thinkabout this problem in a new way, potentially leading to new discoveries in thefuture.ivPrefaceThis thesis is original, unpublished, independent work by the author, Anton Likhtarov.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Shortest paths in line arrangements . . . . . . . . . . . . . . . . . 11.2 History and related work . . . . . . . . . . . . . . . . . . . . . . 22 Exploring the arrangement geometry . . . . . . . . . . . . . . . . . 42.1 Definitions and observations . . . . . . . . . . . . . . . . . . . . 42.2 General position . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Urquhart’s theorem and related lemmas . . . . . . . . . . . . . . 62.3.1 Pencil Lemma . . . . . . . . . . . . . . . . . . . . . . . 72.3.2 Quadrilateral Lemma . . . . . . . . . . . . . . . . . . . . 102.4 Circle Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.5 Phantom-line Lemma . . . . . . . . . . . . . . . . . . . . . . . . 172.6 Two-lines Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 19vi3 The (1+ ε) approximation algorithm . . . . . . . . . . . . . . . . . 243.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Simple arrangements . . . . . . . . . . . . . . . . . . . . . . . . 253.3 Cycles in simple arrangements . . . . . . . . . . . . . . . . . . . 273.4 Arrangement quadrants . . . . . . . . . . . . . . . . . . . . . . . 293.5 Upper and lower quadrants . . . . . . . . . . . . . . . . . . . . . 293.6 S and T quadrants . . . . . . . . . . . . . . . . . . . . . . . . . . 303.6.1 Exponential subarrangements . . . . . . . . . . . . . . . 303.6.2 Line sequences . . . . . . . . . . . . . . . . . . . . . . . 323.6.3 Error-wedge Lemma . . . . . . . . . . . . . . . . . . . . 343.6.4 (1+ ε) approximation . . . . . . . . . . . . . . . . . . . 353.7 Approximation in the critical triangle . . . . . . . . . . . . . . . . 373.8 Running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47viiList of FiguresFigure 2.1 Urquhart’s theorem. . . . . . . . . . . . . . . . . . . . . . . 6Figure 2.2 An S–T path on two intersecting pencils of lines. The shortestpath would not use interior intersections. . . . . . . . . . . . 7Figure 2.3 Nested Ellipse Lemma. . . . . . . . . . . . . . . . . . . . . . 8Figure 2.4 Pencil Lemma. The path shown cannot be shortest in the ar-rangement. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Figure 2.5 Three nested ellipses through P. The ellipse with foci at S andV is inside the ellipse with foci at S and T , which is inside theellipse with foci at T and U . . . . . . . . . . . . . . . . . . . 9Figure 2.6 Lemma 2.3.4. . . . . . . . . . . . . . . . . . . . . . . . . . . 10Figure 2.7 Case 1: x is tangent to C . . . . . . . . . . . . . . . . . . . . . 11Figure 2.8 Case 2: x crosses C . . . . . . . . . . . . . . . . . . . . . . . 11Figure 2.9 Circle Lemma. No line intersects both C and the shortest path.S is not shown, but is somewhere within the shaded area. . . . 12Figure 2.10 First case: Z ∈4PQR. . . . . . . . . . . . . . . . . . . . . . 13Figure 2.11 Second case: Z /∈4PQR. Z is located within the shaded area. 14Figure 2.12 Case one: Z above c. . . . . . . . . . . . . . . . . . . . . . . 15Figure 2.13 Case two: d intersects b above, induction. . . . . . . . . . . . 15Figure 2.14 Case three: d intersects b below. Z can only appear in theshaded region, any line through Z that crosses C would alsocross C ′. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Figure 2.15 Phantom-line Lemma: the shortest path does not travel alongb in its direction. . . . . . . . . . . . . . . . . . . . . . . . . 17viiiFigure 2.16 Translating the phantom line b′. . . . . . . . . . . . . . . . . 18Figure 2.17 b′ intersects Z. Note that the direction of translation can change:z∩ x is on the opposite side of b′ compared to x∩ y. . . . . . . 19Figure 2.18 Y ′ lies on a. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Figure 2.19 X ′ lies on c. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Figure 2.20 A counterexample where a∩b /∈ Hull(S,T ). . . . . . . . . . . 20Figure 2.21 p visits a before travelling on b. . . . . . . . . . . . . . . . . 21Figure 2.22 If p travels on b before visiting a then rotating the arrangementand reversing the shortest path direction reduces to the first case. 21Figure 2.23 First case: z≤ e. y∩a /∈ DQ leads to a contradiction. . . . . . 22Figure 2.24 Second case: z > e. . . . . . . . . . . . . . . . . . . . . . . . 23Figure 3.1 Top row: an arrangement and its simple subarrangement. Bot-tom row: up-lines and down-lines of the simple subarrangement. 26Figure 3.2 A possible cycle between two cross lines and the boundary. . . 28Figure 3.3 The retrograde region around S and the unused cross line in-tersections. . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Figure 3.4 Arrangement quadrants. . . . . . . . . . . . . . . . . . . . . 29Figure 3.5 Case 1. Eliminating travel on b and c results in a shorter path. 30Figure 3.6 Case 2. If d > b, QD and DU give a shorter path. . . . . . . . 31Figure 3.7 Case 2. If d < b and a < c, AP and PB give a shorter path. . . 31Figure 3.8 A simple arrangement and its exponential subarrangement. Notethat the removed cross lines can still be used as bridge seg-ments to jump from boundary to boundary, but not to othercross lines. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32Figure 3.9 Error-wedge Lemma. . . . . . . . . . . . . . . . . . . . . . . 34Figure 3.10 d(U,V,P)< (1+ ε)d(U,W,P)≤ (1+ ε)|p′|. . . . . . . . . . 36Figure 3.11 (pi −α)/2 < ∂ (4PQR) < 3(pi −α). The upper bound holdsonly if α > pi/2. . . . . . . . . . . . . . . . . . . . . . . . . 38Figure 3.12 ∂ (4PQR)< 6ε∂ (4XYZ). . . . . . . . . . . . . . . . . . . . 39Figure 3.13 p last turns at Q in the critical triangle. . . . . . . . . . . . . . 40Figure 3.14 Parallel tangents. . . . . . . . . . . . . . . . . . . . . . . . . 41Figure 3.15 ∂ (4PQR)< εd(Q,V,X). . . . . . . . . . . . . . . . . . . . 41ixFigure 3.16 Any shortest A–B path that respects C must be at least as longas d(A,C,B) = d(A,D,B). . . . . . . . . . . . . . . . . . . . 42Figure 3.17 Induction step. d(A,X ,Y,B)≥ d(A,C,B). . . . . . . . . . . . 43xAcknowledgmentsI first would like to thank my advisor Will Evans for his never-ending patience andcareful guidance, especially during the times when the progress seemed impossi-ble.I would also like to thank my second reviewer David Kirkpatrick for his valu-able comments.Also I thank my friends Ralph Furman and Reza Zadeh for reviewing the slidesfor my thesis presentation and for their good-humored ribbing about not havinggraduated yet over the years.Finally, I thank my wife Stella—without her loving support and encouragementI might have never completed this thesis.xiChapter 1IntroductionThe shortest distance between twopoints is not a very interesting journey.— Rube Goldberg1.1 Shortest paths in line arrangementsWe consider the problem of finding a shortest path (using the Euclidean metric) inan arrangement of lines on a plane between two points in the arrangement.Given a finite set of lines A = {li} on a plane and two points S, T on somelines in A , the SHORTEST-PATH problem is the problem of finding the shortestpossible path p from S to T along the lines in A .Given also a real number ε < 1, the APPROXIMATE-SHORTEST-PATH problemis the problem of finding a path from S to T along the lines in A with length thatis at most (1+ ε) times the length of p.While these problems have been studied for some time, it’s still an open prob-lem to establish tight bounds on time complexity. The best known solution forSHORTEST-PATH has the time complexity O(n2), while the best known lowerbound is Ω(n logn).While we didn’t succeed in improving these bounds, our contributions are:1. We show a new approach for exploring the shortest path geometry, provingthe novel Circle Lemma, and exploring the connections to Urquhart’s The-1orem. We use these techniques to demonstrate a simple, geometric proofof the Pencil Lemma (the existing proofs due to Kavitha [13] and Hart [11]involve full parameterization and complicated algebraic manipulations).2. We present an algorithm for the APPROXIMATE-SHORTEST-PATH problemwith the time complexity of O(n logn+ ε−3 log(ε−1)n).1.2 History and related workThe earliest known treatment of this problem is by Davis in 1948 [4]. He showsthat certain lines will never be used by the shortest path.To obtain the naive upper bound, we could construct the entire O(n2) arrange-ment and then use Dijkstra’s shortest path algorithm for an overall time complexityof O(n2 logn). To improve on this, Henzinger et al. show how to construct theshortest path in planar graphs in O(n) time, bringing the overall time complexitydown to O(n2)[12]. In addition, an approach called “topological peeling”[2, 3] re-duces the space complexity to O(n). As far as we can tell, this is the best currentlyknown solution.On the other hand, the best known lower bound of Ω(n logn) follows fromthe reduction from the CONVEX-HULL-SIZE-VERIFICATION problem (“given npoints on a plane, is their convex hull of size n?”), which is known to be Ω(n logn)[15].Some restricted versions of the problem have also been studied. If the linesare restricted to only k unique orientations, the shortest path can be found in timeO(n+k2)[6]. If the arrangement is formed by two intersecting pencils of lines andwe’re interested in the shortest path between the corners of the resulting “grid”,the path is trivial and can be found in O(n) time [11, 13]. It’s interesting to notethat even this seemingly much simpler variant of the problem has been open forsome time, and when eventually solved both proofs involve full parameterizationand complicated algebraic manipulations. One of our contributions is a simplegeometric proof which we call the Pencil Lemma.The APPROXIMATE-SHORTEST-PATH can be solved in O(n logn) if ε = 1 (thatis, we want a factor of 2 approximation) [1].2Finally, Hart gives a short overview for an approximation algorithm with timecomplexity of O(n logn + (min{n,ε−2})ε−1 log(ε−1))[10], though the completealgorithm and proof was never published. We build on some of the ideas in thisoverview paper and present a complete approximation algorithm.3Chapter 2Exploring the arrangementgeometry2.1 Definitions and observationsWe assume that no line contains both S and T ; otherwise the shortest path is triv-ially found in O(n) time.We fix a coordinate system so that S = (−1,0) and T = (1,0).We use the notation d(A,B) for the length of the segment AB, and d(A,B,C) asa shortcut for d(A,B)+d(B,C) (similarly for any larger number of terms).Every line l induces a partition on the plane l∪ l+∪ l− where l+ and l− are theopen half-planes defined by l. A line l that separates S from T (that is, S and T arein different half-planes defined by l) is called a cross line; every other line is calledan exterior line.For every exterior line b, take the closed half-plane defined by b that containsboth S and T . The intersection of these half-planes is a convex, possibly unboundedregion that we denote Hull(S,T ). An exterior line that has a nonempty intersectionwith Hull(S,T ) is called a boundary line.It’s easy to see that if a shortest path intersects a line, the intersection is a closedsegment or a point. The shortest path will intersect every cross line, and will neverleave Hull(S,T ). Thus we can ignore any non-boundary exterior lines.A path is said to visit a line if it intersects with it. A path travels on a line if the4intersection is a positive length segment and not just a point.We will often need to explicitly state the direction that a path is travelling alonga given line. It’s trivial to see that a shortest path will only travel on lines on the up-per boundary of Hull(S,T ) in the clockwise direction from S to T —otherwise thepath would self-intersect, and we could obtain a shorter path. Similarly, a short-est path will only travel on lines on the lower boundary in the counterclockwisedirection from S to T .The shortest path can travel on a cross line in either direction. To make thediscussion clear, we replace each cross line with two coincident directed lines: anup-line with the positive y-direction of travel and a down-line with the negativey-direction of travel.Now that we have partitioned the arrangement into a set of upper boundary,lower boundary, up-, and down-lines, the possible direction of travel on each lineis unique.Observation 2.1.1. If a shortest path travels consecutively on lines x and then y,1. x is an upper boundary or an up-line if and only if y is an upper boundaryor a down-line.2. x is a lower boundary or a down-line if and only if y is a lower boundary oran up-line.Proof. Sketch. In each case, the negation would have the path cross some linetwice. For example, if x and y were both down-lines, then p would either have tocross x again after travelling on y or would have already crossed y before travellingon x.Finally, we have some notation to help us talk about line angles. An up-line a issaid to be steeper than an up-line b if the angle that the directed line a makes withthe directed line−→ST is larger than the angle that b makes with−→ST . We write b < a(b is less steep or shallower than a). We have a similar definition for down-lines.Intuitively, the path would often prefer a shallower line to get across Hull(S,T )faster.52.2 General positionFor the simplicity of the argument, we assume that the arrangement given is ingeneral position. By this we mean that no two lines are parallel; no three linesintersect at a single point; and S and T belong to exactly one line.Note that any arrangement can be perturbed slightly to be in general positionwithout changing the sequence of lines visited by a shortest path (with perhapsthe exception of adding a small segment of travel next to S or T if they happen tointersect more than one line). Unfortunately it is not known if we can compute thisperturbation quickly—the problem of finding if any three lines intersect at a pointbelongs to a class of “n2-hard problems”[7, 14].We believe that the argument can be adapted to drop the general position re-quirement, but we did not attempt to do so.2.3 Urquhart’s theorem and related lemmasThe following curious theorem has direct application to the problems we’re con-sidering.D ABB′C ′CFigure 2.1: Urquhart’s theorem.Theorem 2.3.1 (Stronger version of Urquhart’s Theorem [8]). If←−→ABB′1 and←−→AC′Care straight lines with←→BC and←−→B′C′ intersecting at D then1. d(A,B,D) = d(A,C′,D) if and only if d(A,B′,D) = d(A,C,D), and2. d(A,B,D)< d(A,C′,D) if and only if d(A,B′,D)< d(A,C,D).1We use←→AB for the line through the points A and B;−→AB for the directed line through A and B withthe direction of travel from A towards B; and AB for the closed line segment from A to B.6Pedoe attributes the theorem to L. M. Urquhart who “discovered it when con-sidering some of the fundamental concepts of the theory of special relativity” [17],though it appears that the history of the theorem and its proofs go back much fur-ther [5, 16]. Hajja has published two proofs of the theorem with some discussionof its history [8, 9].2.3.1 Pencil LemmaThe SHORTEST-PATH problem remained open even for the special case where thearrangement is formed by two intersecting pencils of lines (see Figure 2.2) untilsolved by Kavitha [13] and independently by Hart in 2003 [11].STFigure 2.2: An S–T path on two intersecting pencils of lines. The shortestpath would not use interior intersections.It turns out that the shortest path never uses the interior of the “distorted grid”in this case, and it’s sufficient to prove the case for the intersecting pencils of twoand three lines. We refer to this base case as the Pencil Lemma.We’re aware of two existing proofs. Kavitha [13] parameterizes the lengths ofcertain paths through the coordinates of the line intersections and differentiates theresulting functions to show that certain path length relationships must hold. Hart’sapproach [11] is similar but uses angles and trigonometry for the parameterizationinstead; it also uses Mathematica to simplify the resulting expressions. Neitherapproach seems to provide any geometric insight into the problem.We present a simpler geometric proof that only uses Urquhart’s Theorem andthe triangle inequality.7Lemma 2.3.2 (Nested Ellipse Lemma). For←−→PXY a straight line with X 6= Y andQ /∈←−→PXY, if d(Z,Q,X)≤ d(Z,P,X) then d(Z,Q,Y )< d(Z,P,Y ).Alternatively, the ellipse with foci Z and X is contained within the ellipse withfoci Z and Y if the ellipses coincide at P (see Figure 2.3).QZXPYFigure 2.3: Nested Ellipse Lemma.Proof.d(Z,P,Y ) = d(Z,P,X ,Y )≥ d(Z,Q,X ,Y )> d(Z,Q,Y ) by the triangle inequality.Lemma 2.3.3 (Pencil Lemma). Fix points S and T . For all points P, Q, and U ∈←→PS, a shortest S–T path on the arrangement {←→PS,←→PT,←→QS,←→QT,←→QU} does not usethe segment UV, where V =←→PT ∩←→QU, provided that no two lines are parallel.Proof. Let A =←→PS∩←→QT and B =←→PT ∩←→QS.If U /∈ SA then the path that uses UV would double-cross a line, and the re-sult holds, so assume U ∈ SA. The three possible paths from S to T have lengthsd(S,A,T ), d(S,B,T ), and d(S,U,V,T ).We show that min{d(S,A,T ), d(S,B,T )} < d(S,U,V,T ). It suffices to showthat if d(S,U,V,T ) ≤ d(S,B,T ) then d(S,A,T ) < d(S,U,V,T ), or equivalently ifd(S,U,V ) ≤ d(S,B,V ) then d(U,A,T ) < d(U,V,T )—in other words, if the path8PSQBVUATFigure 2.4: Pencil Lemma. The path shown cannot be shortest in the arrange-ment.that uses UV is better than the path through B then the path through A must bebetter still.PSVUQTFigure 2.5: Three nested ellipses through P. The ellipse with foci at S and Vis inside the ellipse with foci at S and T , which is inside the ellipse withfoci at T and U .Assume d(S,U,V )≤ d(S,B,V ).By Theorem 2.3.1, d(S,Q,V )≤ d(S,P,V ).By Lemma 2.3.2, taking X =V , Y = T , and Z = S, d(S,Q,T )< d(S,P,T ).By Lemma 2.3.2 again, taking X = S, Y =U , and Z =T , d(U,Q,T )< d(U,P,T ).Finally, by Theorem 2.3.1, d(U,A,T )< d(U,V,T ).Intuitively, there are three nested ellipses through P (see Figure 2.5), so it fol-lows that if Q is inside the innermost ellipse, it must also be inside the outermost9ellipse and the result follows.2.3.2 Quadrilateral LemmaWe’ll make use of the following simple geometric lemma, which is closely relatedto Urquhart’s Theorem. Using this lemma, we show that a given shortest pathcannot travel on some line segments in the arrangement since there would be away to shorten the path.Lemma 2.3.4. Let a, b, and c be three lines tangent to a circle C so that b∩ c andC are in different half-planes defined by a.Let P = a∩b, Q = b∩ c, and R = a∩ c.Let x be a line so that U = x∩a ∈ PR and V = x∩ c ∈ RQ.1. If x is tangent to C then d(U,P,Q) = d(U,V,Q).2. If x crosses C then d(U,P,Q)> d(U,V,Q).3. If x does not cross C then d(U,P,Q)< d(U,V,Q).CabcPQRxUVFigure 2.6: Lemma 2.3.4.Proof. Case 1. x is tangent to C .Let A, B, C, X be the points where a, b, c, and x respectively coincide with C(see Figure 2.7).10PQRUVBXACFigure 2.7: Case 1: x is tangent to C .We have:d(C,Q) = d(B,Q) d(C,V ) = d(X ,V )d(A,P) = d(B,P) d(A,U) = d(X ,U)d(C,Q) = d(C,V,Q) = d(X ,V,Q) = d(X ,U,V,Q) = d(A,U,V,Q)d(B,Q) = d(B,P,Q) = d(A,P,Q) = d(A,U,P,Q)So d(A,U,V,Q) = d(A,U,P,Q), and thus d(U,V,Q) = d(U,P,Q).Case 2. x crosses C (see Figure 2.8).PQRUVBACxV ′Figure 2.8: Case 2: x crosses C .Let←→UV ′ be the line through U tangent to C that does not coincide with a.By Case 1, d(U,P,Q) = d(U,V ′,Q) = d(U,V ′,V,Q)> d(U,V,Q) (by the triangleinequality).Case 3. x does not cross C .11As in Case 2, Let←→UV ′ be the line through U tangent to C that does not coincidewith a. By Case 1, d(U,P,Q) = d(U,V ′,Q) < d(U,V,V ′,Q) = d(U,V,Q) (by thetriangle inequality).2.4 Circle LemmaThe Circle Lemma shows that travelling along any cross line imposes significantrestrictions on any other lines crossed by the shortest path.Lemma 2.4.1 (Circle Lemma). Let C be the unique circle tangent to lines a, b,and c that lies in the half-plane defined by a that does not contain b∩ c.If b separates S from T and the shortest path from S to T travels consecutivelyon a, b, and c, then the arrangement contains no lines that intersect both C andthe shortest path from S to T .CabcTPQRxZFigure 2.9: Circle Lemma. No line intersects both C and the shortest path. Sis not shown, but is somewhere within the shaded area.Proof. We first establish some common notation and then prove the lemma in mul-tiple parts.Let P = a∩b, Q = b∩ c, R = a∩ c. Suppose for the sake of contradiction thatthere’s a line x that intersects both C and the shortest path from S to T at a point Z(see Figure 2.9).Part 1. Z is located in the shortest subpath from S to Q.12We first observe that Z must be inside the same quadrant defined by the lines band c that contains the circle C ; in all other cases the supposed shortest path fromS to Q would double cross some line which is a contradiction.ZabcCPRQUxVWFigure 2.10: First case: Z ∈4PQR.First, consider the case where Z ∈4PQR (see Figure 2.10).Let V = a∩ x and W = c∩ x. It must be that W ∈ RQ, otherwise x would havecrossed the shortest path twice, which is a contradiction. It follows that V ∈ RPsince x crosses C .If δ is the length of the shortest subpath from Z to Q, we haved(Q,W,V )< d(Q,P,V )≤ δ +d(Z,V ) (by Lemma 2.3.4)d(Q,W,Z,V ) = d(Q,W,V )< δ +d(Z,V )d(Q,W,Z)< δ ,which is a contradiction.The other case is where Z /∈4PQR (see Figure 2.11).Let d be the line on which the shortest path arrives at U , and V ∈ d be somepoint so that VU is part of the shortest path.Let W = d ∩ c. It must be that W ∈ RQ, otherwise d would have crosses theshortest path twice.Note also that d does not cross C since otherwise d(U,W,Q)< d(U,P,Q) (byLemma 2.3.4), which would be a contradiction.13abcCPRQUVWC′dFigure 2.11: Second case: Z /∈4PQR. Z is located within the shaded area.We apply the Circle Lemma by induction on the number of line segments inthe shortest path, considering the shortest path from S′ = Z to T ′ = Q, and takinga′ = d, b′ = a (which separates Z from Q), and c′ = b. Since the shortest path fromZ to Q has at least one segment fewer than the shortest path from S to T and isfinite, the induction must eventually end in the first case of the proof.Let C ′ be the circle in the inductive step. We have that no line through Zcrosses C ′. As a corollary, Z is located in the bounded region defined by the linesa, b, and the circle C ′.Any line through Z that crosses C must also cross C ′, since C and C ′ sharethe tangents a and b, and C contacts these tangents at points that are further awayfrom P than C ′ does (by virtue of another tangent d of C ′ not crossing C ).So no lines through Z can cross C .Part 2. Z is located in the shortest subpath from Q to T .Since b separates S from T and the shortest path cannot cross a or b twice,Z must be in the quadrant defined by a and b that is opposite of the quadrantcontaining C .Consider first the case where Z ∈ c or Z is in the same half-plane defined by cas the circle C (see Figure 2.12).Let W = x∩ a. Note that W /∈ RP, otherwise x would cross PQ, which is part14abcPRQZCxVdWFigure 2.12: Case one: Z above c.of the shortest path, a contradiction. Let d be the unique tangent line of C throughZ that intersects PQ, and let V = d∩PQ (d might not exist in the arrangement).Let δ be the length of the shortest subpath from P to Z. By Lemma 2.3.4,d(P,W,Z)< d(P,V,Z)≤ δ , which is a contradiction.The other case is where Z is in the half-plane defined by c that does not containthe circle C . Let d be the line on which the path leaves c. We have two subcases.CabcdPQVZRC′Figure 2.13: Case two: d intersects b above, induction.First, consider the case where d∩b is in the same half-plane defined by c as the15circle C (see Figure 2.13). Note that d does not cross C since otherwise we wouldhave (by Lemma 2.3.4) d(P,a∩d,V )< d(P,Q,V ), a contradiction.We apply the Circle Lemma by induction on the number of line segments inthe shortest path, considering the shortest path from S′ = P to T ′ = Z, and takinga′ = b, b′ = c (which separates P from Z), and c′ = d. Since the shortest path fromP to Z has at least one segment fewer than the shortest path from S to T and isfinite, the induction must eventually end in one of the other cases of the proof.Let C ′ be the circle in the inductive step. We have that no line through Zcrosses C ′.Since Z is in the quadrant defined by b and c that is opposite to the quadrantcontaining C and C ′, any line through Z that crosses C must also cross C ′, becauseC and C ′ share the tangents b and c, and C ′ contacts these tangents at points thatare further away from Q than C does (by virtue of another tangent d of C ′ notcrossing C ).So no lines through Z cross C in this case.For the final case we have d ∩ b in the half-plane defined by c that does notcontain the circle C (see Figure 2.14).CabcdPQVRC′xZFigure 2.14: Case three: d intersects b below. Z can only appear in the shadedregion, any line through Z that crosses C would also cross C ′.16We again apply the Circle Lemma by induction, considering the reversed short-est path from Z to P, and taking a′ = d, b′ = c (which separates P from Z), andc′ = b. In this case, we’re guaranteed to end up in the Part 1 of the proof.We get that in the inductive step no lines through Z cross the unique circle C ′tangent to lines d, c, and b that lies in the half-plane defined by d that does notcontain Q. We also get that the subpath from P to Z does not cross C ′, so Z mustbe in the bounded region defined by the lines b, c, and the circle C ′. Since b andc are tangent to both C and C ′, it follows that any line through Z that crosses Cmust also cross C ′.Therefore no lines through Z cross C and this completes the proof.2.5 Phantom-line LemmaThis lemma allows us to conclude that the shortest path does not travel on certainline segments that are surrounded by “better” lines on each side.Lemma 2.5.1 (Phantom-line Lemma). Let a, b, and c be three directed lines sothat the shortest path from S to T travels through points A ∈ a and C ∈ c so that Cis to the right of a and A is to the left of c.If b separates S from T and A from C, and b makes a positive angle with botha and c then the shortest path does not travel along b in the direction of the line(note: the shortest path may travel along a or c with or against the respectivedirections).a bcACSTFigure 2.15: Phantom-line Lemma: the shortest path does not travel along bin its direction.Proof. Suppose that the shortest path p does travel along a line segment XY ∈ b.17XY must be to the right of a and to the left of c in its entirety, otherwise the pathwould double cross either a or c.Let x be the line on which the shortest path arrives at X and y be the line onwhich the shortest path leaves Y .Since b separates S from T , the shortest path travels along x and y on oppositesides of b. We will introduce a new line b′ to the arrangement which is initiallycoincident with b (the “phantom line” of the lemma’s name). We will translate b′in steps, always maintaining (1) b′ separates S from T and A from C; (2) using b′makes for a shorter path; and (3) after every step the shortest path (with b′) hasfewer segments in it, allowing us to use induction.a bcxXyYb′X ′Y ′Figure 2.16: Translating the phantom line b′.We continuously translate b′ towards x∩y. Note that as long as b′ doesn’t crossx∩ y or any vertices of the path, using b′ instead of b results in a shorter path. LetX ′ = x∩b′ and Y ′ = y∩b′ (see Figure 2.16).One of the following will happen as we’re translating b′:1. b′ intersects a vertex Z on the shortest path (see Figure 2.17). If the path visitsZ after leaving X′Y ′, we can obtain a shorter path p′ by replacing the subpathfrom X ′ to Z with X′Z and using x∩z as the new direction of translation for b′,where z is the line on which the path leaves Z. Similarly, if Z is visited beforearriving at X′Y ′, we replace the subpath from Z to Y ′ with ZY ′ and translatetowards z∩y. The new path has fewer line segments, and the argument musteventually terminate in one of the other cases. (Note: we cannot use a morestraightforward induction. While applying the lemma by induction tells usthat there’s a shorter path in the new arrangement that does not travel alongb′ in the direction of the line, it could travel along b′ in the opposite direction,which would not allow us to conclude that the same shortest path exists in18the original arrangement.)acxX ′yY ′b′ZabxX ′b′Z⇒zFigure 2.17: b′ intersects Z. Note that the direction of translation can change:z∩ x is on the opposite side of b′ compared to x∩ y.2. b′ intersects x∩ y. In this case travel on b′ has shrunk to a single point. Weobtained a shorter path that does not rely on b′, which is a contradiction.3. X′Y ′ intersects a (see Figure 2.18). Since b (and thus b′) makes a positiveangle with a, we must have Y ′ ∈ a happen first as we’re translating b′. Wereplace the path from A to Y ′ with AY ′ to obtain a shorter path that does notuse b′, a contradiction.acxX ′yY ′Ab′Figure 2.18: Y ′ lies on a.4. X′Y ′ intersects c (see Figure 2.19). Since b (and thus b′) makes a positiveangle with c, we must have X ′ ∈ c happen first as we’re translating b′. Wereplace the path from X ′ to C with X′C to obtain a shorter path that does notuse b′, a contradiction.2.6 Two-lines LemmaThe following lemma allows us to only consider arrangements where no two up-lines (or down-lines) intersect within Hull(S,T ).19acxX ′ yY ′CFigure 2.19: X ′ lies on c.Lemma 2.6.1 (Two-lines Lemma). If a < b are two up-lines (down-lines) thatintersect within Hull(S,T ), then no shortest path travels on b.Note that the condition that a and b intersect within Hull(S,T ) is required sinceit is possible to construct a counterexample if a∩b 6∈ Hull(S,T ) (see Figure 2.20).S THull(S, T )abFigure 2.20: A counterexample where a∩b /∈ Hull(S,T ).Proof. We will prove the lemma for down-lines; the proof for up-lines is similar.Suppose, for the sake of contradiction, that there is a shortest path p that travelson b. Let BE be the segment of travel on b. We must have a∩b /∈ BE, otherwise thepath would double-cross a, so there are two possibilities: either p visits a beforeBE—that is, BE and T are in the same half-plane defined by a (see Figure 2.21);or p visits a after BE—that is, BE and S are in the same half-plane defined by a.In the second case, consider the rotation of the arrangement through pi , with Sand T swapped; the direction of travel along p is reversed and a and b are down-lines in the rotated arrangement. p visits a before BE in the rotated arrangement,so we have reduced this case to the first one (see Figure 2.22).So we assume that p visits a before BE.20S TabFigure 2.21: p visits a before travelling on b.S TabSTabFigure 2.22: If p travels on b before visiting a then rotating the arrangementand reversing the shortest path direction reduces to the first case.We further assume that b is the last down-line that p travels on so that b in-tersects one or more down-lines a′ where a′ < b, a′ ∩ b ∈ Hull(S,T ), and p vis-its a′ before travelling on b, and we let a be the last a′ that p travels on. LetQ = a∩b ∈ Hull(S,T ), and let A be the point at which p leaves a.Let x be the line on which p travels after leaving b. Note that since E = x∩b ∈BQ, x cannot be a boundary line, otherwise Q /∈ Hull(S,T ), so x is an up-line.Let y be the line on which p travels after leaving x. Note that y must exist: if parrives directly to T on x, then T is at an intersection of x and the boundary, whichwe disallow by the general position assumption.Finally, let z be the line on which the path arrives to b (so that z∩b = B). Lete =−→AB (which might not exist in the arrangement). Let further C = e∩y, D = a∩x,F = x∩ y, Z = z∩ y.Consider first the case where z≤ e.Claim 1. y∩a ∈ DQ.Proof. Let y′ =←→FQ, C′ = e∩ y′, and Z′ = z∩ y′ (see Figure 2.23).By Lemma 2.3.3 we havemin{d(A,D,F),d(A,C′,F)}< d(A,B,E,F)21baxyzBAeTSCDEFQy′C ′ZZ ′Figure 2.23: First case: z≤ e. y∩a /∈ DQ leads to a contradiction.Note also that d(A,B,E,F) ≤ δ where δ is the length of the actual subpathfrom A to F .It can’t be that d(A,D,F) < d(A,B,E,F) since then shortest path would havetravelled on AD and DF, so we must have d(A,C′,F) < d(A,B,E,F) and thusd(B,C′,F)< d(B,E,F).Since by assumption z≤ e, we also have d(B,Z′,F)≤ d(B,C′,F).If y∩ a /∈ DQ then also d(B,Z,F) < d(B,Z′,F), so the path travelling on BZand ZF would be shorter than p which travels on BE and EF, a contradiction.By Observation 2.1.1, since x is an up-line, y is either an upper boundary or adown-line. Since y∩a ∈ DQ and Q ∈ Hull(S,T ), y cannot be a boundary line. Soy must be a down-line.Note that we have p travelling on y after visiting b, b< y, and b∩y∈Hull(S,T ).This contradicts the assumption we made that b was the last line with these prop-erties visited by p.Consider now the case where z > e (see Figure 2.24). Let w be the line onwhich p travels before arriving to z. Note that w 6= a, otherwise we would havez = e.By Observation 2.1.1, and the fact that the travel on both w and z intersects the22b azBAeTSQwFigure 2.24: Second case: z > e.interior of4ABQ, we conclude that w is a down-line and z is an up-line; otherwise,if z is an upper boundary line then A /∈Hull(S,T ), and if w is a lower boundary linethen either A /∈ Hull(S,T ) or Q /∈ Hull(S,T ).Note also that we must have w∩a∈ AQ and w∩b /∈ BQ —otherwise we wouldhave w∩b ∈ Hull(S,T ) and w < b, and we would have chosen w over a since thepath travels on w after visiting a.Consider the shortest subpath from S to B, and note that w∩a ∈Hull(S,B). Byinduction on the number of segments in the shortest path, we have that the subpathwould not travel on w, a contradiction.23Chapter 3The (1+ ε) approximationalgorithm3.1 OverviewWe present a high level summary of the algorithm steps here. The algorithm worksby ignoring certain lines and intersections for the purpose of finding the shortestpath. The resulting graph is small enough to make a dent in the time complexity,while at the same time we take care to ignore lines and intersections that couldhave made the shortest path only moderately shorter.The approach borrows ideas from the overview paper by Hart [10], in particularthe overall high level approach of constructing the unimodal sequence of angles andthe insight that further elimination of lines by making the angles get exponentiallysmall allows for an asymptotic reduction in running time while keeping the errorin the path small. The full algorithm was never published so we don’t know howHart tackled some of the issues we cover here (in particular the approximation onthe critical triangle). As far as we know the Circle Lemma and its application hereis novel.The subsequent sections fill in the details, prove that the algorithm is correct(that is, if the shortest path uses the lines or intersections that the algorithm ig-nores, it would be shorter by a factor of at most (1+ ε)), and show that the timecomplexity is O(n logn+ ε−3 log(ε−1)n).241. Partition the arrangement A into the set E of exterior lines and the set C ofcross lines (that is, the lines that cross ST).2. Construct the set of up-lines U and the set of down-lines D by constructingthe two directed lines for every line in C.3. Construct Hull(S,T ) by intersecting the half-planes defined by the lines in E(this can be done e.g. using the CONVEX-HULL algorithm in the dual plane).Construct two ordered sets of boundary lines BU (the upper boundary) andBL (the lower boundary) by taking those lines in E that define the upper andthe lower chains of Hull(S,T ) respectively.4. Remove certain cross lines from U and D by constructing the simple subar-rangement (see Section 3.2).5. Remove cross line to cross line intersections within:upper and lower quadrants (see Section 3.5);the exponential subarrangement with ε ′= 3√1+ ε−1 (see Section 3.6.1);and the critical S and T triangles, taking the same ε ′ as above for both(see Section 3.7).6. Construct the resulting arrangement graph. Note that the graph is directedand acyclic, except for the trivial subgraphs around S and T (see Section 3.3).7. Use topological sort to find the shortest path.Note that we have three approximation steps applied one after another (expo-nential subarrangement and the two critical triangles) for a factor of (1+ ε ′) each.The total approximation factor is (1+ ε ′)3 = (1+ ε) as desired.3.2 Simple arrangementsAn arrangement of lines A containing points S and T is simple if1. Every exterior line is a boundary line—no lines are outside Hull(S,T ).25S T S TS T S TucdcFigure 3.1: Top row: an arrangement and its simple subarrangement. Bottomrow: up-lines and down-lines of the simple subarrangement.2. No two up-lines (down-lines) intersect within Hull(S,T ).We define a total order on all up-lines (down-lines): a <∗ b iff any path fromS to T that does not leave Hull(S,T ) crosses a before b. We label the up-lines {u1,u2, . . . ,un}where i< j ⇐⇒ ui <∗ u j. Similarly for the down-lines{d1,d2, . . . ,dm}.3. There’s a unimodal ordering of steepness for all up-lines (down-lines). Thatis, u1 > u2 > .. . > uc−1 > uc < uc+1 < .. . < un (similarly for down-lines).We call the shallowest up-line uc the critical up-line (similarly for the criticaldown-line).Note: the c in uc and dc is used for convenience and not meant as a specificindex (which would imply that uc and dc are at exactly the same position intheir respective lists).Any arrangementA has a simple subarrangement constructed by the followingprocedure:1. Discard the lines outside of Hull(S,T ).2. Order the up-lines by the intersections along the lower boundary to obtain26the list {u1,u2, . . . ,un}. We will construct the new set of up-lines U startingwith {uc}:For every ui in the sequence (uc−1,uc−2, . . . ,u1):Discard from U any lines {uk|ui < uk}; then add ui to U .For every ui in the sequence (uc+1,uc+2, . . . ,un):Discard from U any lines {uk|k > c;ui < uk}; then add ui to U .3. Construct the new set of down-lines in a similar fashion.Note that we can construct the simple subarrangement in time O(n logn) whichis dominated by the time required to construct Hull(S,T ) and to order the intersec-tions with the boundary; if we use a stack to construct U , we would only everdiscard lines from the top of the stack for a total of O(n).The fact that it’s easy to construct and the following result allow us to lookexclusively at simple arrangements:Theorem 3.2.1. IfAs is a simple subarrangement ofA and p is a shortest path inAs, then p is a shortest path in A .Proof. We show that no lines removed in the construction of the subarrangementwould have been used by the shortest path.The lines outside of Hull(S,T ) are not used by the shortest path.Consider a line uk discarded fromU during the construction procedure becauseui < uk for some i < k < c. If ui∩uk ∈ Hull(S,T ) then the shortest path would nottravel on uk by Lemma 2.6.1. Otherwise the shortest path would not travel on ukby Lemma 2.5.1, as any segment of travel on uk would be located between two lesssteep lines: ui and uc.The proof for the case c < k < i and for the down-lines is similar.3.3 Cycles in simple arrangementsIt’s possible for the directed graph induced by a simple arrangement to containcycles in it (see Figure 3.2) if an up-line and a down-line cross at an angle larger27Sd1u1TFigure 3.2: A possible cycle between two cross lines and the boundary.than pi . Note that the shortest path would not use the intersection between thesetwo lines by Observation 2.1.1.Due to the unimodal ordering of line angles, these “retrograde” regions arecontiguous, are located adjacent to S or T and are easy to compute (see Figure 3.3).Since we can ignore the interior intersections for the purpose of finding the shortestpath, the subgraph contains O(n) vertices (all of them on the boundary), and theshortest path to each vertex is found in O(n logn).Sd1d2 d3u3u2u1Figure 3.3: The retrograde region around S and the unused cross line inter-sections.283.4 Arrangement quadrantsIt’s useful to partition Hull(S,T ) into regions formed by the lines uc and dc1 (seeFigure 3.4). The region below dc and above uc is called the S quadrant; the regionabove dc and below uc is called the T quadrant. The region above both lines iscalled the upper quadrant, while the region below both lines is called the lowerquadrant.It is easy to compute the shortest path in the upper and lower quadrants: weshow that the shortest path does not turn from one cross line to another.The S and T quadrants require additional approximation steps, detailed below.S TdcucSTUpperLowerFigure 3.4: Arrangement quadrants.3.5 Upper and lower quadrantsTheorem 3.5.1. A shortest path p in a simple arrangement does not turn fromone cross line to another after leaving dc and before arriving to uc (that is, in theupper quadrant) or after leaving uc and before arriving to dc (that is, in the lowerquadrant).Proof. Suppose, without loss of generality, that p leaves dc, turns at a point Q froma cross line b to a cross line c, and then arrives at uc. Let a be the line on which parrives at b and d be the line on which p leaves c. Let A = a∩ b, B = c∩ d, andP = a∩d.1uc and dc might not intersect within Hull(S,T ), in which case the upper or lower quadrant couldbe empty.29Case 1. b is an up-line and c is a down-line (see Figure 3.5).QabcducdcABPFigure 3.5: Case 1. Eliminating travel on b and c results in a shorter path.It must be that a < c since if a > c then also a > dc and by Lemma 2.5.1 theshortest path would not travel on a.Similarly, it must be that d < b.Consider the quadrilateral AQBP. Since a < c and d < b we have d(A,P,B)<d(A,Q,B), so we obtained a shorter path, a contradiction.Case 2. b is a down-line and c is an up-line. Let C = d ∩ uc and D = b∩ uc.By Case 1, we must conclude that d is a boundary line—otherwise the path wouldmake a cross line to cross line turn at B. Let U be the point at which the path arrivesat uc; it must be that U ∈ DC.Consider the quadrilateral QBCD. If d > b then d(Q,D,U) < d(Q,B,U) ≤|pQU | where pQU is the actual subpath from Q to U , so we must conclude thatd < b (see Figure 3.6).By a similar argument we conclude that a < c.Now as in the first case, considering the quadrilateral AQBP we see that d(A,P,B)<d(A,Q,B) and we have a contradiction (see Figure 3.7).3.6 S and T quadrants3.6.1 Exponential subarrangementsAny simple arrangementA has an exponential subarrangementAε defined below.30QbcducdcBCDUFigure 3.6: Case 2. If d > b, QD and DU give a shorter path.QbcducdcBPaAFigure 3.7: Case 2. If d < b and a < c, AP and PB give a shorter path.Let A be a simple arrangement. As before, let the up-lines be labeled as{u1,u2, . . . ,un} where i < j ⇐⇒ ui <∗ u j with uc the critical up-line. Similarlyfor the down-lines and dc.Let σi (τi) be the angle that the directed line ui makes with the line through S(line through T ) considered as a directed line with a positive y-coordinate travel. Ifui makes a negative angle with the line through S (line through T ), then the shortestpath would not use it by Lemma 2.5.1, so we assume that σi,τi ∈ (0,pi). Note thatfor steep up-lines, σi and τi are small. We will use the notation ∠ui = σi.Aε is constructed by the following procedure:1. Construct the new set of up-lines Uε starting with {uc}:For every ui in the sequence (uc−1,uc−2, . . . ,u1):31S T S TFigure 3.8: A simple arrangement and its exponential subarrangement. Notethat the removed cross lines can still be used as bridge segments to jumpfrom boundary to boundary, but not to other cross lines.Let u j be the last up-line added to Uε . Add ui to Uε if i = 1 orσ j/σi−1 > 1+ ε/2.For every ui in the sequence (uc+1,uc+2, . . . ,un):Let u j be the last up-line added to Uε . Add ui to Uε if i = n orτ j/τi+1 > 1+ ε/2.2. Construct the new set of down-lines in a similar fashion.3. AugmentAε with a set of bridge segments. For every up-line and down-lineinA not already included, we include the line segment connecting the lowerboundary to the upper. The shortest path is not allowed to turn from a crossline to a bridge segment or vice versa, or from one bridge segment to another.Another way to view an exponential subarrangement is as keeping all the linesin the arrangement and removing some cross line to cross line intersections (wecall these cross lines bridge segments).It’s easy to see that we can construct Aε in time O(n logn), the time needed toorder the lines by σi and τi. The intention is to get rid of lines that are close to eachother and have similar angles. We show that this does not significantly increase thelength of the shortest path.3.6.2 Line sequencesIt will help for the discussion below to develop a language when we talk about thesequence of line types traversed by a shortest path.32We will use the symbols u, d, U, D to refer to an arbitrary up-, down-, upperboundary, and lower boundary line respectively. If we need to label a specific line,we will use u1,d2, etc.A sequence of symbols is valid if it follows the following rules:1. u or U can be immediately followed by d or U2. d or D can be immediately followed by u or DFor example, udDDuUUdu is a valid sequence, while uddUD is not.We can identify any shortest path p with a string of the above symbols corre-sponding to each line that p travels on in order from S to T . By Observation 2.1.1,any shortest path will map to a valid sequence.A valid sequence is exact if no u is immediately followed by d and vice versa.For example, dDDuUUd is an exact sequence, while dDDudDu is valid but not ex-act. Paths that map to exact sequences travel along the boundary or cross Hull(S,T )using bridge segments without turning from one cross line to another. Any suchpath would be completely preserved in an exponential subarrangement, thus thename.An upper subsequence of a given sequence is the subsequence of all u and Uelements with their relative order preserved. Similarly, a lower subsequence is thesubsequence of all d and D elements. A reordering is the sequence obtained byconcatenating the upper subsequence with the lower subsequence. For example,a sequence U1d2D3D4u5U6U7d8 has an upper subsequence U1u5U6U7 and a lowersubsequence d2D3D4d8; its reordering is the sequence U1u5U6U7d2D3D4d8.We will talk about the reordering of a path in the sense of taking the individualline segments that the path travels on and reordering them into another contiguouspoly-line (by translating the line segments while preserving the angles) accordingto the path’s sequence reordering. Note that a path reordering creates a poly-linefrom the original path’s starting to its ending point of the same length as the originalpath.Finally we have an observation about the line angles in the sequence whichmirrors the unimodal angle ordering in simple arrangements.33Observation 3.6.1. Let p be a shortest path in a simple arrangement. If p travelson an up-line u j before reaching uc, then for all i < j in the upper subsequence ofp, li > u j (li could be an upper boundary line or an up-line).Similarly for the down-lines.Proof. If there’s a line li < u j where i < j then by Lemma 2.5.1 the path would nothave travelled on u j (any travel segment is between the shallower lines li and uc),so it must be that li > u j.3.6.3 Error-wedge LemmaWe will make use of the following lemma, which allows us to approximate shortestpath segments with travel on two lines:αβABCFigure 3.9: Error-wedge Lemma.Lemma 3.6.2 (Error-wedge Lemma). Let 4ABC be a triangle with α = ∠BACand β = ∠ABC. If α/β < ε/2 then d(A,B,C)< (1+ ε)d(A,C).Proof. First, we need the fact that f (β ) = β (cos(β )+1)sin(β ) < 2 for β ∈ (0,pi). We omitfull details, but this is easily shown since limβ→0+ f (β ) = 2, limβ→pi− f (β ) = 0,and ddβ f (β )< 0 for 0 < β < pi .Using further the fact that d(A,B) = d(A,C)cos(α)+ d(B,C)cos(β ), as wellas the law of sines d(A,C)sin(α) = d(B,C)sin(β ), we have34d(A,B,C)d(A,C)=d(A,C)cos(α)+d(B,C)cos(β )+d(B,C)d(A,C)=d(A,C)cos(α)+d(B,C)(cos(β )+1)d(A,C)=d(A,C)cos(α)+d(A,C) sin(α)sin(β ) (cos(β )+1)d(A,C)=cos(α)+sin(α)sin(β )(cos(β )+1) =cos(α)+sin(α)β(β (cos(β )+1)sin(β ))<1+αβ(β (cos(β )+1)sin(β ))<1+αβ2 <1+ ε3.6.4 (1+ ε) approximationLemma 3.6.3. Given a simple arrangement A , let Aε be its exponential subar-rangement, and P a point on an up-line, down-line, or a boundary line in the Squadrant of Aε . If p is a shortest S–P path in A and q is a shortest S–P path inAε , then |q|< (1+ ε)|p|.Proof. We prove this by induction on (nu,nd)—the number of up-lines and down-lines in Aε respectively that any shortest S–P path will intersect.Without loss of generality, let P be a point on a down-line or an upper boundaryline dk in Aε .Let um be the last up-line inAε crossed by p (we take the boundary line throughS to be um if no such up-line exists). Let um+1 be the next up-line in Aε , whichmust exist and um > um+1 ≥ uc since P is in the S quadrant and p does not cross uc.35Let U be the point where p leaves um and let p′ be the U–P subpath of p.By induction, the S–U subpath is well-approximated, so it’s sufficient to showthat the U–P subpath is also well-approximated. We assume that p′ travels on atleast two lines—otherwise the single line must be um or an upper boundary line byObservation 2.1.1, and we apply induction by removing dk.Consider the maximal contiguous exact suffix s of p′ ending at P, excludingany initial u or d in the suffix. By construction, every line in s is in Aε since wekeep all boundary lines and bridge segments.Let Q be the point where p′ enters s. If s is nonempty, Q must lie on a boundaryline and by the inductive assumption we can well-approximate the shortest S–Qpath, which does not intersect dk and thus intersects fewer lines than the shortestS–P path. So assume that s is empty—that is, Q = P.Note that the assumption of travel on at least two lines and the fact that s isempty implies that p′ ends with either ud or du.If A has no up-lines between um and um+1 then u in the sequence must be um,and the only possibility is that p′ travels on um followed by dk. We remove dk andproceed by induction.Otherwise, there’s at least one up-line between um and um+1 that we skippedduring the construction of Aε , and we must have σm+1/σm < 1+ ε/2.UPdkumum+1p′R(p′)XSVWFigure 3.10: d(U,V,P)< (1+ ε)d(U,W,P)≤ (1+ ε)|p′|.Consider the reordering of p′, and let X be the point at the end of the uppersubsequence in the reordering. We would like to show that (1) dk separates U from36X , and that (2) all lines in the upper subsequence of p are more steep than um+1.These two facts will allow the application of Lemma 3.6.2.Since p′ ends with either ud or du, its upper subsequence ends with u, and itslower subsequence ends with d. By Observation 3.6.1, we immediately have (2);and, since all lines in its lower subsequence are steeper than dk, we have (1) byconvexity of the reordering.Let V = um∩dk, and let W be the point where the reordering of p′ first crossesdk. Since d(U,W,P) ≤ |p′| and WP ∈ dk, it’s sufficient to show that travel onUV ∈ um followed by VW ∈ dk well-approximates p′.Note that by (1) W must be within the upper subsequence of the reordering. By(2) we have ∠VUW < σm+1−σm, and we have∠VUW∠UVW <σm+1−σmσm +δk<σm+1−σmσm=σm+1σm−1 < ε2Finally by Lemma 3.6.2 we have d(U,V,W ) + d(W,P) < (1 + ε)d(U,W ) +d(W,P)< (1+ ε)d(U,W,P)≤ (1+ ε)|p′|.3.7 Approximation in the critical triangleLet i and j be the largest indices so that ∠ui < min{pi/4,ε/(12 + 6ε)∠uc} and∠d j < min{pi/4,ε/(12+6ε)∠dc}. We call the triangle defined by ui, d j, and s thecritical triangle and show that there’s a particularly simple approximation for thepart of the shortest path that traverses it.Note that to get the full approximation we need to apply the lemma belowtwice (for the critical triangle next to S and T ) for a total approximation factor of(1+ ε)2. Taking this together with another factor of (1+ ε) from the exponentialsubarrangement, we would use ε ′ = 3√1+ ε−1 in the complete algorithm instead.Lemma 3.7.1. Given a unit circle U , let a, b, and c be three lines tangent to it sothat Q = a∩b is not in the same half-plane defined by c as U . Let P = a∩ c andR = b∩ c. Let α = ∠PQR ∈ (0,pi).Then ∂ (4PQR)> (pi−α)/2. (∂ (x) is the perimeter of x)If α > pi/2 then also ∂ (4PQR)< 3(pi−α).37PQbcURaα1Figure 3.11: (pi −α)/2 < ∂ (4PQR) < 3(pi −α). The upper bound holdsonly if α > pi/2.Proof. For the lower bound, using the Taylor series expansion, we have for 0 <x < pi/2:sin(x)> x− x3/6Let γ = (pi−α)/2 < pi/2.∂ (4PQR) = 2tan(γ) = 2 sin(γ)cos(γ)>2γ− γ3/61> γ = (pi−α)/2For the upper bound, using the Taylor series expansions again, we have for0 < x < pi/4sin(x)< x− x3/6+ x5/5! < x+ x5/5!,andcos(x)> 1− x2/2 > 1− (pi/4)2/2 > 17/25.Let γ = (pi−α)/2 < pi/4.∂ (4PQR) = 2tan(γ) = 2 sin(γ)cos(γ)<2γ+ γ5/5!17/25< 22γ17/25= 100/17γ < 6γ = 3(pi−α)Corollary 3.7.1.1. Given a circle C , let a, b, and c be three lines tangent to it so38that X = a∩ b is not in the same half-plane defined by c as C . Let Y = a∩ c andZ = b∩ c.Let further d and e be two lines also tangent to C so that Q = d ∩ e is not inthe same half-plane defined by c as C .If∠RQP> pi/2 and (pi−∠RQP)< ε(pi−∠YXZ), then ∂ (4PQR)< 6ε∂ (4XYZ).PQdbcCR XaYZeFigure 3.12: ∂ (4PQR)< 6ε∂ (4XYZ).Proof. Since we’re only concerned about ratios, we can assume that C is a unitcircle without loss of generality.By Lemma 3.7.1, ∂ (4PQR)< 3(pi−∠RQP) and ∂ (4XYZ)> (pi−∠YXZ)/2.We have∂ (4PQR)< 3(pi−∠RQP)<3ε(pi−∠YXZ) = 6ε(pi−∠YXZ)/2 <6ε∂ (4XYZ)Lemma 3.7.2 (Tangent-bound Lemma). Let E be a simple arrangement. If p isa shortest path in E and q is a shortest path in E but with the restriction that noturns are allowed between two cross lines within the critical triangle, then |q| <(1+ ε)|p|.Proof. If p doesn’t turn from a cross line to a cross line within the critical trianglethen we’re done.39TPQducucdcsCARBFigure 3.13: p last turns at Q in the critical triangle.Otherwise, let Q be the point at the last such turn when traversing p from Stowards T . Without loss of generality, let’s assume that p arrives at Q on an up-lineu and leaves Q on a down-line d, and also that p arrives to u on a line c (whichcould be a down-line or a lower boundary line by Observation 2.1.1); let P = c∩u.We would like to apply the Lemma 2.4.1 to the shortest path from S to T trav-elling on the lines c, u (which is a cross line by assumption and thus separates Sfrom T ), and d. It must be that c > d since otherwise c < d > dc and the shortestpath would not use d by Lemma 2.5.1. So this fixes the circle in the Circle Lemmadefinition to be the unique circle C tangent to c, u, and d that lies in the half-planedefined by c that does not contain Q. Let also R = c∩d.We have that s (the line through S) does not cross C .So it must be that s intersects d within the closed segment RQ. Let A = s∩d ∈RQ and B = s∩u.We also get that no lines crossed by the shortest path after leaving Q crossC—in particular, uc and dc do not cross C .Let the approximate path q be the path obtained from p by replacing the exist-ing subpath from S to Q with the two segments SA and AQ. Note that q does notturn from a cross line to a cross line within the critical triangle. We claim that qprovides the required approximation.Let u′c be a line parallel to uc and tangent to C (we choose the tangent that putsuc and C in the different half-planes defined by u′c). We define d′c in a similar way.Let V = u∩d′c, X = d′c∩u′c, Y = d′c∩ c, and Z = u′c∩ c (see Figure 3.14).40TPQducucdcCRVXYZFigure 3.14: Parallel tangents.Let δ = |q|− |p|. It’s sufficient to show that δ < ε|p|, which we prove in a fewsteps:1. δ ≤ ∂ (4PQR)This follows from the facts that δ ≤ ∂ (4AQB) and ∂ (4AQB)≤ ∂ (4PQR)(the perimeters are equal if s is tangent to C ).PQducCR VXsαZYFigure 3.15: ∂ (4PQR)< εd(Q,V,X).2. ∂ (4PQR)< εd(Q,V,X)Proof. Since ∠RPQ = ∠u+α and ∠PRQ = ∠d−α , where α is the anglebetween c and s, we have pi −∠RQP = ∠PRQ +∠RPQ = ∠u +∠d (seeFigure 3.15).41Similarly, pi−∠YXZ = ∠uc +∠dc.Since u and d are in the critical triangle, we have ∠u +∠d < ε/(12 +6ε)(∠uc +∠ud) and ∠u+∠d < pi/2. We havepi−∠RQP < ε12+6ε(pi−∠YXZ) ∠RQP > pi/2∂ (4PQR)< ε2+ ε∂ (4XYZ) (By Corollary 3.7.1.1)∂ (4XYZ)−∂ (4PQR) = 2d(Q,V,X)2+ εε∂ (4PQR)−∂ (4PQR)< 2d(Q,V,X)1ε∂ (4PQR)< d(Q,V,X)3. d(Q,V,X)≤ |p|This follows immediately from the following intuitively obvious claim:Given a circle C , let b1 and b2 be the tangents of C through B. Let A bea point in the region bounded by b1, b2, and C , and let a1 and a2 be thetangents of C through A.Let ACBD be the quadrilateral defined by the intersections of the four tan-gents. Note that by Lemma 2.3.4, d(A,C,B) = d(A,D,B).If p is a shortest A–B path that doesn’t travel on any lines that cross C then|p| ≥ d(A,C,B) = d(A,D,B) (see Figure 3.16).Aa1C C Bb1a2b2DFigure 3.16: Any shortest A–B path that respects C must be at least as longas d(A,C,B) = d(A,D,B).42Proof. If A ∈ b1 or A ∈ b2, the result follows since d(A,C,B) = d(A,B), andany shortest path is at least as long as d(A,B).If p only travels on a single segment AB, then it must be that A∈ b1 or A∈ b2(otherwise←→AB would cross C ), and the result follows as above.Otherwise, let AX be the first segment of p. If this segment intersects b1 orb2 we take X to be this point of intersection instead.Let x1 and x2 be the tangents of C through X , and let XY BZ be the quadri-lateral defined by the four tangents b1, b2, x1, and x2. By Lemma 2.3.4,d(X ,Y,B) = d(X ,Z,B) (see Figure 3.17).Aa1C C Bb1a2b2DXYZx1x2Figure 3.17: Induction step. d(A,X ,Y,B)≥ d(A,C,B).By induction on the number of line segments in p, |p| = d(A,X)+ |pXB| ≥d(A,X)+d(X ,Y,B) (note that the induction must terminate in the case abovewhen p crosses b1 or b2).Since←→AX does not cross C , then either C ∈ YB or D∈ ZB. Since d(X ,Y,B) =d(X ,Z,B), we can assume without loss of generality that C ∈ YB.We have d(A,X) + d(X ,Y,B) = d(A,X) + d(X ,Y,C,B) = d(A,X ,Y,C) +d(C,B)≥ d(A,C,B) by the triangle inequality.Finally, putting the steps together we get δ < ε|p| and the shortest path is well-approximated by q.3.8 Running timeOrdering the lines by angle and choosing the lines that are part of the exponentialsubarrangement can be done in O(n logn) time.43The graph induced by the arrangement will contain O(n) edges, but we do notneed to consider turns between cross lines within the critical triangles or the upperand lower regions so we can save on the number of vertices.We will use ε ′ where (1+ ε ′)3 = (1+ ε) for the exponential subarrangementand the critical triangle definitions to simplify the discussion.Let’s first calculate the number of up-lines inside and outside the critical trian-gle in the S quadrant. Suppose that the total number of up-lines in the S quadrant isk and the critical triangle includes the lines u1, . . . , ui with ∠ui < x <∠ui+1, wherex = min{pi/4,(ε ′/(12+6ε ′))∠uc}.By the exponential subarrangement construction, ∠u j/∠u j−2 ≥ 1+ε ′/2 for all3≤ j ≤ c. We have∠u j∠u j−2m=∠u j∠u j−2× ∠u j−2∠u j−4 ×·· ·×∠u j−2m+2∠u j−2m≥ (1+ ε ′/2)m∠ui < (ε ′/(12+6ε ′))∠uc∠uc∠ui> 12/ε ′+6∠uc∠ui≥ ∠uc∠uc−2m ≥ (1+ ε′/2)m > 12/ε ′+6m >log(12/ε ′+6)log(1+ ε ′/2)In other words, if m is at least this large, the remaining k−m lines are in thecritical triangle. In total, we have m2+2m(k−m) = 2mk−m2 vertices in the graphin the S quadrant.The T quadrant is similar, and the top and bottom quadrants do not contributeany vertices. Asymptotically, since k = O(n), we get |V |= O(mn).1. m = O(1/e′ log(1/e′))Let φ ′= 1/ε ′, so that log(12/ε ′+6)/ log(1+ε ′/2)= log(12φ ′+6)/ log(1+441/(2φ ′)). If g(φ ′) = O( f (φ ′)) then there are C, φ ′0 so that for all φ ′ > φ ′o:log(12φ ′+6)log(1+1/(2φ ′))<C f (φ ′)log(12φ ′+6)<C f (φ ′) log(1+1/(2φ ′))12φ ′+6 < eC f (φ′) log(1+1/(2φ ′)) exponentiate12φ ′+6 < φ ′Cφ′ log(1+1/(2φ ′)) take f (x) = x logxUsing log(1+ x) = x− x2/2+ x3/3− . . .:12φ ′+6 < φ ′Cφ′(1/(2φ ′)−(1/(2φ ′))2/2+(1/(2φ ′))3/3−...)12φ ′+6 < φ ′C(1/2−1/(2φ′)+(1/(3·8φ ′2)−...)Which holds for φ ′ and C sufficiently large to make the exponent greater thanone, so log(12φ ′+6)/ log(1+1/(2φ ′)) = O(φ ′ logφ ′).2. 1/ε ′ = O(1/ 3√ε). Since ε ′ = 3√1+ ε−1, we haveφ ′ =13√1+1/φ −1φ ′ =3√φ3√φ +1− 3√φ multiplying through by3√φφ ′ = O( 3√φ)3. It follows that m = O(ε−3 log(ε−1)).Since the graph is directed and acyclic2, we can simply use the O(n) topologicalsort to find the shortest path, and the overall time complexity isO(n logn)+O(|V |) = O(n logn+mn) =O(n logn+ ε−3 log(ε−1)n)2except for the trivial subgraph, where the shortest path is also found in O(n logn)—see Sec-tion 3.345Chapter 4Future workThe problem and some of our proofs suggest a number of possible directions toexplore.The Circle Lemma seems to be fundamental in understanding the problem.We believe that other results, like the Phantom Lemma and the Two-lines Lemmacould be restated as corollaries of the Circle Lemma. The Circle Lemma reducesthe shortest path problem to a potentially simpler combinatorial problem of findingif certain lines intersect certain circles.The fact that the best known solution is O(n2) suggests a possibility that thisproblem falls into a class of “3SUM-hard” problems [7][14]. It is also not knownif any of these problems can be solved in sub-O(n2) time.Other avenues to explore is finding a sub-O(n2) exact solution on a restrictedproblem (for example, with bounds on minimum differences between line anglesor distances between intersections in the arrangement), or a sub-O(n logn) approx-imation.46Bibliography[1] P. Bose, W. S. Evans, D. G. Kirkpatrick, M. McAllister, and J. Snoeyink.Approximating shortest paths in arrangements of lines. In CCCG,volume 96, pages 143–148. Citeseer, 1996. → page 2[2] D. Z. Chen, S. Luan, and J. Xu. Topological peeling and implementation. InInternational Symposium on Algorithms and Computation, pages 454–466.Springer, 2001. → page 2[3] D. Z. Chen, O. Daescu, X. S. Hu, and J. Xu. Finding an optimal path withoutgrowing the tree. Journal of Algorithms, 49(1):13–41, 2003. → page 2[4] C. Davis. The short-cut problem. The American Mathematical Monthly, 55(3):147–150, 1948. → page 2[5] M. A. Deakin. Yet more on urquhart’s theorem. The AustralianMathematical Society Gazette, pages 3–3, 1997. → page 7[6] D. Eppstein and D. Hart. Shortest paths in an arrangement with k lineorientations. In Symposium on Discrete Algorithms: Proceedings of thetenth annual ACM-SIAM symposium on Discrete algorithms, volume 17,pages 310–316, 1999. → page 2[7] A. Gajentaan and M. H. Overmars. On a class of o(n2) problems incomputational geometry. Computational geometry, 5(3):165–185, 1995. →pages 6, 46[8] M. Hajja. An elementary proof of the most “elementary” theorem ofeuclidean geometry. J. Geometry Graphics, 8:17–22, 2004. → pages 6, 7[9] M. Hajja. A very short and simple proof of “the most elementary theorem”of euclidean geometry. In Forum Geom, volume 6, pages 167–169, 2006. →page 747[10] D. Hart. Approximating the shortest path in line arrangements. In CCCG,pages 105–108. Citeseer, 2001. → pages 3, 24[11] D. Hart. Shortest paths in two intersecting pencils of lines. In CCCG, pages166–169, 2003. → pages 2, 7[12] M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-pathalgorithms for planar graphs. Journal of Computer and System Sciences, 55(1):3–23, 1997. → page 2[13] T. Kavitha and K. R. Varadarajan. On shortest paths in line arrangements. InCCCG, pages 170–173, 2003. → pages 2, 7[14] J. King. A survey of 3SUM-hard problems. Not published, 2004. → pages6, 46[15] D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm?SIAM journal on computing, 15(1):287–299, 1986. → page 2[16] A. Michael. Deakin. the provenance of urquhart’s theorem. Austral. Math.Soc. Gaz, 8(1):26–28, 1981. → page 7[17] D. Pedoe. The most “elementary” theorem of euclidean geometry.Mathematics Magazine, 49(1):40–42, 1976. → page 748
You may notice some images loading slow across the Open Collections website. Thank you for your patience as we rebuild the cache to make images load faster.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Shortest paths in line arrangements
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Shortest paths in line arrangements Likhtarov, Anton 2020
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Shortest paths in line arrangements |
Creator |
Likhtarov, Anton |
Publisher | University of British Columbia |
Date Issued | 2020 |
Description | The problem of finding a shortest Euclidean path in an arrangement of lines between two points in the arrangement has been extensively studied; however, the best known exact solution takes quadratic time, and it’s not known if a subquadratic time algorithm exists. While I did not succeed in improving these bounds, I examined instead the problem of efficiently finding the approximate shortest path where the runtime depends on the bound of the relative error in the path length. I present an algorithm for computing this approximate shortest path. The algorithm uses the geometric structure of the arrangement; I show that certain lines are never used by the shortest path, while other lines could be ignored without making the path much longer. My work includes a number of lemmas that provide simple proofs for related problems (such as shortest path in two intersecting pencils of lines), and could have applications in future work on this problem. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2020-04-14 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0389809 |
URI | http://hdl.handle.net/2429/74003 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2020-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2020_may_likhtarov_anton.pdf [ 1.05MB ]
- Metadata
- JSON: 24-1.0389809.json
- JSON-LD: 24-1.0389809-ld.json
- RDF/XML (Pretty): 24-1.0389809-rdf.xml
- RDF/JSON: 24-1.0389809-rdf.json
- Turtle: 24-1.0389809-turtle.txt
- N-Triples: 24-1.0389809-rdf-ntriples.txt
- Original Record: 24-1.0389809-source.json
- Full Text
- 24-1.0389809-fulltext.txt
- Citation
- 24-1.0389809.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0389809/manifest