Ch.10: More Geometric Data Structures

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 10.1. Interval Trees 10.2. Priority Search Trees 10.3. Segment Trees 10.4. Notes and Comments

79 flashcards · Mathematics · by lakesare

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

[More Geometric Data Structures] What is a windowing query?
Given a rectangular region (the window), report all objects of a large scene (roads, cities, segments, polygons) that lie in it, or intersect it. e.g. a car navigation system that shows the part of a roadmap around the current position. Checking every feature of the map is too slow, so the map is stored in a data structure.
[More Geometric Data Structures] Besides geographic maps, name two applications of windowing queries.
Flight simulation (select the landscape triangles in sight of the pilot) and printed circuit board design (zoom in on part of the board). In flight simulation the query region is 3-dimensional and is called the viewing volume.
[More Geometric Data Structures] How do windowing queries differ from the range queries of range trees and kd-trees?
The data are line segments, polygons or curves instead of points, and the search space is usually only 2- or 3-dimensional. Range queries often deal with higher-dimensional point sets.
[Interval Trees] Why is windowing on a printed circuit board easier than windowing on a roadmap?
The board's segments have few orientations; typically they are all axis-parallel. Roadmap segments have arbitrary orientations.
[Interval Trees] A segment parallel to the xxx -axis or the yyy -axis is called axis-parallel, or orthogonal.
[Interval Trees] SSS is a set of nnn axis-parallel segments and W=[x:x′]×[y:y′]W = [x : x'] \times [y : y']W=[x:x′]×[y:y′] an axis-parallel query window. Into which two kinds does the windowing solution split the segments that intersect WWW ?
Segments with at least one endpoint inside WWW , and segments with no endpoint inside WWW (they cross the boundary of WWW ). A segment can lie inside WWW , cross the boundary once or twice, or overlap the boundary.
[Interval Trees] A range query with window WWW on the segment endpoints reports a segment twice if both its endpoints lie in WWW . Name a way to avoid this.
When an endpoint is found inside WWW , check whether the other one is too; if so, report the segment only at its leftmost (or bottom) endpoint. Alternatively, mark a segment when it is first reported and skip marked segments.
[Interval Trees] Lemma 10.1 SSS is a set of nnn axis-parallel segments in the plane. The segments with at least one endpoint inside an axis-parallel query window WWW can be reported in … ? With what storage and preprocessing?
O(log⁡n+k)O(\log n + k)O(logn+k) time, with O(nlog⁡n)O(n \log n)O(nlogn) storage and preprocessing ( kkk = number of reported segments). A 2-dimensional range query with WWW on the 2n2n2n segment endpoints, in a range tree with fractional cascading.
[Interval Trees] An axis-parallel segment intersects an axis-parallel window WWW but has no endpoint inside WWW . Why is it enough to query with the left edge and the bottom edge of WWW ?
Such a segment crosses two opposite edges of WWW (or contains a boundary edge), so it meets the left or the bottom edge. A vertical one crosses both horizontal edges, a horizontal one both vertical edges. So the problem becomes: report the horizontal segments crossed by a vertical query segment (and symmetrically, the vertical segments crossed by a horizontal one).
[Interval Trees] When does the vertical line ℓ:x=qx\ell : x = q_xℓ:x=qx intersect the horizontal segment sss from (x,y)(x, y)(x,y) to (x′,y)(x', y)(x′,y) ?
If and only if x≤qx≤x′x \le q_x \le x'x≤qx≤x′ . Only xxx -coordinates matter, so the problem becomes 1-dimensional: report the intervals that contain the query point qxq_xqx .
[Interval Trees] III is a set of nnn closed intervals on the real line and xmidx_{\text{mid}}xmid is the median of their 2n2n2n endpoints. Which three sets does the root of an interval tree split III into?
IleftI_{\text{left}}Ileft (entirely left of xmidx_{\text{mid}}xmid ), ImidI_{\text{mid}}Imid (containing xmidx_{\text{mid}}xmid ), IrightI_{\text{right}}Iright (entirely right of xmidx_{\text{mid}}xmid ). Ileft={[xj:xj′]:xj′<xmid}I_{\text{left}} = \{[x_j : x'_j] : x'_j < x_{\text{mid}}\}Ileft={[xj:xj′]:xj′<xmid} , Imid={[xj:xj′]:xj≤xmid≤xj′}\ I_{\text{mid}} = \{[x_j : x'_j] : x_j \le x_{\text{mid}} \le x'_j\} Imid={[xj:xj′]:xj≤xmid≤xj′} , Iright={[xj:xj′]:xm…
[Interval Trees] In an interval tree, why are the intervals containing xmidx_{\text{mid}}xmid kept at the node itself instead of in both subtrees?
Storing them in both subtrees could happen again at every level, so an interval could be stored many times and storage would blow up.
[Interval Trees] Every interval in ImidI_{\text{mid}}Imid contains xmidx_{\text{mid}}xmid . qx<xmidq_x < x_{\text{mid}}qx<xmid . How are the intervals of ImidI_{\text{mid}}Imid that contain qxq_xqx reported?
Walk along ImidI_{\text{mid}}Imid sorted on increasing left endpoint, reporting, until an interval does not contain qxq_xqx . Every right endpoint lies right of xmid>qxx_{\text{mid}} > q_xxmid>qx , so qx∈[xj:xj′]q_x \in [x_j : x'_j]qx∈[xj:xj′] iff xj≤qxx_j \le q_xxj≤qx . Once that fails, it fails for all later intervals.
[Interval Trees] Every interval in ImidI_{\text{mid}}Imid contains xmidx_{\text{mid}}xmid . qx>xmidq_x > x_{\text{mid}}qx>xmid , or qx=xmidq_x = x_{\text{mid}}qx=xmid . How are the intervals of ImidI_{\text{mid}}Imid that contain qxq_xqx reported?
qx>xmidq_x > x_{\text{mid}}qx>xmid : walk along ImidI_{\text{mid}}Imid sorted on decreasing right endpoint, until an interval misses qxq_xqx . qx=xmidq_x = x_{\text{mid}}qx=xmid : report all of ImidI_{\text{mid}}Imid (either sorted list works).
[Interval Trees] Define the interval tree of a set III of intervals.
Root vvv stores xmidx_{\text{mid}}xmid and the intervals containing it ( ImidI_{\text{mid}}Imid ); the subtrees are interval trees for IleftI_{\text{left}}Ileft and IrightI_{\text{right}}Iright . xmidx_{\text{mid}}xmid = median of the interval endpoints; IleftI_{\text{left}}Ileft , IrightI_{\text{right}}Iright = the intervals entirely left, right of it. ImidI_{\text{mid}}Imid is stored twice, as sorted lists Lleft(v)\mathcal{L}_{\text{left}}(v)Lleft(v) and Lright(v)\mathcal{L}_{\text{r…
[Interval Trees] In an interval tree, how are the lists Lleft(v)\mathcal{L}_{\text{left}}(v)Lleft(v) and Lright(v)\mathcal{L}_{\text{right}}(v)Lright(v) at a node vvv sorted?
Lleft(v)\mathcal{L}_{\text{left}}(v)Lleft(v) on left endpoints (increasing), Lright(v)\mathcal{L}_{\text{right}}(v)Lright(v) on right endpoints (decreasing). Both contain the same intervals: those containing xmid(v)x_{\text{mid}}(v)xmid(v) .
[Interval Trees] Lemma 10.2. An interval tree on a set of nnn intervals uses how much storage, and what is its depth?
O(n)O(n)O(n) storage, depth O(log⁡n)O(\log n)O(logn) . Depth: xmidx_{\text{mid}}xmid is the median of the endpoints, so each subtree gets at most half of them.
[Interval Trees] Why does an interval tree on nnn intervals use only O(n)O(n)O(n) storage?
IleftI_{\text{left}}Ileft , ImidI_{\text{mid}}Imid , IrightI_{\text{right}}Iright are disjoint, so every interval is in exactly one set ImidI_{\text{mid}}Imid , hence appears once in each of two sorted lists. The tree itself has O(n)O(n)O(n) nodes.
[Interval Trees] Lemma 10.3. How fast can an interval tree on nnn intervals be built?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) At a node: median in linear time (or by presorting), and sorting the lists Lleft\mathcal{L}_{\text{left}}Lleft , Lright\mathcal{L}_{\text{right}}Lright in O(nmidlog⁡nmid)O(n_{\text{mid}} \log n_{\text{mid}})O(nmidlognmid) , nmid=∣Imid∣n_{\text{mid}} = |I_{\text{mid}}|nmid=∣Imid∣ . The linear parts sum to O(n)O(n)O(n) per depth level, and the nmidn_{\text{mid}}nmid sum to nnn .
[Interval Trees] What does QueryIntervalTree (v,qx)(v, q_x)(v,qx) do at a non-leaf node vvv of an interval tree?
If qx<xmid(v)q_x < x_{\text{mid}}(v)qx<xmid(v) : walk Lleft(v)\mathcal{L}_{\text{left}}(v)Lleft(v) from the leftmost endpoint and recurse on the left child. Otherwise: walk Lright(v)\mathcal{L}_{\text{right}}(v)Lright(v) from the rightmost endpoint and recurse on the right child. Each walk reports intervals containing qxq_xqx and stops at the first that doesn't. At a leaf nothing happens.
[Interval Trees] Why does a query in an interval tree on nnn intervals take O(log⁡n+k)O(\log n + k)O(logn+k) time ( kkk = number of reported intervals)?
At most one node per depth is visited, and a node vvv costs O(1+kv)O(1 + k_v)O(1+kv) , where kvk_vkv intervals are reported at vvv . Depth O(log⁡n)O(\log n)O(logn) and ∑kv=k\sum k_v = k∑kv=k .
[Interval Trees] Theorem 10.4. An interval tree on a set III of nnn intervals: storage, building time, query time for the intervals containing a query point?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time, O(log⁡n+k)O(\log n + k)O(logn+k) query time ( kkk = number of reported intervals).
[Interval Trees] For a horizontal segment s=[sx:sx′]×sys = [s_x : s'_x] \times s_ys=[sx:sx′]×sy , the interval [sx:sx′][s_x : s'_x][sx:sx′] is the x-interval of sss .
[Interval Trees] Horizontal segments are stored in an interval tree by their xxx -intervals. The query is now a vertical segment q=qx×[qy:qy′]q = q_x \times [q_y : q'_y]q=qx×[qy:qy′] with qx<xmidq_x < x_{\text{mid}}qx<xmid at the root. What must hold for a segment sss of ImidI_{\text{mid}}Imid to be intersected by qqq ?
Its left endpoint must lie in (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] . A left endpoint left of qqq is no longer enough: its yyy -coordinate must also lie in [qy:qy′][q_y : q'_y][qy:qy′] . (Skipping the right subtree is still correct.)
[Interval Trees] How does the interval tree for horizontal segments, queried with a vertical segment q=qx×[qy:qy′]q = q_x \times [q_y : q'_y]q=qx×[qy:qy′] , store each set Imid(v)I_{\text{mid}}(v)Imid(v) ?
As two 2-dimensional range trees: Tleft(v)\mathcal{T}_{\text{left}}(v)Tleft(v) on the left endpoints and Tright(v)\mathcal{T}_{\text{right}}(v)Tright(v) on the right endpoints of the segments in Imid(v)I_{\text{mid}}(v)Imid(v) . They replace the sorted lists Lleft(v)\mathcal{L}_{\text{left}}(v)Lleft(v) , Lright(v)\mathcal{L}_{\text{right}}(v)Lright(v) . Each uses O(nmidlog⁡nmid)O(n_{\text{mid}} \log n_{\text{mid}})O(nmidlognmid) storage and answers a query in O(log⁡nmid+k)O(\log n_{\text…
[Interval Trees] Theorem 10.5 SSS is a set of nnn horizontal segments in the plane. The segments intersecting a vertical query segment can be reported in … ? With what storage and building time?
O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) query time, O(nlog⁡n)O(n \log n)O(nlogn) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time ( kkk = number of reported segments). An interval tree on the xxx -intervals, with range trees on the left and right endpoints of each Imid(v)I_{\text{mid}}(v)Imid(v) .
[Interval Trees] Horizontal segments are stored in an interval tree on their xxx -intervals; at each node vvv , the segments containing xmid(v)x_{\text{mid}}(v)xmid(v) are stored in range trees on their endpoints.Why are storage O(nlog⁡n)O(n \log n)O(nlogn) and query time O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) for a vertical query segment?
Storage: a range tree is a log⁡n\log nlogn factor larger than a sorted list. Query: a range query, O(log⁡n+kv)O(\log n + k_v)O(logn+kv) , at each of the O(log⁡n)O(\log n)O(logn) nodes on the search path.
[Interval Trees] Corollary 10.6 SSS is a set of nnn axis-parallel segments in the plane. The segments intersecting an axis-parallel rectangular query window can be reported in … ? With what storage and building time?
O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) query time, O(nlog⁡n)O(n \log n)O(nlogn) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time ( kkk = number of reported segments). A range tree on the endpoints for segments with an endpoint inside, plus interval trees with range trees for segments crossing the left or bottom edge.
[Priority Search Trees] What special property of the range queries (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] does the priority search tree use?
The range is unbounded on one side. With priority search trees instead of range trees as associated structures, the storage for reporting horizontal segments hit by a vertical query segment drops from O(nlog⁡n)O(n \log n)O(nlogn) to O(n)O(n)O(n) , and no fractional cascading is needed.
[Priority Search Trees] Do priority search trees bring the storage for axis-parallel windowing (segments intersecting an axis-parallel window) down to O(n)O(n)O(n) ?
No, it stays O(nlog⁡n)O(n \log n)O(nlogn) . A range tree is still needed to report the segment endpoints that lie inside the window.
[Priority Search Trees] How can a 1-dimensional range query (−∞:qx](-\infty : q_x](−∞:qx] be answered in O(1+k)O(1 + k)O(1+k) time instead of O(log⁡n+k)O(\log n + k)O(logn+k) ?
Walk along the points sorted by xxx , starting at the leftmost, until a point is not in the range. kkk = number of reported points. A list cannot also select by yyy , so priority search trees use a heap instead.
[Priority Search Trees] What is a heap on the xxx -coordinates of a point set?
The root stores the point with minimum xxx ; the remaining points are split into two subsets of almost equal size, stored recursively in the same way.
[Priority Search Trees] How is a query (−∞:qx](-\infty : q_x](−∞:qx] answered in a heap on xxx -coordinates, and in what time?
At a node, if its point has x≤qxx \le q_xx≤qx , report it and continue in both subtrees; otherwise abort there. Time O(1+k)O(1 + k)O(1+k) . kkk = number of reported points. Black: reported; grey: visited, search aborted.
[Priority Search Trees] Query (−∞:5](-\infty : 5](−∞:5] in this heap: which points are reported, and at which nodes is the search aborted?
Reported: 1, 3, 4. Aborted at 8 and 11. The subtrees below 8 and 11 are never visited.
[Priority Search Trees] What does a heap leave free that a priority search tree fixes?
How the remaining points are split in two: a priority search tree splits them by yyy -coordinate. Every yyy in one half is smaller than every yyy in the other; a heap allows any split into almost equal halves.
[Priority Search Trees] Define the priority search tree of a point set PPP (distinct coordinates).
P=∅P = \emptysetP=∅ : a leaf. Otherwise a root vvv storing p(v)=pmin⁡p(v) = p_{\min}p(v)=pmin (smallest xxx ) and y(v)=ymidy(v) = y_{\text{mid}}y(v)=ymid , the median yyy of the other points; left subtree for PbelowP_{\text{below}}Pbelow , right subtree for PaboveP_{\text{above}}Pabove . Pbelow={p∈P∖{pmin⁡}:py<ymid}P_{\text{below}} = \{p \in P \setminus \{p_{\min}\} : p_y < y_{\text{mid}}\}Pbelow={p∈P∖{pmin}:py<ymid} , Pabove={p∈P∖{pmin⁡}:py>ymid}\ P_{\text{above}} = \{p \in P \setminus…
[Priority Search Trees] In the priority search tree of these points, which point is stored at the root, and which points go to its left subtree?
Root: p5p_5p5 (smallest xxx ). Left subtree: p3,p4,p6p_3, p_4, p_6p3,p4,p6 (the lower half by yyy of the rest). The tree is drawn sideways: the partitioning is on yyy . p3p_3p3 has the smallest xxx among p3,p4,p6p_3, p_4, p_6p3,p4,p6 .
[Priority Search Trees] How fast can a priority search tree on nnn points be built?
O(nlog⁡n)O(n \log n)O(nlogn) recursively; O(n)O(n)O(n) if the points are already sorted on yyy . The linear-time construction works bottom-up, the way heaps are normally built.
[Priority Search Trees] What does ReportInSubtree (v,qx)(v, q_x)(v,qx) do in a priority search tree?
If vvv is not a leaf and (p(v))x≤qx(p(v))_x \le q_x(p(v))x≤qx : report p(v)p(v)p(v) and recurse on both children. Otherwise stop. It reports all points in the subtree of vvv with x≤qxx \le q_xx≤qx : the heap query.
[Priority Search Trees] Lemma 10.7. How long does ReportInSubtree (v,qx)(v, q_x)(v,qx) take to report the points with x≤qxx \le q_xx≤qx in the subtree of vvv of a priority search tree?
O(1+kv)\boldsymbol{O(1 + k_v)}O(1+kv) , where kvk_vkv is the number of reported points.
[Priority Search Trees] ReportInSubtree (v,qx)(v, q_x)(v,qx) : if vvv is not a leaf and (p(v))x≤qx(p(v))_x \le q_x(p(v))x≤qx , report p(v)p(v)p(v) and recurse on both children of vvv .Why does it report every point with x≤qxx \le q_xx≤qx in the subtree of vvv of a priority search tree?
xxx -coordinates decrease along the path from any node μ\muμ up to vvv , so if (p(μ))x≤qx(p(\mu))_x \le q_x(p(μ))x≤qx , all points on that path have x≤qxx \le q_xx≤qx . The search is never aborted above μ\muμ .
[Priority Search Trees] ReportInSubtree (v,qx)(v, q_x)(v,qx) : if vvv is not a leaf and (p(v))x≤qx(p(v))_x \le q_x(p(v))x≤qx , report p(v)p(v)p(v) and recurse on both children of vvv .Why does it take only O(1+kv)O(1 + k_v)O(1+kv) time ( kvk_vkv = number of reported points)?
Each visited node μ≠v\mu \neq vμ=v has a parent whose point was reported; charge μ\muμ to that point. Each reported point is charged at most twice.
[Priority Search Trees] How does QueryPrioSearchTree answer a range (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] in a priority search tree?
Search with qyq_yqy and qy′q'_yqy′ ; test the points on both search paths; call ReportInSubtree on the subtrees lying between the two paths. Below the split node vsplitv_{\text{split}}vsplit : where the qyq_yqy -path goes left, on the right child; where the qy′q'_yqy′ -path goes right, on the left child. ReportInSubtree (v,qx)(v, q_x)(v,qx) reports the points with x≤qxx \le q_xx≤qx in the subtree of vvv . The shaded subtrees contain only points with yyy in [qy:qy′][q_y : q&#x27…
[Priority Search Trees] In a priority search tree query (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] , why are the nodes on the search paths to qyq_yqy and qy′q'_yqy′ tested explicitly, besides the selected subtrees?
The points stored on the search paths themselves can lie in the range, and they are in none of the selected subtrees. e.g. the root stores the point with the smallest xxx .
[Priority Search Trees] Priority search tree query (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] : below vsplitv_{\text{split}}vsplit , where the search path to qyq_yqy goes left at vvv , call ReportInSubtree (rc(v),qx)(rc(v), q_x)(rc(v),qx) .Why does every point ppp reported in that call lie in the range?
px≤qxp_x \le q_xpx≤qx by ReportInSubtree; py≤qy′p_y \le q'_ypy≤qy′ since the subtree lies left of vsplitv_{\text{split}}vsplit and qy′>y(vsplit)q'_y > y(v_{\text{split}})qy′>y(vsplit) ; py≥qyp_y \ge q_ypy≥qy since it lies right of vvv , where the qyq_yqy -path went left.
[Priority Search Trees] In a priority search tree query (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] , why is no point of the range missed?
A point stored left of a node where the qyq_yqy -path goes right has y<qyy < q_yy<qy , and one stored right of a node where the qy′q'_yqy′ -path goes left has y>qy′y > q'_yy>qy′ . So a point in the range is on a search path (tested explicitly) or in a subtree on which ReportInSubtree is called.
[Priority Search Trees] Why does a priority search tree query (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] on nnn points take O(log⁡n+k)O(\log n + k)O(logn+k) time?
The search paths have O(log⁡n)O(\log n)O(logn) nodes, and all ReportInSubtree calls together take O(log⁡n+k)O(\log n + k)O(logn+k) , each costing O(1+kv)O(1 + k_v)O(1+kv) . kkk = number of reported points.
[Priority Search Trees] Theorem 10.9. A priority search tree on nnn points in the plane: storage, building time, query time for a range (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] ?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time, O(log⁡n+k)O(\log n + k)O(logn+k) query time ( kkk = number of reported points).
[Segment Trees] How does the bounding box trick handle windowing on arbitrarily oriented segments, and why is its worst case bad?
Query the axis-parallel bounding boxes, then test each segment whose box meets WWW . Worst case: all boxes intersect WWW , while no segment does. In practice it usually works well.
[Segment Trees] For windowing on arbitrarily oriented segments, which assumption is made on the segment set SSS ?
The segments don't intersect each other (they may touch). For intersecting segments the problem is a lot harder and the time bounds are worse.
[Segment Trees] Segments of arbitrary orientation are stored in an interval tree by xxx -interval. Why doesn't this help to find those hit by a vertical query segment q=qx×[qy:qy′]q = q_x \times [q_y : q'_y]q=qx×[qy:qy′] ?
A right endpoint right of qqq says nothing about whether the segment crosses qqq : that depends on its slope. At a node with xmid>qxx_{\text{mid}} > q_xxmid>qx , all stored segments have their right endpoint right of qqq . A left endpoint in (−∞:qx]×[qy:qy′](-\infty : q_x] \times [q_y : q'_y](−∞:qx]×[qy:qy′] no longer decides it. For horizontal segments, the left endpoint in that range was exactly the condition.
[Segment Trees] What is the locus approach for designing data structures?
Partition the parameter space (all possible queries) into regions where every query has the same answer; then answer a query by locating its region. It only works well when there are few regions. For windowing, the parameter space (qx,qx′,qy,qy′)(q_x, q'_x, q_y, q'_y)(qx,qx′,qy,qy′) is 4-dimensional with up to Θ(n4)\Theta(n^4)Θ(n4) regions.
[Segment Trees] p1<⋯<pmp_1 < \dots < p_mp1<⋯<pm are the distinct endpoints of a set of intervals. What are the elementary intervals?
(−∞:p1),[p1:p1],(p1:p2),[p2:p2],…,(pm−1:pm),[pm:pm],(pm:+∞)(-\infty : p_1), [p_1 : p_1], (p_1 : p_2), [p_2 : p_2], \dots, (p_{m-1} : p_m), [p_m : p_m], (p_m : +\infty)(−∞:p1),[p1:p1],(p1:p2),[p2:p2],…,(pm−1:pm),[pm:pm],(pm:+∞) Open intervals between consecutive endpoints, alternated with the single points. That is 2m+12m + 12m+1 of them.
[Segment Trees] Why are the endpoints pip_ipi themselves elementary intervals, and not just the open pieces between them?
The set of intervals containing a query point pip_ipi can differ from the set containing the points just beside pip_ipi .
[Segment Trees] All intervals of III containing the elementary interval Int⁡(μ)\operatorname{Int}(\mu)Int(μ) are stored at the leaf μ\muμ of a search tree on the elementary intervals. What is good and what is bad?
Good: O(log⁡n+k)O(\log n + k)O(logn+k) query. Bad: storage can be quadratic, since an interval is stored at every leaf it spans. Many pairwise overlapping intervals, each spanning many elementary intervals.
[Segment Trees] The interval sss spans the elementary intervals of μ1,μ2,μ3,μ4,μ5\mu_1, \mu_2, \mu_3, \mu_4, \mu_5μ1,μ2,μ3,μ4,μ5 . Where does a segment tree store sss , and why is that enough?
At vvv and at μ5\mu_5μ5 , instead of at μ1,…,μ5\mu_1, \dots, \mu_5μ1,…,μ5 . A search path ends in μ1,…,μ4\mu_1, \dots, \mu_4μ1,…,μ4 exactly when it passes through vvv . In general an interval is stored at nodes that together cover it, chosen as high as possible.
[Segment Trees] Define the segment tree on a set III of intervals: its skeleton, Int⁡(v)\operatorname{Int}(v)Int(v) , and what each node stores.
A balanced binary tree with the elementary intervals as leaves, in order; each node vvv stores Int⁡(v)\operatorname{Int}(v)Int(v) and its canonical subset I(v)I(v)I(v) . Int⁡(v)\operatorname{Int}(v)Int(v) = the union of the elementary intervals of the leaves below vvv . Arrows point from nodes to their canonical subsets.
[Segment Trees] In a segment tree on intervals III , which intervals form the canonical subset I(v)I(v)I(v) of a node vvv ?
The intervals [x:x′]∈I[x : x'] \in I[x:x′]∈I with Int⁡(v)⊆[x:x′]\operatorname{Int}(v) \subseteq [x : x']Int(v)⊆[x:x′] and Int⁡(parent(v))⊈[x:x′]\operatorname{Int}(\mathit{parent}(v)) \not\subseteq [x : x']Int(parent(v))⊆[x:x′] . Int⁡(v)\operatorname{Int}(v)Int(v) is the union of the elementary intervals of the leaves below vvv . So [x:x′][x : x'][x:x′] covers vvv 's interval but not its parent's.
[Segment Trees] Lemma 10.10. How much storage does a segment tree on nnn intervals use?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) Height O(log⁡n)O(\log n)O(logn) : at most 4n+14n + 14n+1 leaves, since m≤2nm \le 2nm≤2n distinct endpoints give 2m+12m + 12m+1 elementary intervals. And an interval is stored at most twice per depth.
[Segment Trees] In a segment tree, why is an interval [x:x′][x : x'][x:x′] stored at at most two nodes of each depth?
Stored at v1v_1v1 and v3v_3v3 , it contains Int⁡(parent(v2))\operatorname{Int}(\mathit{parent}(v_2))Int(parent(v2)) for any v2v_2v2 between them on that depth, so it is not stored at v2v_2v2 . It spans from the left end of Int⁡(v1)\operatorname{Int}(v_1)Int(v1) to the right end of Int⁡(v3)\operatorname{Int}(v_3)Int(v3) . With height O(log⁡n)O(\log n)O(logn) this gives O(nlog⁡n)O(n \log n)O(nlogn) storage.
[Segment Trees] What does QuerySegmentTree (v,qx)(v, q_x)(v,qx) do, and how long does it take?
Report all intervals in I(v)I(v)I(v) ; if vvv is not a leaf, recurse into the child ccc with qx∈Int⁡(c)q_x \in \operatorname{Int}(c)qx∈Int(c) . Time O(log⁡n+k)O(\log n + k)O(logn+k) . kkk = number of reported intervals. One node per level is visited, at O(1+kv)O(1 + k_v)O(1+kv) each.
[Segment Trees] How is a segment tree on nnn intervals built?
Sort the endpoints, build a balanced binary tree on the elementary intervals, then insert the intervals one by one. Sorting takes O(nlog⁡n)O(n \log n)O(nlogn) ; the tree and every Int⁡(v)\operatorname{Int}(v)Int(v) are computed bottom-up in linear time.
[Segment Trees] What does InsertSegmentTree (v,[x:x′])(v, [x : x'])(v,[x:x′]) do in a segment tree?
If Int⁡(v)⊆[x:x′]\operatorname{Int}(v) \subseteq [x : x']Int(v)⊆[x:x′] , store [x:x′][x : x'][x:x′] at vvv . Otherwise recurse into each child ccc with Int⁡(c)∩[x:x′]≠∅\operatorname{Int}(c) \cap [x : x'] \neq \emptysetInt(c)∩[x:x′]=∅ .
[Segment Trees] Why does inserting one interval [x:x′][x : x'][x:x′] into a segment tree on nnn intervals take O(log⁡n)O(\log n)O(logn) time?
At most 4 nodes per level are visited: at most 2 where it is stored, at most 1 whose interval contains xxx , at most 1 whose interval contains x′x'x′ . A visited node vvv either stores [x:x′][x : x'][x:x′] , or Int⁡(v)\operatorname{Int}(v)Int(v) contains an endpoint of [x:x′][x : x'][x:x′] . Constant time per node, with I(v)I(v)I(v) a linked list.
[Segment Trees] Theorem 10.12. A segment tree on a set III of nnn intervals: storage, building time, query time for the intervals containing a query point?
O(nlog⁡n)O(n \log n)O(nlogn) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time, O(log⁡n+k)O(\log n + k)O(logn+k) query time ( kkk = number of reported intervals).
[Segment Trees] For reporting the intervals containing a query point, interval tree or segment tree?
Interval tree: same O(log⁡n+k)O(\log n + k)O(logn+k) query time, but O(n)O(n)O(n) storage instead of O(nlog⁡n)O(n \log n)O(nlogn) .
[Segment Trees] Why is a segment tree more powerful than an interval tree for more complicated queries (such as windowing on segments)?
The intervals containing qxq_xqx are exactly the union of the canonical subsets on the search path. So the canonical subsets can be stored in associated structures for further querying.In an interval tree, not all intervals stored at the visited nodes contain qxq_xqx ; a walk along the sorted list is still needed.
[Segment Trees] A segment tree is built on the xxx -intervals of a set SSS of disjoint segments. Which segments are in the canonical subset S(v)S(v)S(v) of a node vvv ?
The segments that span the slab Int⁡(v)×(−∞:+∞)\operatorname{Int}(v) \times (-\infty : +\infty)Int(v)×(−∞:+∞) of vvv , but not the slab of the parent of vvv . A segment spans a slab if it completely crosses it.
[Segment Trees] A node vvv of a segment tree on disjoint segments has canonical subset S(v)S(v)S(v) (segments spanning the slab of vvv ). How is S(v)S(v)S(v) stored, and why is that possible?
In a binary search tree T(v)\mathcal{T}(v)T(v) on the vertical order of the segments within the slab. They all span the slab and don't intersect, so they are ordered from bottom to top.
[Segment Trees] A segment sss spans the slab of a node on the search path of qxq_xqx . When does the vertical query segment q=qx×[qy:qy′]q = q_x \times [q_y : q'_y]q=qx×[qy:qy′] intersect sss ?
Iff the lower endpoint of qqq is below sss and the upper endpoint of qqq is above sss . So searching T(v)\mathcal{T}(v)T(v) (vertical order of S(v)S(v)S(v) ) with both endpoints of qqq is a 1-dimensional range query: O(log⁡n+kv)O(\log n + k_v)O(logn+kv) .
[Segment Trees] Segment tree on nnn disjoint segments, with each canonical subset in a search tree on vertical order. Why are the storage O(nlog⁡n)O(n \log n)O(nlogn) and the query time O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) for a vertical query segment?
Storage: each associated tree is linear in ∣S(v)∣|S(v)|∣S(v)∣ . Query: a 1-dimensional range query, O(log⁡n+kv)O(\log n + k_v)O(logn+kv) , in T(v)\mathcal{T}(v)T(v) for each of the O(log⁡n)O(\log n)O(logn) nodes on the search path. kkk = number of reported segments.
[Segment Trees] Segment tree on nnn disjoint segments, with each canonical subset in a search tree on vertical order. What is the straightforward preprocessing time, and how is it improved to O(nlog⁡n)O(n \log n)O(nlogn) ?
O(nlog⁡2n)O(n \log^2 n)O(nlog2n) ; improved by maintaining a (partial) vertical order of the segments while building the segment tree, so each associated structure is built in linear time.
[Segment Trees] Theorem 10.13 SSS is a set of nnn disjoint segments in the plane. The segments intersecting a vertical query segment can be reported in … ? With what storage and building time?
O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) query time, O(nlog⁡n)O(n \log n)O(nlogn) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time ( kkk = number of reported segments). A segment tree on the xxx -intervals, each canonical subset in a search tree on vertical order.
[Segment Trees] Corollary 10.14 SSS is a set of nnn segments in the plane with disjoint interiors. The segments intersecting an axis-parallel rectangular query window can be reported in … ? With what storage and building time?
O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) query time, O(nlog⁡n)O(n \log n)O(nlogn) storage, O(nlog⁡n)O(n \log n)O(nlogn) building time ( kkk = number of reported segments). Disjoint interiors suffice: endpoints may coincide with other endpoints or lie on other segments.
[Notes and Comments] A query asking for all intervals that contain a given point is called a stabbing query.
Interval tree: Edelsbrunner and McCreight. Priority search tree: McCreight. Segment tree: Bentley.
[Notes and Comments] How can a priority search tree answer stabbing queries (intervals containing a point qxq_xqx )?
Map each interval [a:b][a : b][a:b] to the point (a,b)(a, b)(a,b) and query with (−∞:qx]×[qx:+∞)(-\infty : q_x] \times [q_x : +\infty)(−∞:qx]×[qx:+∞) . a≤qx≤ba \le q_x \le ba≤qx≤b exactly when (a,b)(a, b)(a,b) lies in that range.
[Notes and Comments] How does a segment tree answer stabbing counting queries (the number of intervals containing qxq_xqx ), and with what bounds?
Store at each node the number of intervals in its canonical subset; add up the numbers on the search path. O(n)O(n)O(n) storage, O(log⁡n)O(\log n)O(logn) query.
[Notes and Comments] When is a searching problem decomposable?
For every partition S=A∪BS = A \cup BS=A∪B , the answer on SSS can be obtained in constant time from the answers on AAA and BBB . e.g. stabbing queries (report both answers) and stabbing counting (add). Static structures for decomposable problems can be made dynamic by general techniques.
[Notes and Comments] What is an R-tree, and what are its storage and worst-case query time?
A 2-dimensional extension of the B-tree, for storage on disk: linear storage, but linear worst-case query time. The most widely used geometric structure in GIS, and fast in practice. Any R-tree on nnn points in ddd dimensions can be forced to visit Ω((n/B)1−1/d+k/B)\Omega((n/B)^{1-1/d} + k/B)Ω((n/B)1−1/d+k/B) blocks ( BBB = block size); the PR-tree attains this for axis-parallel boxes.