Ch.16: Simplex Range Searching
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 16.1. Partition Trees 16.2. Multi-Level Partition Trees 16.3. Cutting Trees 16.4. Notes and Comments
70 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Simplex Range Searching] A GIS map layer plots one point per 5,000 inhabitants. You want the number of people affected by a new airport. Which geometric query is this, and why don't the range trees and kd-trees (orthogonal range searching) help?
Count the points inside a query region that is not a rectangle. The affected area (where the plane noise exceeds some level) depends on the dominating wind direction, so it is not axis-parallel. Data structures for rectangular queries don't apply.
[Simplex Range Searching] In range searching, what does “count the points in a query range” mean?
Report the number of points, not enumerate them. Enumerating them is called reporting.
[Partition Trees] You want to count the points of a set SSS inside a query region that is a simple polygon. How do you reduce this to a simpler query range?
Triangulate the polygon and query with each triangle, then add up. Points on a common boundary of two triangles need a bit of care so they are not counted twice. A non-polygonal region can be approximated by a polygon first.
[Partition Trees] What is the triangular range searching problem?
Preprocess a set SSS of nnn points in the plane so that the points of SSS inside a query triangle ttt can be counted. The warm-up is the degenerate case where the query triangle becomes a half-plane.
[Partition Trees] One-dimensional half-line counting: nnn points on the real line, count the points on a given side of a query point. Which structure and query time?
A balanced binary search tree storing at each node the number of points in its subtree: O(logn)O(\log n)O(logn) query.
[Partition Trees] In a balanced binary search tree on points of the real line, why does a half-line query only recurse into one child of each visited node?
The region of the other child is completely inside or completely outside the half-line. Each node's key splits its region of the line into two pieces. If a child's piece is inside, take that child's stored count; if outside, ignore it. Grey: the query half-line. The black node's region lies inside it, so only the right subtree is searched.
[Partition Trees] Why can't the binary-tree approach for half-lines be copied to the plane by splitting the plane into two regions?
No partition of the plane into two regions has, for every query half-plane, a region fully inside or fully outside it. So one partitions into more regions, such that every query half-plane needs recursion into only a few of them.
[Partition Trees] What is a simplicial partition Ψ(S)\Psi(S)Ψ(S) of a set SSS of nnn points in the plane?
A collection {(S1,t1),…,(Sr,tr)}\{(S_1, t_1), \dots, (S_r, t_r)\}{(S1,t1),…,(Sr,tr)} where the SiS_iSi are disjoint subsets with union SSS , and tit_iti is a triangle containing SiS_iSi . The SiS_iSi are the classes, and rrr (the number of triangles) is the size of Ψ(S)\Psi(S)Ψ(S) .
[Partition Trees] In a simplicial partition {(S1,t1),…,(Sr,tr)}\{(S_1, t_1), \dots, (S_r, t_r)\}{(S1,t1),…,(Sr,tr)} of a point set SSS , must the triangles tit_iti be disjoint? Can a point be in two classes?
Triangles may overlap; but every point belongs to exactly one class. A point can lie in several triangles while being a member of only one SiS_iSi .
[Partition Trees] When does a line ℓ\ellℓ cross a triangle ttt ? And a (relatively open) segment, used in simplicial partitions when SSS is not in general position?
Triangle: ℓ\ellℓ intersects the interior of ttt . Segment: ℓ\ellℓ intersects its relative interior but does not contain it.
[Partition Trees] For a simplicial partition Ψ(S)\Psi(S)Ψ(S) , what is the crossing number of a line ℓ\ellℓ , and the crossing number of Ψ(S)\Psi(S)Ψ(S) itself?
Of ℓ\ellℓ : the number of triangles of Ψ(S)\Psi(S)Ψ(S) crossed by ℓ\ellℓ . Of Ψ(S)\Psi(S)Ψ(S) : the maximum crossing number over all lines.
[Partition Trees] A simplicial partition of size 5 (shades of the points mark the classes). What is the crossing number of ℓ\ellℓ ? Of the partition?
ℓ\ellℓ : 2. The partition: 4. Some lines cross four of the triangles, but no line crosses all five.
[Partition Trees] When is a simplicial partition {(S1,t1),…,(Sr,tr)}\{(S_1, t_1), \dots, (S_r, t_r)\}{(S1,t1),…,(Sr,tr)} of nnn points fine?
∣Si∣≤2n/r\boldsymbol{|S_i| \le 2n/r}∣Si∣≤2n/r for every 1≤i≤r\boldsymbol{1 \le i \le r}1≤i≤r No class has more than twice the average number of points n/rn/rn/r .
[Partition Trees] Answering a half-plane query hhh with a simplicial partition {(Si,ti)}\{(S_i, t_i)\}{(Si,ti)} : on which classes must you recurse, and what governs the query time?
Only on the classes whose triangle tit_iti is crossed by the bounding line of hhh , so the crossing number governs the query time. If the bounding line misses tit_iti , then SiS_iSi lies completely inside hhh or is completely disjoint from it.
[Partition Trees] Theorem 16.1 For any set SSS of nnn points in the plane and any rrr with 1≤r≤n1 \le r \le n1≤r≤n , there is a fine simplicial partition of size rrr and crossing number … ? It can be built in which time?
Crossing number O(r)O(\sqrt{r})O(r) , built in O(n1+ε)O(n^{1+\varepsilon})O(n1+ε) time for any ε>0\varepsilon > 0ε>0 . The exponent can be made as close to 1 as you like (but a bound such as O(nlogn)O(n \log n)O(nlogn) is not claimed). The proof is due to Matoušek and not given in the book.
[Partition Trees] What does a partition tree on a set SSS of points look like?
One point: a leaf storing it. Otherwise: a root whose rrr children correspond to the triangles of a fine simplicial partition of SSS of size rrr ; each child ν\nuν is the root of a partition tree on its class. rrr is a sufficiently large constant, and the children are unordered. The dotted triangles: the partition built recursively for the class of the middle child.
[Partition Trees] In a partition tree, what are t(ν)t(\nu)t(ν) and the canonical subset S(ν)S(\nu)S(ν) of a child ν\nuν , and what is stored at ν\nuν for half-plane range counting?
t(ν)t(\nu)t(ν) is its triangle, S(ν)S(\nu)S(ν) its class; ν\nuν stores t(ν)t(\nu)t(ν) and the cardinality ∣S(ν)∣|S(\nu)|∣S(ν)∣ . Other applications store other information about S(ν)S(\nu)S(ν) . For a leaf, the canonical subset is the single point stored there.
[Partition Trees] A half-plane query hhh on a partition tree returns a set Υ\UpsilonΥ of selected nodes. What property must Υ\UpsilonΥ have?
S∩h=⋃ν∈ΥS(ν)\boldsymbol{S \cap h = \bigcup_{\nu \in \Upsilon} S(\nu)}S∩h=⋃ν∈ΥS(ν) , a disjoint union of canonical subsets. The count is then the sum of the stored cardinalities ∣S(ν)∣|S(\nu)|∣S(ν)∣ .
[Partition Trees] For a half-plane query hhh on a partition tree, which nodes ν\nuν exactly are the selected ones?
Those with t(ν)⊂ht(\nu) \subset ht(ν)⊂h (for a leaf: its point lies in hhh ) and no ancestor μ\muμ with t(μ)⊂ht(\mu) \subset ht(μ)⊂h . t(ν)t(\nu)t(ν) is the triangle of node ν\nuν .
[Partition Trees] SelectInHalfplane (h,T)(h, \mathcal{T})(h,T) selects the nodes of a partition tree T\mathcal{T}T whose canonical subsets make up the points in the half-plane hhh . What does it do at the root?
Leaf: select it if its point is in hhh . Otherwise, for each child ν\nuν : if t(ν)⊂ht(\nu) \subset ht(ν)⊂h , select ν\nuν ; else if t(ν)∩h≠∅t(\nu) \cap h \ne \emptysett(ν)∩h=∅ , recurse into ν\nuν 's subtree. t(ν5)t(\nu_5)t(ν5) is disjoint from hhh and ignored; ν3,ν4,ν6\nu_3, \nu_4, \nu_6ν3,ν4,ν6 are crossed by the boundary and visited recursively.
[Partition Trees] For half-plane range counting with a partition tree, how is the set Υ\UpsilonΥ of selected nodes handled in practice?
Not stored: keep a counter and add ∣S(ν)∣|S(\nu)|∣S(ν)∣ whenever a node ν\nuν is selected.
[Partition Trees] Lemma 16.2. How much storage does a partition tree on nnn points in the plane use?
O(n)\boldsymbol{O(n)}O(n)
[Partition Trees] A partition tree on nnn points: each internal node has rrr children (constant rrr ) for the classes of a fine simplicial partition ( ∣S(ν)∣≤2n/r|S(\nu)| \le 2n/r∣S(ν)∣≤2n/r ).Why does it use O(n)O(n)O(n) storage?
Its number of nodes satisfies M(n)≤1+∑νM(nν)M(n) \le 1 + \sum_\nu M(n_\nu)M(n)≤1+∑νM(nν) with ∑νnν=n\sum_\nu n_\nu = n∑νnν=n and nν≤2n/rn_\nu \le 2n/rnν≤2n/r , which solves to O(n)O(n)O(n) for constant r>2r > 2r>2 ; each node needs O(r)=O(1)O(r) = O(1)O(r)=O(1) . nν=∣S(ν)∣n_\nu = |S(\nu)|nν=∣S(ν)∣ ; ∑νnν=n\sum_\nu n_\nu = n∑νnν=n because the classes are disjoint.
[Partition Trees] A partition tree with branching degree rrr (fine simplicial partitions with crossing number at most crc\sqrt{r}cr ) has query time Q(n)≤r+cr Q(2n/r)Q(n) \le r + c\sqrt{r}\, Q(2n/r)Q(n)≤r+crQ(2n/r) .Why must rrr be chosen large to get a query time near O(n)O(\sqrt{n})O(n) ?
The recurrence gives nlog(cr)/log(r/2)n^{\log(c\sqrt{r}) / \log(r/2)}nlog(cr)/log(r/2) , whose exponent tends to 12\frac1221 only as rrr grows; for small rrr the constant ccc pushes it up. logc+12logrlogr−log2→12\frac{\log c + \frac12 \log r}{\log r - \log 2} \to \frac12logr−log2logc+21logr→21 as r→∞r \to \inftyr→∞ .
[Partition Trees] Lemma 16.3 For a set SSS of nnn points in the plane and any ε>0\varepsilon > 0ε>0 , a partition tree for SSS can select, for a query half-plane hhh , how many nodes whose canonical subsets disjointly make up S∩hS \cap hS∩h , in which time?
O(n1/2+ε)\boldsymbol{O(n^{1/2+\varepsilon})}O(n1/2+ε) nodes in O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) time, so half-plane range counting takes O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) .
[Partition Trees] Query time of a partition tree with branching degree rrr : Q(n)≤r+cr Q(2n/r)Q(n) \le r + c\sqrt{r}\, Q(2n/r)Q(n)≤r+crQ(2n/r) , where crc\sqrt{r}cr bounds the crossing number.Which rrr does the proof of the O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) query bound choose, and why does it work?
r=⌈2(c2)1/ε⌉\boldsymbol{r = \lceil 2(c\sqrt{2})^{1/\varepsilon} \rceil}r=⌈2(c2)1/ε⌉ Then (r/2)ε≥c2(r/2)^\varepsilon \ge c\sqrt{2}(r/2)ε≥c2 , so cr (2/r)1/2+ε=c2 (2/r)ε≤1c\sqrt{r}\,(2/r)^{1/2+\varepsilon} = c\sqrt{2}\,(2/r)^{\varepsilon} \le 1cr(2/r)1/2+ε=c2(2/r)ε≤1 : the recursive part does not exceed n1/2+εn^{1/2+\varepsilon}n1/2+ε .
[Partition Trees] A partition tree answers half-plane counting in about O(n)O(\sqrt{n})O(n) , while most structures so far had polylogarithmic query time. Is logarithmic query time impossible for half-planes?
No, but it costs (roughly) quadratic storage: cutting trees. n\sqrt{n}n -type query time is the price of linear storage for a truly 2-dimensional query problem.
[Partition Trees] For data structures based on canonical subsets (range trees, segment trees, partition trees): what determines the query time, and what the storage?
Query: roughly linear in the number of canonical subsets needed to express a query answer. Storage: the number of precomputed canonical subsets (for segment trees: the sum of their sizes). Trade-off: few canonical subsets per query needs many precomputed subsets, and the reverse.
[Partition Trees] For half-plane range searching: how many canonical subsets does a partition tree precompute, how many are needed in general to express one half-plane query, and how many for logarithmic query time?
O(n)O(n)O(n) precomputed; Ω(n)\Omega(\sqrt{n})Ω(n) needed per query in general; roughly quadratically many for logarithmic query time.
[Partition Trees] How must the partition tree and its query algorithm change to handle query triangles instead of half-planes?
Not at all: same structure and algorithm, the query half-plane replaced by the triangle (in fact any query range γ\gammaγ ). Children with t(ν)t(\nu)t(ν) inside γ\gammaγ are selected, outside are ignored, and only those partially inside are visited recursively.
[Partition Trees] A partition tree with crossing number at most crc\sqrt{r}cr in its simplicial partitions of size rrr .How many triangles of such a partition can the boundary of a query triangle γ\gammaγ cross, and why?
At most 3cr3c\sqrt{r}3cr A triangle crossed by the boundary of γ\gammaγ is crossed by one of the three lines through the edges of γ\gammaγ . So the query recurrence only changes ccc to 3c3c3c ; choose rrr larger and the bound stays O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) .
[Partition Trees] Theorem 16.4. A partition tree on nnn points in the plane, for any ε>0\varepsilon > 0ε>0 : storage, triangle counting query time, reporting time, construction time?
O(n)O(n)O(n) storage, O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) counting, O(k)O(k)O(k) additional for reporting the kkk points, O(n1+ε)O(n^{1+\varepsilon})O(n1+ε) construction.
[Partition Trees] A fine simplicial partition of size rrr with crossing number O(r)O(\sqrt{r})O(r) can be built in O(n1+ε′)O(n^{1+\varepsilon'})O(n1+ε′) time, for any ε′>0\varepsilon' > 0ε′>0 .Why can a partition tree on nnn points be built in O(n1+ε)O(n^{1+\varepsilon})O(n1+ε) time?
T(n)=O(n1+ε/2)+∑νT(nν)T(n) = O(n^{1+\varepsilon/2}) + \sum_\nu T(n_\nu)T(n)=O(n1+ε/2)+∑νT(nν) with ∑νnν=n\sum_\nu n_\nu = n∑νnν=n , which solves to O(n1+ε)O(n^{1+\varepsilon})O(n1+ε) . Take ε′=ε/2\varepsilon' = \varepsilon/2ε′=ε/2 . Each level of the tree costs O(n1+ε/2)O(n^{1+\varepsilon/2})O(n1+ε/2) in total, and the O(logn)O(\log n)O(logn) levels fit in the extra nε/2n^{\varepsilon/2}nε/2 .
[Partition Trees] Why can a partition tree report the kkk points in a query triangle in O(k)O(k)O(k) time on top of the counting query?
Traverse the subtrees of the selected nodes: their leaves are the kkk points, and a tree whose internal nodes have degree ≥2\ge 2≥2 has fewer internal nodes than leaves.
[Multi-Level Partition Trees] What is a multi-level data structure?
A structure whose nodes store, for their canonical subset, another data structure (the associated structure) instead of just a number. Range trees for rectangular queries and the windowing structures (interval and segment trees with associated trees) are earlier examples.
[Multi-Level Partition Trees] When does a line ℓ\ellℓ intersect a segment sss with endpoints pleft(s)p_{\mathrm{left}}(s)pleft(s) and pright(s)p_{\mathrm{right}}(s)pright(s) ?
If and only if the endpoints lie on distinct sides of ℓ\ellℓ , or sss has an endpoint on ℓ\ellℓ .
[Multi-Level Partition Trees] Counting the segments of a set SSS that intersect a query line ℓ\ellℓ : which subproblem do multi-level partition trees solve, and how is the rest handled?
Count the segments with pright(s)p_{\mathrm{right}}(s)pright(s) above ℓ\ellℓ and pleft(s)p_{\mathrm{left}}(s)pleft(s) below ℓ\ellℓ ; the opposite case and the endpoints on ℓ\ellℓ are counted with similar structures. For a vertical ℓ\ellℓ , its left side counts as below and its right side as above.
[Multi-Level Partition Trees] Segment intersection counting with a two-level partition tree on nnn segments SSS : what do the two levels store?
First level: a partition tree T\mathcal{T}T on the right endpoints Pright(S)P_{\mathrm{right}}(S)Pright(S) . At each node ν\nuν : a partition tree Tνassoc\mathcal{T}_\nu^{\mathrm{assoc}}Tνassoc on the left endpoints of the segments S(ν)S(\nu)S(ν) whose right endpoints form ν\nuν 's canonical subset. Tνassoc\mathcal{T}_\nu^{\mathrm{assoc}}Tνassoc is the associated structure of ν\nuν , for half-plane range counting.
[Multi-Level Partition Trees] Two-level partition tree: first level on the right endpoints of the segments; each node ν\nuν has an associated partition tree Tνassoc\mathcal{T}_\nu^{\mathrm{assoc}}Tνassoc on the left endpoints of its segments. ℓ+\ell^+ℓ+ and ℓ−\ell^-ℓ− are the half-planes above and below the query line ℓ\ellℓ .How does SelectIntSegments (ℓ,T)(\ell, \mathcal{T})(ℓ,T) select the segments with right endpoint above ℓ\ellℓ and left endpoint below ℓ\ellℓ ?
For each child ν\nuν : if t(ν)⊂ℓ+t(\nu) \subset \ell^+t(ν)⊂ℓ+ , select in Tνassoc\mathcal{T}_\nu^{\mathrm{assoc}}Tνassoc with the half-plane ℓ−\ell^-ℓ− ; else if ℓ\ellℓ intersects t(ν)t(\nu)t(ν) , recurse into ν\nuν 's subtree. At a leaf: select it if its segment intersects ℓ\ellℓ . The count is the sum of the selected canonical subsets' cardinalities.
[Multi-Level Partition Trees] A two-level partition tree (right endpoints, then left endpoints) selects the segments with right endpoint above and left endpoint below a query line ℓ\ellℓ . How do you get those with the left endpoint above and the right endpoint below?
Same tree: exchange ℓ+\ell^+ℓ+ and ℓ−\ell^-ℓ− in the query algorithm.
[Multi-Level Partition Trees] Lemma 16.5. Storage of a two-level partition tree for segment intersection selection on nnn segments?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) M(n)=∑ν[O(nν)+M(nν)]M(n) = \sum_\nu [O(n_\nu) + M(n_\nu)]M(n)=∑ν[O(nν)+M(nν)] with ∑νnν=n\sum_\nu n_\nu = n∑νnν=n , nν≤2n/rn_\nu \le 2n/rnν≤2n/r : each of the O(logn)O(\log n)O(logn) levels stores linear-size associated trees of total size O(n)O(n)O(n) .
[Multi-Level Partition Trees] Lemma 16.6. Query time of a two-level partition tree for counting the segments (among nnn ) intersected by a query line, for any ε>0\varepsilon > 0ε>0 ?
O(n1/2+ε)\boldsymbol{O(n^{1/2+\varepsilon})}O(n1/2+ε) , the same as a one-level partition tree, with O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) selected nodes. Q(n)=O(rn1/2+ε)+∑i=1crQ(2n/r)Q(n) = O(r n^{1/2+\varepsilon}) + \sum_{i=1}^{c\sqrt{r}} Q(2n/r)Q(n)=O(rn1/2+ε)+∑i=1crQ(2n/r) : at most rrr associated queries of O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) each at the root, plus recursion into at most crc\sqrt{r}cr children.
[Multi-Level Partition Trees] Adding a second level to a partition tree: what happens to storage and query time?
Storage grows by a logarithmic factor; the query time stays the same asymptotically. O(n)→O(nlogn)O(n) \to O(n \log n)O(n)→O(nlogn) storage; O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) query either way.
[Cutting Trees] Why can't partition trees (with simplicial partitions) be made faster than O(n)O(\sqrt{n})O(n) query time?
Simplicial partitions with crossing number less than O(r)O(\sqrt{r})O(r) don't exist, and a faster query would need them.
[Cutting Trees] Dualize half-plane range counting “count the points of SSS above a query line”. Which problem do you get?
Given a set LLL of nnn lines, count the lines below a query point qqq . The dotted segment points down from qqq to the lines below it.
[Cutting Trees] Given nnn lines LLL , how can you count the lines below a query point qqq in O(logn)O(\log n)O(logn) time, and with how much storage?
Build the arrangement A(L)\mathcal{A}(L)A(L) with point location, storing at each face the number of lines below it: O(n2)O(n^2)O(n2) storage. The number of lines below qqq depends only on the face of A(L)\mathcal{A}(L)A(L) containing qqq .
[Cutting Trees] Why doesn't “precompute the answer for every possible query” (as the arrangement does for half-planes) work for triangular range counting?
There are far too many combinatorially different query triangles. Instead, the lines below a query point are expressed by a few canonical subsets, recursively, and a multi-level structure handles triangles.
[Cutting Trees] ttt is a triangle and ℓi\ell_iℓi a line that does not intersect ttt . Why is this useful for counting the lines below a query point q∈tq \in tq∈t ?
ℓi\ell_iℓi lies below every point of ttt or above every point of ttt , so only the lines intersecting ttt remain undecided for qqq . So: store at each triangle the number of lines below it, and recurse on the lines intersecting the triangle that contains qqq .
[Cutting Trees] LLL is a set of nnn lines in the plane and 1≤r≤n1 \le r \le n1≤r≤n . What is a (1/r)(1/r)(1/r) -cutting Ξ(L)\Xi(L)Ξ(L) for LLL ?
A set of possibly unbounded triangles with disjoint interiors covering the plane, none crossed by more than n/rn/rn/r lines of LLL . A line crosses a triangle if it intersects the triangle's interior. The size of the cutting is its number of triangles. A (1/2)(1/2)(1/2) -cutting of size ten (thick) for six lines (thin).
[Cutting Trees] How do the triangles of a (1/r)(1/r)(1/r) -cutting differ from those of a simplicial partition?
Cutting triangles have disjoint interiors and cover the plane; simplicial partition triangles may overlap. Also a cutting is defined for lines (bounding how many cross each triangle), a simplicial partition for points (bounding how many triangles a line crosses).
[Cutting Trees] Theorem 16.7 For any set LLL of nnn lines in the plane and any 1≤r≤n1 \le r \le n1≤r≤n , a (1/r)(1/r)(1/r) -cutting of which size exists, and in which time can it be built (with the crossing lines of each triangle)?
Size O(r2)O(r^2)O(r2) , built in O(nr)O(nr)O(nr) time.
[Cutting Trees] What does a cutting tree on a set LLL of lines look like?
One line: a leaf storing it. Otherwise: a root whose children correspond to the triangles of a (1/r)(1/r)(1/r) -cutting of LLL ; each child ν\nuν is the root of a cutting tree on the lines crossing t(ν)t(\nu)t(ν) . rrr is a sufficiently large constant; ν\nuν stores t(ν)t(\nu)t(ν) and, for counting lines below a point, ∣L−(ν)∣|L^-(\nu)|∣L−(ν)∣ .
[Cutting Trees] In a cutting tree, for a child ν\nuν with triangle t(ν)t(\nu)t(ν) : what are the lower canonical subset L−(ν)L^-(\nu)L−(ν) , the upper canonical subset L+(ν)L^+(\nu)L+(ν) , and the crossing subset?
L−(ν)L^-(\nu)L−(ν) : lines below t(ν)t(\nu)t(ν) . L+(ν)L^+(\nu)L+(ν) : lines above t(ν)t(\nu)t(ν) . Crossing subset: lines crossing t(ν)t(\nu)t(ν) .
[Cutting Trees] Cutting tree: each child ν\nuν of a node has a triangle t(ν)t(\nu)t(ν) (the triangles of a cutting, disjoint interiors), its lower canonical subset L−(ν)L^-(\nu)L−(ν) (lines below t(ν)t(\nu)t(ν) ), and a subtree Tν\mathcal{T}_\nuTν on the lines crossing t(ν)t(\nu)t(ν) .How does SelectBelowPoint (q,T)(q, \mathcal{T})(q,T) select the lines below a query point qqq ?
Find the child νq\nu_qνq with q∈t(νq)q \in t(\nu_q)q∈t(νq) ; select νq\nu_qνq (its set L−(νq)L^-(\nu_q)L−(νq) ) and recurse into Tνq\mathcal{T}_{\nu_q}Tνq . At a leaf: select it if its line is below qqq . Exactly one child per level is visited.
[Cutting Trees] Lemma 16.8. A cutting tree on nnn lines: query time to select (or count) the lines below a query point, number of canonical subsets, and storage?
O(logn)O(\log n)O(logn) time, O(logn)O(\log n)O(logn) canonical subsets, O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) storage for any ε>0\varepsilon > 0ε>0 .
[Cutting Trees] A cutting tree with constant rrr : each node has O(r2)O(r^2)O(r2) children (a (1/r)(1/r)(1/r) -cutting), each with at most n/rn/rn/r crossing lines.Why is the query time for the lines below a point O(logn)O(\log n)O(logn) ?
Q(n)=O(r2)+Q(n/r)Q(n) = O(r^2) + Q(n/r)Q(n)=O(r2)+Q(n/r) : one child per level, and the number of lines shrinks by a factor rrr .
[Cutting Trees] A cutting tree uses (1/r)(1/r)(1/r) -cuttings of size at most cr2cr^2cr2 , each triangle crossed by at most n/rn/rn/r lines; storage M(n)=O(r2)+∑νM(nν)M(n) = O(r^2) + \sum_\nu M(n_\nu)M(n)=O(r2)+∑νM(nν) .Which rrr makes M(n)=O(n2+ε)M(n) = O(n^{2+\varepsilon})M(n)=O(n2+ε) , and why?
r=⌈(2c)1/ε⌉\boldsymbol{r = \lceil (2c)^{1/\varepsilon} \rceil}r=⌈(2c)1/ε⌉ Then cr2⋅(n/r)2+ε=c r−ε n2+ε≤12n2+εcr^2 \cdot (n/r)^{2+\varepsilon} = c\, r^{-\varepsilon}\, n^{2+\varepsilon} \le \frac12 n^{2+\varepsilon}cr2⋅(n/r)2+ε=cr−εn2+ε≤21n2+ε : the children's storage is at most half the bound.
[Cutting Trees] Using a cutting tree in the dual, half-plane range counting on nnn points: query time and storage?
O(logn)O(\log n)O(logn) query, O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) storage.
[Cutting Trees] What is the dual of triangular range counting on a point set SSS ?
Given lines LLL and three query points, each labelled “above” or “below”, count the lines of LLL on the specified side of all three points. A triangle is the intersection of three half-planes, so ppp lies in it iff ppp lies in each half-plane, i.e. the dual line p∗p^*p∗ is on the right side of each dual point.
[Cutting Trees] A two-level cutting tree selects the lines of LLL below two query points q1q_1q1 and q2q_2q2 . What does it store?
A cutting tree T\mathcal{T}T on LLL , and at each node ν\nuν a second-level cutting tree Tνassoc\mathcal{T}_\nu^{\mathrm{assoc}}Tνassoc on its lower canonical subset L−(ν)L^-(\nu)L−(ν) . The first level selects the lines below q1q_1q1 in canonical subsets; the associated structures select from those the lines below q2q_2q2 .
[Cutting Trees] Two-level cutting tree: a cutting tree on LLL ; each node ν\nuν stores a cutting tree Tνassoc\mathcal{T}_\nu^{\mathrm{assoc}}Tνassoc on its lower canonical subset (lines below t(ν)t(\nu)t(ν) ).How does SelectBelowPair (q1,q2,T)(q_1, q_2, \mathcal{T})(q1,q2,T) work?
Find the child ν\nuν with q1∈t(ν)q_1 \in t(\nu)q1∈t(ν) ; run SelectBelowPoint (q2,Tνassoc)(q_2, \mathcal{T}_\nu^{\mathrm{assoc}})(q2,Tνassoc) , and recurse with SelectBelowPair (q1,q2,Tν)(q_1, q_2, \mathcal{T}_\nu)(q1,q2,Tν) . Tν\mathcal{T}_\nuTν is the subtree on the lines crossing t(ν)t(\nu)t(ν) . At a leaf: select it if its line is below both q1q_1q1 and q2q_2q2 .
[Cutting Trees] Adding an extra level to a cutting tree: what happens to query time and storage? (Compare partition trees.)
Query time grows by a logarithmic factor; storage stays the same. Exactly the other way around for partition trees: storage ×logn\times \log n×logn , query time unchanged.
[Cutting Trees] Lemma 16.9. A two-level cutting tree on nnn lines, selecting the lines below two query points: query time, number of canonical subsets, storage?
O(log2n)O(\log^2 n)O(log2n) time, O(log2n)O(\log^2 n)O(log2n) canonical subsets, O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) storage for any ε>0\varepsilon > 0ε>0 . Q(n)=O(r2)+O(logn)+Q(n/r)Q(n) = O(r^2) + O(\log n) + Q(n/r)Q(n)=O(r2)+O(logn)+Q(n/r) : a one-level query O(logn)O(\log n)O(logn) at each of O(logn)O(\log n)O(logn) levels. M(n)=∑ν[O(nν2+ε)+M(nν)]M(n) = \sum_\nu [O(n_\nu^{2+\varepsilon}) + M(n_\nu)]M(n)=∑ν[O(nν2+ε)+M(nν)] solves to O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) for large enough c…
[Cutting Trees] Theorem 16.10. A (three-level) cutting tree on nnn points in the plane, for any ε>0\varepsilon > 0ε>0 : storage, triangle counting query, reporting, construction time?
O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) storage, O(log3n)O(\log^3 n)O(log3n) counting, O(k)O(k)O(k) additional for reporting kkk points, O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) construction.
[Cutting Trees] Triangular range counting on nnn points: compare partition trees and cutting trees.
Partition tree: O(n)O(n)O(n) storage, O(n1/2+ε)O(n^{1/2+\varepsilon})O(n1/2+ε) query. Cutting tree: O(n2+ε)O(n^{2+\varepsilon})O(n2+ε) storage, O(log3n)O(\log^3 n)O(log3n) query.
[Notes and Comments] Who gave the first data structure for triangular range searching in the plane with (roughly) linear storage, and what was its query time?
Willard, with O(n0.774)O(n^{0.774})O(n0.774) query time. Same idea as partition trees, but his partition had a worse crossing number. The best solution is due to Matoušek.
[Notes and Comments] Simplex range searching in Rd\mathbb{R}^dRd with linear storage: what crossing number do simplicial partitions achieve, and what query time follows?
Crossing number O(r1−1/d)O(r^{1-1/d})O(r1−1/d) , query time O(n1−1/d+ε)O(n^{1-1/d+\varepsilon})O(n1−1/d+ε) (Matoušek). Chazelle's lower bound: linear storage forces Ω(n1−1/d/logn)\Omega(n^{1-1/d}/\log n)Ω(n1−1/d/logn) query time.
[Notes and Comments] Chazelle's lower bound: a structure for simplex range searching on nnn points in Rd\mathbb{R}^dRd with O(m)O(m)O(m) storage has which query time?
Ω(n/(m1/dlogn))\boldsymbol{\Omega(n / (m^{1/d} \log n))}Ω(n/(m1/dlogn)) In the plane a slightly sharper bound holds: Ω(n/m)\Omega(n/\sqrt{m})Ω(n/m) .
[Notes and Comments] Simplex range searching in Rd\mathbb{R}^dRd with cutting trees (Chazelle's cuttings, size O(rd)O(r^d)O(rd) ): query time and storage?
O(logdn)O(\log^d n)O(logdn) query, O(nd+ε)O(n^{d+\varepsilon})O(nd+ε) storage. Combining partition and cutting trees: for n≤m≤ndn \le m \le n^dn≤m≤nd , storage O(m1+ε)O(m^{1+\varepsilon})O(m1+ε) gives query time O(n1+ε/m1/d)O(n^{1+\varepsilon}/m^{1/d})O(n1+ε/m1/d) .
[Notes and Comments] Half-plane range reporting in the plane (not counting): which bounds are possible?
O(logn+k)O(\log n + k)O(logn+k) query with O(n)O(n)O(n) storage, kkk the number of reported points. Half-space queries are a special case of simplex queries that allows better results.