Ch.6: Point Location
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 6.1. Point Location and Trapezoidal Maps 6.2. A Randomized Incremental Algorithm 6.3. Dealing with Degenerate Cases 6.4. A Tail Estimate 6.5. Notes and Comments
84 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Point Location] What is a point location query?
Given a map (a planar subdivision) and a query point qqq by its coordinates, find the region of the map containing qqq . e.g. the point at longitude 5°6′ east, latitude 52°3′ north lies in the Netherlands.
[Point Location] Why do applications of point location (a ship's electronic map of currents, a GIS showing the country under the mouse pointer) need a preprocessed data structure, rather than searching the map for each query?
Queries come with high frequency and must be answered fast (in real time, as the ship or the mouse moves). So the map is preprocessed once and stored in a structure that answers each query quickly.
[Point Location and Trapezoidal Maps] What is the planar point location problem for a planar subdivision S\mathcal{S}S with nnn edges?
Store S\mathcal{S}S so that, given a query point qqq , the face of S\mathcal{S}S containing qqq can be reported. If qqq lies on an edge or coincides with a vertex, the query reports that instead.
[Point Location and Trapezoidal Maps] How is the simple slab data structure for point location in a planar subdivision S\mathcal{S}S built?
Vertical lines through all vertices cut the plane into slabs; per slab, an array of the edges crossing it, sorted top to bottom. Plus a sorted array of the vertices' xxx -coordinates. Each edge in a slab is labelled with the face of S\mathcal{S}S immediately above it inside the slab.
[Point Location and Trapezoidal Maps] Why can the edges of a planar subdivision that intersect one slab (the region between two consecutive vertical lines through vertices) be sorted from top to bottom?
No vertex lies inside the slab, so every such edge crosses the slab completely, and edges don't cross each other. So every region between two consecutive edges in the slab belongs to a single face.
[Point Location and Trapezoidal Maps] Slab structure: vertical lines through all vertices of a planar subdivision S\mathcal{S}S cut the plane into slabs; per slab, a sorted array of the edges crossing it, each labelled with the face above it.How is a query point qqq answered, and in what time ( nnn = number of edges)?
Binary search on xxx for the slab, then binary search in that slab's array for the edge directly below qqq : O(logn)O(\log n)O(logn) . The edge's label is the face containing qqq ; no edge below qqq means the unbounded face. The arrays have length at most 2n2n2n (vertices) and nnn (edges in one slab).
[Point Location and Trapezoidal Maps] Slab structure: vertical lines through all vertices of a planar subdivision S\mathcal{S}S cut the plane into slabs; per slab, a sorted array of the edges crossing it.What is the elementary operation of the binary search inside a slab?
Given a segment sss and a point qqq whose vertical line intersects sss : does qqq lie above sss , below sss , or on sss ?
[Point Location and Trapezoidal Maps] Slab structure: vertical lines through all vertices of a planar subdivision S\mathcal{S}S with nnn edges cut the plane into slabs; per slab, a sorted array of the edges crossing it.What is its worst-case storage, and why is the bound attained?
O(n2)\boldsymbol{O(n^2)}O(n2) : O(n)O(n)O(n) slabs, each array O(n)O(n)O(n) , and there are subdivisions where n/4n/4n/4 slabs are each crossed by n/4n/4n/4 edges. Even in practice the storage is likely around O(nn)O(n\sqrt{n})O(nn) : useless for large maps.
[Point Location and Trapezoidal Maps] When is a subdivision S′\mathcal{S}'S′ a refinement of a subdivision S\mathcal{S}S , and why does that help point location?
Every face of S′\mathcal{S}'S′ lies completely in one face of S\mathcal{S}S , so the face f′∈S′f' \in \mathcal{S}'f′∈S′ containing qqq tells the face f∈Sf \in \mathcal{S}f∈S containing qqq . The slab structure does point location in a refinement (edges plus vertical lines through all vertices) whose complexity can be quadratic. The trapezoidal map is a refinement of size O(n)O(n)O(n) .
[Point Location and Trapezoidal Maps] When are two line segments in the plane non-crossing?
Their intersection is empty or a common endpoint. The edges of any planar subdivision are non-crossing.
[Point Location and Trapezoidal Maps] For trapezoidal maps of a set SSS of non-crossing segments, the book adds a large axis-parallel bounding box RRR containing all of SSS . Why is this harmless for point location in a subdivision?
A query point outside RRR always lies in the unbounded face. RRR removes the unbounded trapezoid-like faces at the boundary of the scene.
[Point Location and Trapezoidal Maps] In this chapter, when is a set SSS of line segments in general position?
Non-crossing, enclosed in a bounding box RRR , and no two distinct endpoints have the same xxx -coordinate. So there are no vertical segments. Unrealistic (vertical edges and shared xxx -coordinates are common in practice), but the general case is handled later by a shear transformation.
[Point Location and Trapezoidal Maps] How is the trapezoidal map T(S)\mathcal{T}(S)T(S) of a set SSS of segments in general position (in a bounding box RRR ) defined?
Draw an upper and a lower vertical extension from every endpoint, each stopping at a segment of SSS or the boundary of RRR . T(S)\mathcal{T}(S)T(S) is the subdivision induced by SSS , RRR and these extensions.
[Point Location and Trapezoidal Maps] The trapezoidal map of a set of segments is also called its vertical decomposition or trapezoidal decomposition.
[Point Location and Trapezoidal Maps] What is a side of a face in a trapezoidal map T(S)\mathcal{T}(S)T(S) ?
A segment of maximal length contained in the face's boundary, i.e. a union of adjacent collinear edges of T(S)\mathcal{T}(S)T(S) . A face can have more edges than sides.
[Point Location and Trapezoidal Maps] SSS is a set of line segments in general position. How many vertical and non-vertical sides does each face of the trapezoidal map T(S)\mathcal{T}(S)T(S) have?
One or two vertical sides, and exactly two non-vertical sides. So every face is a trapezoid or a triangle (a trapezoid with one degenerate edge of length zero).
[Point Location and Trapezoidal Maps] Why is every face fff of a trapezoidal map T(S)\mathcal{T}(S)T(S) convex?
Every corner has interior angle at most 180°. Vertical extensions remove reflex angles at segment endpoints, angles where an extension abuts a segment are at most 180°, and the corners of RRR are 90°.Segments are non-crossing, so every corner of fff is one of these three kinds.
[Point Location and Trapezoidal Maps] Every face fff of a trapezoidal map T(S)\mathcal{T}(S)T(S) is convex, and every non-vertical side of fff lies on a segment of SSS or an edge of the bounding box RRR .Why can't fff have more than two non-vertical sides?
Two adjacent ones would meet in a segment endpoint, and its vertical extension separates them. With more than two non-vertical sides, two adjacent ones both bound fff from above (or both from below); being on non-crossing segments, they meet in a segment endpoint.Contradiction. Convexity gives at most two vertical sides; boundedness gives at least one vertical and at least two non-vertical sides.
[Point Location and Trapezoidal Maps] For a trapezoid Δ\DeltaΔ of a trapezoidal map T(S)\mathcal{T}(S)T(S) , what are top(Δ)\mathit{top}(\Delta)top(Δ) and bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) ?
The segment of SSS (or edge of RRR ) bounding Δ\DeltaΔ from above, and the one bounding it from below.
[Point Location and Trapezoidal Maps] SSS is in general position and Δ\DeltaΔ is a trapezoid of T(S)\mathcal{T}(S)T(S) . What are the five possible cases for the left side of Δ\DeltaΔ ?
(a) a point, (b) and (c) one vertical extension, (d) two vertical extensions, (e) the left edge of RRR . (a) the common left endpoint of top(Δ)\mathit{top}(\Delta)top(Δ) and bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) ; (b) the lower extension of the left endpoint of top(Δ)\mathit{top}(\Delta)top(Δ) ; (c) the upper extension of the left endpoint of bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) ; (d) the upper and lower extensions of the right endpoint of a third segment. Case (e) occurs only for the…
[Point Location and Trapezoidal Maps] For a trapezoid Δ\DeltaΔ of a trapezoidal map T(S)\mathcal{T}(S)T(S) , what is leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) ?
The segment endpoint defining the left side of Δ\DeltaΔ : the left endpoint of top(Δ)\mathit{top}(\Delta)top(Δ) or bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) , or the right endpoint of a third segment. The left side lies on the vertical extensions of leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) (or is that point, when degenerate). For the leftmost trapezoid, leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) is the lower left corner of RRR . rightp(Δ)\mathit{rightp}(\Delta)rightp(Δ) is symmetric.
[Point Location and Trapezoidal Maps] Which four items uniquely determine a trapezoid Δ\DeltaΔ of a trapezoidal map?
top(Δ),bottom(Δ),leftp(Δ),rightp(Δ)\boldsymbol{\mathit{top}(\Delta), \mathit{bottom}(\Delta), \mathit{leftp}(\Delta), \mathit{rightp}(\Delta)}top(Δ),bottom(Δ),leftp(Δ),rightp(Δ) The segments above and below, and the endpoints defining the left and right sides. Δ\DeltaΔ is said to be defined by them.
[Point Location and Trapezoidal Maps] SSS is a set of nnn line segments in general position. At most how many vertices and how many trapezoids does the trapezoidal map T(S)\mathcal{T}(S)T(S) have?
At most 6n+4\boldsymbol{6n + 4}6n+4 vertices and 3n+1\boldsymbol{3n + 1}3n+1 trapezoids. So T(S)\mathcal{T}(S)T(S) has linear complexity, unlike the refinement by vertical lines through all endpoints.
[Point Location and Trapezoidal Maps] Why does the trapezoidal map of nnn segments in general position have at most 6n+46n + 46n+4 vertices?
4+2n+2(2n)\boldsymbol{4 + 2n + 2(2n)}4+2n+2(2n) : the 4 corners of RRR , the 2n2n2n endpoints, and where the 2 extensions of each endpoint end.
[Point Location and Trapezoidal Maps] Why does the trapezoidal map of nnn segments in general position have at most 3n+13n + 13n+1 trapezoids?
Count by leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) : the lower left corner of RRR is leftp\mathit{leftp}leftp of exactly one trapezoid, a right endpoint of at most one, a left endpoint of at most two. 1+n+2n1 + n + 2n1+n+2n . A left endpoint of sss serves the trapezoid above sss and the one below sss , with the convention that in the degenerate case (a) leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) is the left endpoint of bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) .
[Point Location and Trapezoidal Maps] When are two trapezoids Δ,Δ′\Delta, \Delta'Δ,Δ′ of a trapezoidal map adjacent, and how many trapezoids can be adjacent to one trapezoid?
They meet along a vertical edge. In general position, at most four; otherwise arbitrarily many. Shaded trapezoids are adjacent to Δ\DeltaΔ . (i) general position; (ii) many endpoints on one vertical line.
[Point Location and Trapezoidal Maps] Δ′\Delta'Δ′ is adjacent to a trapezoid Δ\DeltaΔ along the left vertical edge of Δ\DeltaΔ . When is Δ′\Delta'Δ′ the upper left neighbor, and when the lower left neighbor of Δ\DeltaΔ ?
Upper left neighbor if top(Δ′)=top(Δ)\mathit{top}(\Delta') = \mathit{top}(\Delta)top(Δ′)=top(Δ) ; lower left neighbor if bottom(Δ′)=bottom(Δ)\mathit{bottom}(\Delta') = \mathit{bottom}(\Delta)bottom(Δ′)=bottom(Δ) . Upper and lower right neighbors are defined symmetrically.
[Point Location and Trapezoidal Maps] For each case (a) to (d) of the left side of a trapezoid Δ\DeltaΔ , which left neighbors (upper, lower) does Δ\DeltaΔ have?
(a) none, (b) lower only, (c) upper only, (d) both. In (b), top(Δ)\mathit{top}(\Delta)top(Δ) starts at the left side, so no trapezoid to the left shares it; similarly for bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) in (c). The leftmost trapezoid (left side on RRR ) has no left neighbors either.
[Point Location and Trapezoidal Maps] What does the book's specialized structure for a trapezoidal map T(S)\mathcal{T}(S)T(S) store, instead of a doubly-connected edge list?
A record per segment and endpoint of SSS , and a record per trapezoid with pointers to top(Δ)\mathit{top}(\Delta)top(Δ) , bottom(Δ)\mathit{bottom}(\Delta)bottom(Δ) , leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) , rightp(Δ)\mathit{rightp}(\Delta)rightp(Δ) and its at most four neighbors. No records for edges or vertices of T(S)\mathcal{T}(S)T(S) . The coordinates of Δ\DeltaΔ aren't stored, but follow in O(1)O(1)O(1) time from those four pointers.
[A Randomized Incremental Algorithm] Why is the trapezoidal map for point location built by a randomized incremental algorithm rather than by a plane sweep?
A sweep would build the map, but not a data structure for point location queries in it. The randomized incremental algorithm builds both together.
[A Randomized Incremental Algorithm] What is the search structure D\mathcal{D}D for a trapezoidal map T(S)\mathcal{T}(S)T(S) ?
A DAG with one root, one leaf per trapezoid, and inner nodes that are xxx -nodes (an endpoint) or yyy -nodes (a segment). Inner nodes have out-degree 2. Each trapezoid points to its leaf and each leaf to its trapezoid.
[A Randomized Incremental Algorithm] How does a query with a point qqq proceed in the search structure D\mathcal{D}D for a trapezoidal map?
From the root to a leaf: at an xxx -node, is qqq left or right of the vertical line through its endpoint; at a yyy -node, is qqq above or below its segment. The leaf reached is the trapezoid containing qqq . Whenever the query reaches a yyy -node, the vertical line through qqq intersects that node's segment, so the test makes sense.
[A Randomized Incremental Algorithm] qqq lies right of p2p_2p2 , left of q1q_1q1 , below s1s_1s1 and above s2s_2s2 . Which path does the query for qqq take, and which leaf does it reach? (White: xxx -nodes; grey: yyy -nodes.)
p1p_1p1 (right), q1q_1q1 (left), s1s_1s1 (below), p2p_2p2 (right), s2s_2s2 (above): leaf DDD .
[A Randomized Incremental Algorithm] Why does the algorithm building the trapezoidal map and its search structure insert the segments in a random order?
The order determines the structure, and some orders are bad (quadratic size, linear query time). A random order gives a good structure in expectation, without needing to find a good order.So the algorithm is randomized incremental, as for linear programming.
[A Randomized Incremental Algorithm] What are the steps of Algorithm TrapezoidalMap( SSS ) for a set SSS of nnn non-crossing segments?
Bounding box, random permutation, then insert the segments one by one, updating both T\mathcal{T}T and D\mathcal{D}D . 1. Build a bounding box RRR ; initialize T\mathcal{T}T and D\mathcal{D}D for it. 2. Take a random permutation s1,…,sns_1, \dots, s_ns1,…,sn . 3. For each sis_isi : find the trapezoids Δ0,…,Δk\Delta_0, \dots, \Delta_kΔ0,…,Δk properly intersected by sis_isi ; replace them in T\mathcal{T}T by the new trapezoids; replace their leaves in D\mathcal{D}D by new leaves, linked in…
[A Randomized Incremental Algorithm] What is the loop invariant of the randomized incremental algorithm for trapezoidal maps (with Si={s1,…,si}S_i = \{s_1, \dots, s_i\}Si={s1,…,si} ), and how is it initialized?
T\mathcal{T}T is the trapezoidal map of SiS_iSi and D\mathcal{D}D is a valid search structure for T\mathcal{T}T . Initially T(∅)\mathcal{T}(\emptyset)T(∅) is the single trapezoid RRR , and D\mathcal{D}D is a single leaf for it. Correctness of the algorithm follows directly from this invariant.
[A Randomized Incremental Algorithm] Inserting a segment sis_isi into a trapezoidal map T(Si−1)\mathcal{T}(S_{i-1})T(Si−1) : which trapezoids of T(Si−1)\mathcal{T}(S_{i-1})T(Si−1) disappear from T(Si)\mathcal{T}(S_i)T(Si) ?
Exactly those intersected by sis_isi .
[A Randomized Incremental Algorithm] Inserting a segment sis_isi with left endpoint ppp into a trapezoidal map T(Si−1)\mathcal{T}(S_{i-1})T(Si−1) : how does the algorithm find the first intersected trapezoid Δ0\Delta_0Δ0 ?
By a point location query with ppp in the current search structure D\mathcal{D}D , which is a search structure for T(Si−1)\mathcal{T}(S_{i-1})T(Si−1) . If ppp is new, general position puts ppp in the interior of Δ0\Delta_0Δ0 .
[A Randomized Incremental Algorithm] FollowSegment. Δ0,Δ1,…,Δk\Delta_0, \Delta_1, \dots, \Delta_kΔ0,Δ1,…,Δk are the trapezoids intersected by a new segment sis_isi , from left to right. Given Δj\Delta_jΔj , how is Δj+1\Delta_{j+1}Δj+1 found?
If rightp(Δj)\mathit{rightp}(\Delta_j)rightp(Δj) lies above sis_isi , Δj+1\Delta_{j+1}Δj+1 is the lower right neighbor of Δj\Delta_jΔj ; otherwise the upper right neighbor. Continue while the right endpoint of sis_isi lies to the right of rightp(Δj)\mathit{rightp}(\Delta_j)rightp(Δj) .
[A Randomized Incremental Algorithm] The left endpoint ppp of a new segment sis_isi is already an endpoint of an earlier segment. While searching the search structure D\mathcal{D}D for the first intersected trapezoid Δ0\Delta_0Δ0 , ppp lies on the vertical line of an xxx -node. How is this resolved?
Decide that ppp lies to the right, as if querying with a point p′p'p′ slightly to the right of ppp . Then the search ends in the first trapezoid properly intersected by sis_isi .
[A Randomized Incremental Algorithm] The left endpoint ppp of a new segment sis_isi is already an endpoint of an earlier segment sss . While searching the search structure D\mathcal{D}D for the first intersected trapezoid Δ0\Delta_0Δ0 , ppp lies on the segment sss of a yyy -node. How is this resolved?
Compare slopes: if sis_isi has larger slope than sss , decide that ppp lies above sss , otherwise below. ppp can only lie on sss if sss and sis_isi share the left endpoint ppp .
[A Randomized Incremental Algorithm] The new segment sis_isi lies completely inside one trapezoid Δ\DeltaΔ of T(Si−1)\mathcal{T}(S_{i-1})T(Si−1) . How are T\mathcal{T}T and D\mathcal{D}D updated?
Δ\DeltaΔ is replaced by four trapezoids A,B,C,DA, B, C, DA,B,C,D ; its leaf is replaced by a small tree: xxx -nodes for pip_ipi and qiq_iqi , and a yyy -node for sis_isi . The new records follow in O(1)O(1)O(1) time from sis_isi and Δ\DeltaΔ 's record. If an endpoint of sis_isi equals leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) or rightp(Δ)\mathit{rightp}(\Delta)rightp(Δ) , there are only two or three new trapezoids.
[A Randomized Incremental Algorithm] A new segment sis_isi intersects trapezoids Δ0,…,Δk\Delta_0, \dots, \Delta_kΔ0,…,Δk with k≥1k \ge 1k≥1 . How is the trapezoidal map T\mathcal{T}T updated, and in what time?
Split at the new endpoints of sis_isi , then merge trapezoids along sis_isi : O(k)O(k)O(k) time. Erect vertical extensions through the endpoints of sis_isi not yet present (splitting Δ0\Delta_0Δ0 and Δk\Delta_kΔk into three each), then shorten the extensions that now abut sis_isi .
[A Randomized Incremental Algorithm] A new segment sis_isi intersects trapezoids Δ0,…,Δk\Delta_0, \dots, \Delta_kΔ0,…,Δk with k≥1k \ge 1k≥1 . How are their leaves in the search structure D\mathcal{D}D replaced?
Δ0\Delta_0Δ0 and Δk\Delta_kΔk : an xxx -node plus a yyy -node; Δ1,…,Δk−1\Delta_1, \dots, \Delta_{k-1}Δ1,…,Δk−1 : a single yyy -node for sis_isi . The xxx -node of Δ0\Delta_0Δ0 tests the left endpoint of sis_isi , that of Δk\Delta_kΔk the right endpoint.The xxx -node is needed only if that endpoint lies in the interior of Δ0\Delta_0Δ0 (or Δk\Delta_kΔk ), i.e. is new. Merged trapezoids get leaves with several incoming edges:
[A Randomized Incremental Algorithm] The randomized incremental algorithm for trapezoidal maps processes a fixed set SSS of nnn segments. What does expected running time, size, and query time mean here?
The average over all n!n!n! insertion orders (random permutations), each giving its own run and search structure. The expected query time is for a fixed query point qqq . That is not the expected maximum query time over all qqq .
[A Randomized Incremental Algorithm] SSS is a set of nnn segments in general position. What does the randomized incremental algorithm achieve for the trapezoidal map T(S)\mathcal{T}(S)T(S) and its search structure D\mathcal{D}D ?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) expected time, O(n)\boldsymbol{O(n)}O(n) expected size of D\mathcal{D}D , and O(logn)\boldsymbol{O(\log n)}O(logn) expected query time for any query point qqq .
[A Randomized Incremental Algorithm] What is the worst-case query time in the search structure D\mathcal{D}D built by the randomized incremental algorithm for nnn segments, and why?
3n\boldsymbol{3n}3n : each iteration increases the depth of D\mathcal{D}D by at most 3. This is the best possible bound over all insertion orders.
[A Randomized Incremental Algorithm] Analysis of the expected query time for a fixed point qqq : XiX_iXi is the number of nodes on qqq 's search path created in iteration iii , and PiP_iPi the probability that some such node exists. Why is E[∑iXi]≤∑i3PiE[\sum_i X_i] \le \sum_i 3 P_iE[∑iXi]≤∑i3Pi ?
Linearity of expectation, and Xi≤3X_i \le 3Xi≤3 , so E[Xi]≤3PiE[X_i] \le 3P_iE[Xi]≤3Pi . Linearity of expectation needs no independence of the XiX_iXi .
[A Randomized Incremental Algorithm] When does iteration iii of the randomized incremental algorithm add a node to the search path of a fixed query point qqq ?
Exactly when the trapezoid containing qqq changes: Δq(Si)≠Δq(Si−1)\Delta_q(S_i) \ne \Delta_q(S_{i-1})Δq(Si)=Δq(Si−1) . So Pi=Pr[Δq(Si)≠Δq(Si−1)]P_i = \Pr[\Delta_q(S_i) \ne \Delta_q(S_{i-1})]Pi=Pr[Δq(Si)=Δq(Si−1)] , and a trapezoid created in iteration iii has sis_isi as top or bottom, or an endpoint of sis_isi as leftp or rightp.
[A Randomized Incremental Algorithm] Δq(Si)\Delta_q(S_i)Δq(Si) is the trapezoid containing qqq in T(Si)\mathcal{T}(S_i)T(Si) , where Si={s1,…,si}S_i = \{s_1, \dots, s_i\}Si={s1,…,si} is the set of the first iii segments in a random order.How does backwards analysis show Pr[Δq(Si)≠Δq(Si−1)]≤4/i\Pr[\Delta_q(S_i) \ne \Delta_q(S_{i-1})] \le 4/iPr[Δq(Si)=Δq(Si−1)]≤4/i ?
Removing a random sis_isi from a fixed SiS_iSi destroys Δq(Si)\Delta_q(S_i)Δq(Si) only if sis_isi is one of at most 4 segments, each with probability 1/i1/i1/i . Those segments: top(Δq(Si))\mathit{top}(\Delta_q(S_i))top(Δq(Si)) , bottom(Δq(Si))\mathit{bottom}(\Delta_q(S_i))bottom(Δq(Si)) , and the only segment having leftp\mathit{leftp}leftp , respectively rightp\mathit{rightp}rightp , as endpoint (if there is one).The bound holds for every fixed SiS_iSi , so it holds unconditionally.
[A Randomized Incremental Algorithm] Backwards analysis: in T(Si)\mathcal{T}(S_i)T(Si) , remove a random segment si∈Sis_i \in S_isi∈Si and ask whether the trapezoid Δ\DeltaΔ containing qqq disappears.Many segments of SiS_iSi can share the endpoint leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) . Why is the probability that leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) disappears still at most 1/i1/i1/i ?
leftp(Δ)\mathit{leftp}(\Delta)leftp(Δ) disappears only if sis_isi is the only segment of SiS_iSi with that endpoint.
[A Randomized Incremental Algorithm] For a fixed query point qqq , iteration iii adds at most 3 nodes to qqq 's search path, and does so with probability at most 4/i4/i4/i .What bound on the expected search path length follows?
∑i=1n12i=12Hn=O(logn)\boldsymbol{\sum_{i=1}^{n} \frac{12}{i} = 12 H_n = O(\log n)}∑i=1ni12=12Hn=O(logn) Hn=1+12+⋯+1nH_n = 1 + \frac12 + \dots + \frac1nHn=1+21+⋯+n1 is the nnn -th harmonic number.
[A Randomized Incremental Algorithm] What are the bounds on the harmonic number Hn=1+12+13+⋯+1nH_n = 1 + \frac12 + \frac13 + \dots + \frac1nHn=1+21+31+⋯+n1 for n>1n > 1n>1 ?
lnn<Hn<lnn+1\boldsymbol{\ln n < H_n < \ln n + 1}lnn<Hn<lnn+1 Compare HnH_nHn with ∫1n1x dx=lnn\int_1^n \frac1x \, dx = \ln n∫1nx1dx=lnn .
[A Randomized Incremental Algorithm] In the randomized incremental algorithm for trapezoidal maps, kik_iki is the number of new trapezoids created when inserting sis_isi . How many inner nodes of D\mathcal{D}D does iteration iii create?
ki−1\boldsymbol{k_i - 1}ki−1 So the size of D\mathcal{D}D is O(n)+∑i(ki−1)O(n) + \sum_i (k_i - 1)O(n)+∑i(ki−1) , the O(n)O(n)O(n) counting the leaves (one per trapezoid). With ki=O(i)k_i = O(i)ki=O(i) this gives the worst case O(n2)O(n^2)O(n2) .
[A Randomized Incremental Algorithm] kik_iki = number of trapezoids created when inserting sis_isi = number of trapezoids of T(Si)\mathcal{T}(S_i)T(Si) that disappear when sis_isi is removed. δ(Δ,s)=1\delta(\Delta, s) = 1δ(Δ,s)=1 if Δ\DeltaΔ disappears from T(Si)\mathcal{T}(S_i)T(Si) when sss is removed from SiS_iSi , else 0.Why is E[ki]=O(1)E[k_i] = O(1)E[ki]=O(1) ?
E[ki]=1i∑s∈Si∑Δ∈T(Si)δ(Δ,s)≤4∣T(Si)∣i=O(i)i=O(1)\boldsymbol{E[k_i] = \frac1i \sum_{s \in S_i} \sum_{\Delta \in \mathcal{T}(S_i)} \delta(\Delta, s) \le \frac{4 |\mathcal{T}(S_i)|}{i} = \frac{O(i)}{i} = O(1)}E[ki]=i1∑s∈Si∑Δ∈T(Si)δ(Δ,s)≤i4∣T(Si)∣=iO(i)=O(1) sis_isi is a random element of SiS_iSi , and at most four segments make a given trapezoid disappear. Hence the expected size of D\mathcal{D}D is O(n)O(n)O(n) .
[A Randomized Incremental Algorithm] Why is the expected running time of the randomized incremental trapezoidal map algorithm O(nlogn)O(n \log n)O(nlogn) ?
Inserting sis_isi takes O(ki)O(k_i)O(ki) plus a point location of its left endpoint in T(Si−1)\mathcal{T}(S_{i-1})T(Si−1) : O(1)+∑i(O(logi)+O(E[ki]))=O(nlogn)O(1) + \sum_i \left(O(\log i) + O(E[k_i])\right) = O(n \log n)O(1)+∑i(O(logi)+O(E[ki]))=O(nlogn) . kik_iki is the number of new trapezoids, with E[ki]=O(1)E[k_i] = O(1)E[ki]=O(1) .
[A Randomized Incremental Algorithm] Are there "bad inputs" for the randomized incremental trapezoidal map algorithm, i.e. sets of nnn segments on which its expected running time exceeds O(nlogn)O(n \log n)O(nlogn) ?
No. The expectation is only over the algorithm's own random choices, not over inputs: the bound holds for every input set.
[A Randomized Incremental Algorithm] A planar subdivision S\mathcal{S}S is given as a doubly-connected edge list, and D\mathcal{D}D is the search structure for the trapezoidal map of its edges. How is every leaf (trapezoid Δ\DeltaΔ ) labelled with its face of S\mathcal{S}S ?
Take the face of S\mathcal{S}S incident to top(Δ)\mathit{top}(\Delta)top(Δ) from below; if top(Δ)\mathit{top}(\Delta)top(Δ) is the top edge of RRR , the unbounded face. Each half-edge stores the face to its left, and the face to its right is found in O(1)O(1)O(1) via its twin.
[A Randomized Incremental Algorithm] Point location in a planar subdivision S\mathcal{S}S with nnn edges: what do trapezoidal maps give (preprocessing, storage, query)?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) expected preprocessing, O(n)\boldsymbol{O(n)}O(n) expected storage, O(logn)\boldsymbol{O(\log n)}O(logn) expected query time for any query point. Via the randomized incremental algorithm on the edges of S\mathcal{S}S , without any general position assumption.
[Dealing with Degenerate Cases] Which two simplifying assumptions does the randomized incremental point location algorithm need removed in the general case?
Distinct endpoints have distinct xxx -coordinates; a query point never lies on an xxx -node's vertical line or a yyy -node's segment. The second assumption concerns the nodes on the query point's search path.
[Dealing with Degenerate Cases] Distinct segment endpoints may share an xxx -coordinate. Why can a trapezoidal map algorithm simply rotate the axis-system slightly, and why does the book do this symbolically?
The vertical direction is immaterial, so a small enough rotation separates the xxx -coordinates; but real tiny rotations need much higher numerical precision. A symbolic perturbation, like the composite numbers used in orthogonal range searching.
[Dealing with Degenerate Cases] What is the shear transformation φ\varphiφ used for degenerate cases of trapezoidal maps?
φ(x,y)=(x+εy, y)\boldsymbol{\varphi(x, y) = (x + \varepsilon y, \; y)}φ(x,y)=(x+εy,y) for a small ε>0\varepsilon > 0ε>0 . It maps a vertical line to a line of slope 1/ε1/\varepsilon1/ε , so distinct points on a common vertical line get distinct xxx -coordinates.
[Dealing with Degenerate Cases] The shear φ(x,y)=(x+εy,y)\varphi(x, y) = (x + \varepsilon y, y)φ(x,y)=(x+εy,y) is applied to segments. What must hold for ε>0\varepsilon > 0ε>0 , and must its value be computed?
ε\varepsilonε must be small enough not to reverse the xxx -order of points with distinct xxx -coordinates. Its value is never needed. A point φp=(x+εy,y)\varphi p = (x + \varepsilon y, y)φp=(x+εy,y) is simply stored as (x,y)(x, y)(x,y) .
[Dealing with Degenerate Cases] Which two elementary geometric operations does the randomized incremental trapezoidal map algorithm (and its query) use?
(1) Is qqq left of, right of, or on the vertical line through ppp ? (2) Is qqq above, below, or on segment p1p2p_1p_2p1p2 ? Test (2) is only applied when the vertical line through qqq intersects p1p2p_1p_2p1p2 .All points involved are segment endpoints (or the query point). The algorithm never computes coordinates of vertical extensions.
[Dealing with Degenerate Cases] After the shear φ(x,y)=(x+εy,y)\varphi(x, y) = (x + \varepsilon y, y)φ(x,y)=(x+εy,y) with ε\varepsilonε arbitrarily small, how is "is φq\varphi qφq left or right of the vertical line through φp\varphi pφp ?" decided?
Compare ppp and qqq lexicographically: by xxx , and by yyy if the xxx -coordinates are equal. So φq\varphi qφq lies on the vertical line through φp\varphi pφp only if p=qp = qp=q . This is the only change the algorithm needs.
[Dealing with Degenerate Cases] After the shear φ(x,y)=(x+εy,y)\varphi(x, y) = (x + \varepsilon y, y)φ(x,y)=(x+εy,y) , how is "is φq\varphi qφq above, below or on segment φs\varphi sφs ?" decided (the vertical line through φq\varphi qφq intersects φs\varphi sφs )?
If sss is vertical, qqq lies on sss ; otherwise test the untransformed qqq against the untransformed sss . If sss is vertical, x1=x=x2x_1 = x = x_2x1=x=x2 and y1≤y≤y2y_1 \le y \le y_2y1≤y≤y2 . Otherwise: an affine map preserves whether a point is above, on or below a line.
[Dealing with Degenerate Cases] After the shear transformation, a query in the search structure gets the outcome "on the line" at an xxx -node, or "on" at a yyy -node. What does that mean?
xxx -node: qqq coincides with that node's endpoint. yyy -node: qqq lies on that node's segment. Either one answers the query.
[Dealing with Degenerate Cases] SSS is any set of nnn non-crossing segments (no general position). What does the randomized incremental algorithm achieve for the trapezoidal map T(S)\mathcal{T}(S)T(S) and its search structure?
The same as in general position: O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) expected time, O(n)\boldsymbol{O(n)}O(n) expected size, O(logn)\boldsymbol{O(\log n)}O(logn) expected query time for any qqq . The algorithm runs on the sheared set φS\varphi SφS and compares points lexicographically.
[A Tail Estimate] The search structure for nnn segments has O(logn)O(\log n)O(logn) expected query time for every fixed query point qqq . Why doesn't that bound the expected maximum query time?
Each permutation might be bad for some query point, so the maximum over all qqq could still be large in expectation. A high-probability bound per point, plus a union bound over finitely many representative points, fixes this.
[A Tail Estimate] SSS is a set of nnn non-crossing segments, qqq a query point, λ>0\lambda > 0λ>0 . What is the high-probability bound for qqq 's search path in the structure from the randomized incremental algorithm?
Pr[path has more than 3λln(n+1) nodes]≤1/(n+1)λln1.25−1\Pr[\text{path has more than } 3\lambda \ln(n+1) \text{ nodes}] \le \boldsymbol{1/(n+1)^{\lambda \ln 1.25 - 1}}Pr[path has more than 3λln(n+1) nodes]≤1/(n+1)λln1.25−1
[A Tail Estimate] In the tail estimate for the query path of qqq , the proof defines a DAG G\mathcal{G}G on the subsets of the segment set SSS . What are its nodes and arcs, and what do its paths mean?
Nodes: all subsets of SSS ; arcs S′→S′∪{s}S' \to S' \cup \{s\}S′→S′∪{s} labelled sss ; source-to-sink paths = permutations of SSS . Layer iii holds the subsets of size iii ; each path is a possible run of the algorithm. A node in layer iii has iii incoming and n−in - in−i outgoing arcs. The earlier indicator variables were not independent; this graph yields independent ones.
[A Tail Estimate] DAG G\mathcal{G}G : nodes are the subsets of SSS ; arc S′→S′∪{s}S' \to S' \cup \{s\}S′→S′∪{s} labelled sss ; source-to-sink paths are insertion orders.Which arcs are marked, and how many marked incoming arcs does each node get?
An arc is marked if inserting its segment changes the trapezoid containing qqq . Exactly four per node (in layers 1 to 3, all incoming arcs). Backwards analysis gives at most four; if fewer, extra arcs are marked arbitrarily to make it exactly four.
[A Tail Estimate] DAG G\mathcal{G}G on the subsets of SSS : each node in layer i≥4i \ge 4i≥4 has iii incoming arcs, exactly 4 of them marked. Xi=1X_i = 1Xi=1 if the iii -th arc on a random source-to-sink path is marked.What is Pr[Xi=1]\Pr[X_i = 1]Pr[Xi=1] , and why are the XiX_iXi independent?
Pr[Xi=1]=4/i\boldsymbol{\Pr[X_i = 1] = 4/i}Pr[Xi=1]=4/i for i≥4i \ge 4i≥4 (and 1 for i<4i < 4i<4 ). Each node in layer iii has the same fraction of marked incoming arcs, whichever path led there. With Y=∑iXiY = \sum_i X_iY=∑iXi , qqq 's search path has at most 3Y3Y3Y nodes.
[A Tail Estimate] What does Markov's inequality say?
For a nonnegative random variable ZZZ and α>0\alpha > 0α>0 : Pr[Z≥α]≤E[Z]/α\Pr[Z \ge \alpha] \le E[Z]/\alphaPr[Z≥α]≤E[Z]/α .
[A Tail Estimate] Y=∑i=1nXiY = \sum_{i=1}^n X_iY=∑i=1nXi with independent Xi∈{0,1}X_i \in \{0, 1\}Xi∈{0,1} , Pr[Xi=1]≤4/i\Pr[X_i = 1] \le 4/iPr[Xi=1]≤4/i .How does the proof bound Pr[Y≥λln(n+1)]\Pr[Y \ge \lambda \ln(n+1)]Pr[Y≥λln(n+1)] ?
Markov on etYe^{tY}etY : Pr[Y≥λln(n+1)]≤e−tλln(n+1) E[etY]\Pr[Y \ge \lambda \ln(n+1)] \le e^{-t\lambda \ln(n+1)} \, E[e^{tY}]Pr[Y≥λln(n+1)]≤e−tλln(n+1)E[etY] , and by independence E[etY]=∏iE[etXi]E[e^{tY}] = \prod_i E[e^{tX_i}]E[etY]=∏iE[etXi] . With t=ln1.25t = \ln 1.25t=ln1.25 : E[etXi]≤1+1i=i+1iE[e^{tX_i}] \le 1 + \frac1i = \frac{i+1}{i}E[etXi]≤1+i1=ii+1 , so the product telescopes to n+1n + 1n+1 . The result is n+1(n+1)λt=1(n+1)λt−1\frac{n+1}{(n+1)^{\lambda t}} = \frac{1}{(n+1)^{\l…
[A Tail Estimate] SSS is a set of nnn non-crossing segments, λ>0\lambda > 0λ>0 . What is the bound on the probability that the maximum search path length in the structure from the randomized incremental algorithm exceeds 3λln(n+1)3\lambda \ln(n+1)3λln(n+1) ?
2/(n+1)λln1.25−3\boldsymbol{2/(n+1)^{\lambda \ln 1.25 - 3}}2/(n+1)λln1.25−3 The single-point bound 1/(n+1)λln1.25−11/(n+1)^{\lambda \ln 1.25 - 1}1/(n+1)λln1.25−1 , times 2(n+1)22(n+1)^22(n+1)2 representative query points.
[A Tail Estimate] To bound the maximum search path length over all query points, why does it suffice to consider 2(n+1)22(n+1)^22(n+1)2 query points ( nnn = number of segments)?
Points in one cell of a fixed decomposition into at most 2(n+1)22(n+1)^22(n+1)2 trapezoids follow the same search path in every possible structure. Decomposition: vertical lines through all endpoints, each slab cut by all segments.Every test is left/right of an endpoint's vertical line or above/below a segment. Then use a union bound over one point per trapezoid.
[A Tail Estimate] Max search path length >3λln(n+1)> 3\lambda \ln(n+1)>3λln(n+1) with probability ≤2/(n+1)λln1.25−3\le 2/(n+1)^{\lambda \ln 1.25 - 3}≤2/(n+1)λln1.25−3 .Taking λ=20\lambda = 20λ=20 : with what probability are the query time, the size and the construction time all good?
At least 1/2. Max path >60ln(n+1)> 60 \ln(n+1)>60ln(n+1) with probability ≤2/(n+1)1.4<1/4\le 2/(n+1)^{1.4} < 1/4≤2/(n+1)1.4<1/4 for n>4n > 4n>4 ; size O(n)O(n)O(n) fails with probability ≤1/4\le 1/4≤1/4 (Markov). Good depth and size imply O(nlogn)O(n \log n)O(nlogn) construction.
[A Tail Estimate] Planar subdivision S\mathcal{S}S with nnn edges: what point location bounds hold in the worst case (not just expected)?
A structure with O(n)\boldsymbol{O(n)}O(n) storage and O(logn)\boldsymbol{O(\log n)}O(logn) query time exists.
[A Tail Estimate] How is a point location structure with worst-case O(n)O(n)O(n) size and O(logn)O(\log n)O(logn) query time built from the randomized incremental algorithm?
Run it while tracking size and depth; as soon as size exceeds c1nc_1 nc1n or depth exceeds c2lognc_2 \log nc2logn , restart with a fresh random permutation. Each run succeeds with probability at least 1/41/41/4 , so at most four runs are expected (for large nnn , barely more than one).
[A Tail Estimate] What is the expected preprocessing time for the worst-case O(n)O(n)O(n) size, O(logn)O(\log n)O(logn) query point location structure obtained by restarting the randomized incremental algorithm?
O(nlog2n)\boldsymbol{O(n \log^2 n)}O(nlog2n) Tracking the maximum query path needs test points: 2(n+1)22(n+1)^22(n+1)2 naively, reducible to O(nlogn)O(n \log n)O(nlogn) . The constants of the simple proof are poor (a query visiting 60lnn60 \ln n60lnn nodes), but better ones follow from the same technique.
[Notes and Comments] Which four basically different approaches give planar point location with O(logn)O(\log n)O(logn) query time and O(n)O(n)O(n) storage?
Chain method, triangulation refinement, persistency, randomized incremental. By Edelsbrunner et al.; Kirkpatrick; Sarnak and Tarjan, and Cole; Mulmuley.The chain method uses segment trees and fractional cascading. The book's presentation of the randomized method follows Seidel.
[Notes and Comments] What is known for point location in three-dimensional subdivisions?
O(nlogn)O(n \log n)O(nlogn) storage with O(log2n)O(\log^2 n)O(log2n) query time is possible; no structure with linear storage and O(logn)O(\log n)O(logn) query time is known. Obtained from dynamic planar point location combined with persistence.
[Notes and Comments] For the arrangement of nnn hyperplanes in ddd -dimensional space, what are its complexity and the point location bounds of Chazelle and Friedman?
Complexity Θ(nd)\boldsymbol{\Theta(n^d)}Θ(nd) ; storage O(nd)\boldsymbol{O(n^d)}O(nd) with O(logn)\boldsymbol{O(\log n)}O(logn) query time.