Ch.5: Orthogonal Range Searching

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 5.1. 1-Dimensional Range Searching 5.2. Kd-Trees 5.3. Range Trees 5.4. Higher-Dimensional Range Trees 5.5. General Sets of Points 5.6. Fractional Cascading 5.7. Notes and Comments

83 flashcards · Mathematics · by lakesare

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

[Orthogonal Range Searching] A personnel database stores each employee's date of birth and monthly salary. How does the query "all employees born between 1950 and 1955 who earn between 3,000 and 4,000 dollars a month" become a geometric problem?
Each employee is a point (date of birth, salary) in the plane; the query asks for all points in an axis-parallel rectangle. The date of birth is the integer 10,000⋅year+100⋅month+day10{,}000 \cdot \text{year} + 100 \cdot \text{month} + \text{day}10,000⋅year+100⋅month+day , so the rectangle is [19,500,000:19,559,999]×[3,000:4,000][19{,}500{,}000 : 19{,}559{,}999] \times [3{,}000 : 4{,}000][19,500,000:19,559,999]×[3,000:4,000] .
[Orthogonal Range Searching] A database stores dates of birth as 10,000⋅year+100⋅month+day10{,}000 \cdot \text{year} + 100 \cdot \text{month} + \text{day}10,000⋅year+100⋅month+day . Which interval of this coordinate means "born between 1950 and 1955"?
[19,500,000:19,559,999]\boldsymbol{[19{,}500{,}000 : 19{,}559{,}999]}[19,500,000:19,559,999] The encoding is an integer whose order is the chronological order, so a time span becomes an interval.
[Orthogonal Range Searching] A database query restricts ddd fields of the records to given intervals. What does it become geometrically?
Report all points inside a ddd -dimensional axis-parallel box, where each record is a point in ddd -dimensional space. Adding "between two and four children" turns the rectangle into the box [19,500,000:19,559,999]×[3,000:4,000]×[2:4][19{,}500{,}000 : 19{,}559{,}999] \times [3{,}000 : 4{,}000] \times [2 : 4][19,500,000:19,559,999]×[3,000:4,000]×[2:4] .
[Orthogonal Range Searching] A query for all points inside an axis-parallel box is called a rectangular range query, or an orthogonal range query.
[1-Dimensional Range Searching] What is the 1-dimensional range searching problem?
Given a set PPP of nnn real numbers, report the points of PPP inside a query interval [x:x′][x : x'][x:x′] .
[1-Dimensional Range Searching] Which data structure answers 1-dimensional range queries on a set PPP of nnn reals, and what do its leaves and internal nodes store?
A balanced binary search tree T\mathcal{T}T : the leaves store the points of PPP , the internal nodes store splitting values xνx_\nuxν . The left subtree of ν\nuν holds the points ≤xν\le x_\nu≤xν , the right subtree the points >xν> x_\nu>xν .
[1-Dimensional Range Searching] A sorted array also answers 1-dimensional range queries. Why use a balanced binary search tree instead?
The array doesn't generalize to higher dimensions, and doesn't allow efficient updates.
[1-Dimensional Range Searching] In a balanced binary search tree T\mathcal{T}T on a set PPP of reals, search with xxx and with x′x'x′ , ending at the leaves μ\muμ and μ′\mu'μ′ . Which points lie in [x:x′][x : x'][x:x′] ?
The points stored at the leaves between μ\muμ and μ′\mu'μ′ , plus possibly the points at μ\muμ and μ′\mu'μ′ themselves. Query [18:77][18 : 77][18:77] : report the dark leaves and μ=19\mu = 19μ=19 ; the leaf μ′=80\mu' = 80μ′=80 is checked and not reported.
[1-Dimensional Range Searching] In a 1-dimensional range query [x:x′][x : x'][x:x′] on a binary search tree, what is the node νsplit\nu_{\text{split}}νsplit ?
The node where the search paths to xxx and to x′x'x′ split, or the leaf where both paths end.
[1-Dimensional Range Searching] How does FINDSPLITNODE (T,x,x′)(\mathcal{T}, x, x')(T,x,x′) find νsplit\nu_{\text{split}}νsplit in a binary search tree T\mathcal{T}T (node ν\nuν with splitting value xνx_\nuxν )?
From the root, go left while x′≤xνx' \le x_\nux′≤xν and right while x>xνx > x_\nux>xν ; stop at the first node where neither holds (or at a leaf). At that node x≤xν<x′x \le x_\nu < x'x≤xν<x′ : the search for xxx goes left and the search for x′x'x′ goes right.
[1-Dimensional Range Searching] 1-dimensional range query [x:x′][x : x'][x:x′] in a binary search tree, after finding the node νsplit\nu_{\text{split}}νsplit where the search paths to xxx and x′x'x′ split: which subtrees are reported?
The subtrees hanging between the two paths: right subtrees where the path to xxx goes left, left subtrees where the path to x′x'x′ goes right. Finally the two leaves where the paths end are checked individually. The selected subtrees lie between the two search paths and hang off them.
[1-Dimensional Range Searching] REPORTSUBTREE (ν)(\nu)(ν) reports all points at the leaves below a node ν\nuν . Why does it take time linear in the number of reported points?
Any binary tree has fewer internal nodes than leaves, so traversing the subtree costs O(number of leaves)O(\text{number of leaves})O(number of leaves) .
[1-Dimensional Range Searching] Lemma 5.1 Algorithm 1DRANGEQUERY (search to νsplit\nu_{\text{split}}νsplit , then report the subtrees between the two search paths and check the two end leaves) reports … ?
Exactly the points that lie in the query range [x:x′][x : x'][x:x′] .
[1-Dimensional Range Searching] 1DRANGEQUERY with [x:x′][x : x'][x:x′] : from the split node νsplit\nu_{\text{split}}νsplit , it follows the path to xxx and reports the right subtree rc(ν)rc(\nu)rc(ν) of each node ν\nuν where the path goes left (symmetrically for x′x'x′ ).Why does a point ppp reported in REPORTSUBTREE (rc(ν))(rc(\nu))(rc(ν)) on the path to xxx lie in [x:x′][x : x'][x:x′] ?
x<px < px<p , since the path of xxx goes left at ν\nuν and ppp is right of ν\nuν ; and p<x′p < x'p<x′ , since ppp is left of νsplit\nu_{\text{split}}νsplit where the path of x′x'x′ goes right. So x<p≤xνsplit<x′x < p \le x_{\nu_{\text{split}}} < x'x<p≤xνsplit<x′ .
[1-Dimensional Range Searching] 1DRANGEQUERY with [x:x′][x : x'][x:x′] : from the split node νsplit\nu_{\text{split}}νsplit , it follows the path to xxx and reports the right subtree of each node where the path goes left (symmetrically for x′x'x′ ), and checks the leaves where the paths end.How does the proof show that every point p∈[x:x′]p \in [x : x']p∈[x:x′] is reported?
Take the lowest visited ancestor ν\nuν of the leaf μ\muμ of ppp and show ν=μ\nu = \muν=μ . Otherwise ν\nuν is on a search path, say of xxx , with μ\muμ in its left subtree. The path of xxx goes right at ν\nuν (else the left child would be visited), so p<xp < xp<x : a contradiction.
[1-Dimensional Range Searching] What are the storage and construction time of a balanced binary search tree on nnn reals?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) construction.
[1-Dimensional Range Searching] 1-dimensional range query: why is the worst-case query time Θ(n)\Theta(n)Θ(n) a poor way to measure the binary search tree?
Checking every point against the range also takes Θ(n)\Theta(n)Θ(n) , and when all nnn points are in the range no method can do better. So the query time is analysed in terms of both nnn and the number kkk of reported points.
[1-Dimensional Range Searching] An algorithm whose running time depends not only on the input size nnn but also on the size kkk of the output is called output-sensitive.
[1-Dimensional Range Searching] Why does a 1-dimensional range query in a balanced binary search tree on nnn points take O(log⁡n+k)O(\log n + k)O(logn+k) time, with kkk the number of reported points?
The REPORTSUBTREE calls take O(k)O(k)O(k) in total; every other visited node lies on one of the two search paths, of length O(log⁡n)O(\log n)O(logn) .
[1-Dimensional Range Searching] Theorem 5.2 A set PPP of nnn points in 1-dimensional space can be stored in a balanced binary search tree with what storage, construction time and range query time?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) construction, O(k+log⁡n)O(k + \log n)O(k+logn) query time, where kkk is the number of reported points.
[Kd-Trees] Kd-trees and range trees are first described under which assumption on the point set PPP in the plane, and why is it no real restriction?
No two points of PPP have the same xxx -coordinate, and no two the same yyy -coordinate. A trick with composite numbers (lexicographic pairs of coordinates) removes the restriction.
[Kd-Trees] When does a point p=(px,py)p = (p_x, p_y)p=(px,py) lie in the query rectangle [x:x′]×[y:y′][x : x'] \times [y : y'][x:x′]×[y:y′] ?
If and only if px∈[x:x′]p_x \in [x : x']px∈[x:x′] and py∈[y:y′]p_y \in [y : y']py∈[y:y′] . So a 2-dimensional range query is composed of two 1-dimensional sub-queries.
[Kd-Trees] How is a kd-tree on a set PPP of points in the plane built, level by level?
Split PPP by a line through the median, alternating: vertical lines at even depth, horizontal lines at odd depth. The node stores the line; the points left of or on it (below or on it) go to the left subtree, the rest to the right subtree. A leaf stores a single point. The root splits with ℓ1\ell_1ℓ1 , its children with ℓ2\ell_2ℓ2 and ℓ3\ell_3ℓ3 , and so on.
[Kd-Trees] Where does the name "kd-tree" come from?
Originally it meant kkk -dimensional tree. The planar tree was a 2d-tree. Now the original meaning is lost, and it is called a 2-dimensional kd-tree.
[Kd-Trees] What are the steps of BUILDKDTREE (P,depth)(P, \textit{depth})(P,depth) for a set PPP of points in the plane?
Split PPP by the median line (vertical at even depth, horizontal at odd), recurse on both halves with depth+1\textit{depth} + 1depth+1 , return a node storing the line. A single point gives a leaf. The first call has depth=0\textit{depth} = 0depth=0 .
[Kd-Trees] BUILDKDTREE splits a set of nnn points at a median, putting the point on the splitting line into the left (lower) subset. How must the median be defined, and why?
As the ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ -th smallest number, so that the median of two values is the smaller one. This ensures termination: with the larger one, both of two points would go to the left subset, and the recursion would not shrink.
[Kd-Trees] How does BUILDKDTREE find the median of each subset in linear time without a linear-time median algorithm?
Presort the points on xxx and on yyy once, and pass both sorted lists down. The median is read off the right list, and the sorted lists for the two recursive calls are built from the given ones in linear time.
[Kd-Trees] Construction time T(n)T(n)T(n) of a kd-tree on nnn points (with presorting): which recurrence, and what does it give?
T(n)=O(n)+2T(⌈n/2⌉)\boldsymbol{T(n) = O(n) + 2T(\lceil n/2 \rceil)}T(n)=O(n)+2T(⌈n/2⌉) , so T(n)=O(nlog⁡n)\boldsymbol{T(n) = O(n \log n)}T(n)=O(nlogn) . With T(1)=O(1)T(1) = O(1)T(1)=O(1) . This also subsumes the O(nlog⁡n)O(n \log n)O(nlogn) presorting.
[Kd-Trees] Lemma 5.3 A kd-tree for a set of nnn points uses how much storage and can be constructed in what time?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) construction time. Storage: it is a binary tree with nnn leaves (one per point), and each node uses O(1)O(1)O(1) .
[Kd-Trees] In a kd-tree, what is region(ν)region(\nu)region(ν) of a node ν\nuν ?
The rectangle (possibly unbounded) of the plane bounded by the splitting lines stored at the ancestors of ν\nuν . The region of the root is the whole plane. The black points are exactly those stored in the subtree of ν\nuν .
[Kd-Trees] In a kd-tree, which points are stored in the subtree rooted at a node ν\nuν ?
Exactly the points that lie in region(ν)region(\nu)region(ν) . So a query only needs to search the subtree of ν\nuν if the query range intersects region(ν)region(\nu)region(ν) .
[Kd-Trees] How does SEARCHKDTREE (ν,R)(\nu, R)(ν,R) handle each child ccc of an internal node ν\nuν of a kd-tree, for a query range RRR ?
If region(c)⊆Rregion(c) \subseteq Rregion(c)⊆R : report its whole subtree (REPORTSUBTREE). Else if region(c)region(c)region(c) intersects RRR : recurse on ccc . Else skip ccc . At a leaf, the stored point is reported if it lies in RRR . Grey nodes are visited. The subtree at the starred node, whose region lies inside the range, is reported whole; the leaves p6,p11p_6, p_{11}p6,p11 are tested and reported, p3,p12,p13p_3, p_{12}, p_{13}p3,p12,p13 are tested and not reported.
[Kd-Trees] SEARCHKDTREE needs region(ν)region(\nu)region(ν) at each node ν\nuν of a kd-tree. Must the regions be stored?
No: they can be maintained during the recursion from the splitting lines. For ν\nuν at even depth with splitting line ℓ(ν)\ell(\nu)ℓ(ν) : region(lc(ν))=region(ν)∩ℓ(ν)leftregion(lc(\nu)) = region(\nu) \cap \ell(\nu)^{\text{left}}region(lc(ν))=region(ν)∩ℓ(ν)left , where ℓ(ν)left\ell(\nu)^{\text{left}}ℓ(ν)left is the closed half-plane left of ℓ(ν)\ell(\nu)ℓ(ν) .
[Kd-Trees] Does SEARCHKDTREE (visit the nodes whose region intersects the query range RRR , report subtrees whose region lies inside RRR ) need RRR to be a rectangle?
No: it works for any query range. Only the O(n+k)O(\sqrt{n} + k)O(n+k) time bound uses that RRR is an axis-parallel rectangle.
[Kd-Trees] Lemma 5.4 A query with an axis-parallel rectangle in a kd-tree storing nnn points can be performed in what time?
O(n+k)\boldsymbol{O(\sqrt{n} + k)}O(n+k) , where kkk is the number of reported points.
[Kd-Trees] A kd-tree query reports the subtrees whose region lies inside the query rectangle in O(k)O(k)O(k) total time ( kkk = number of reported points).How does the proof of the O(n+k)O(\sqrt{n} + k)O(n+k) bound count the remaining visited nodes?
Their regions meet the boundary of the rectangle, so count the regions a vertical (or horizontal) line can intersect. Each of the four edges of the rectangle lies on such a line.
[Kd-Trees] Let Q(n)Q(n)Q(n) be the number of regions of a kd-tree on nnn points that a vertical line ℓ\ellℓ intersects. Why is Q(n)=1+Q(n/2)Q(n) = 1 + Q(n/2)Q(n)=1+Q(n/2) wrong?
The children of the root split horizontally: if ℓ\ellℓ intersects the region of a child of the root, it intersects the regions of both grandchildren below it. The recursive situation is not the same as the original one.
[Kd-Trees] Q(n)Q(n)Q(n) = number of regions intersected by a vertical line ℓ\ellℓ in a kd-tree on nnn points whose root has a vertical splitting line.Which recurrence does Q(n)Q(n)Q(n) satisfy, and why?
Q(n)=2+2Q(n/4)\boldsymbol{Q(n) = 2 + 2Q(n/4)}Q(n)=2+2Q(n/4) , so Q(n)=O(n)\boldsymbol{Q(n) = O(\sqrt{n})}Q(n)=O(n) . Of the four nodes at depth two (each with about n/4n/4n/4 points and a vertical split again), ℓ\ellℓ meets the regions of two; the 2 counts the root and one of its children. Grey: the regions ℓ\ellℓ intersects.
[Kd-Trees] The kd-tree query bound O(n+k)O(\sqrt{n} + k)O(n+k) counts the regions crossed by the whole lines through the query edges. When is it pessimistic? Give an example.
For small query ranges, whose short edges intersect far fewer regions. e.g. the range [x:x]×[y:y][x : x] \times [y : y][x:x]×[y:y] asks whether the point (x,y)(x, y)(x,y) is in the set, and takes O(log⁡n)O(\log n)O(logn) time.
[Kd-Trees] Theorem 5.5 A kd-tree for a set PPP of nnn points in the plane: storage, construction time, rectangular range query time?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) construction, O(n+k)O(\sqrt{n} + k)O(n+k) query, where kkk is the number of reported points.
[Kd-Trees] How is a kd-tree built for points in ddd -dimensional space?
Cycle through the coordinates: at depth iii , split at the median of coordinate (i mod d)+1(i \bmod d) + 1(imodd)+1 . The splitting hyperplane is perpendicular to that axis: first coordinate at the root, …, last at depth d−1d - 1d−1 , then the first again.The recursion stops at a single point, stored in a leaf.
[Kd-Trees] A ddd -dimensional kd-tree on nnn points ( ddd constant): storage, construction time, query time?
O(n)O(n)O(n) storage, O(nlog⁡n)O(n \log n)O(nlogn) construction, O(n1−1/d+k)O(n^{1 - 1/d} + k)O(n1−1/d+k) query. kkk = number of reported points; for d=2d = 2d=2 the query time is O(n+k)O(\sqrt{n} + k)O(n+k) .
[Range Trees] Range trees versus kd-trees for nnn points in the plane: what does the range tree gain, and at what price?
Query time O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) instead of O(n+k)O(\sqrt{n} + k)O(n+k) , for storage O(nlog⁡n)O(n \log n)O(nlogn) instead of O(n)O(n)O(n) . kkk = number of reported points.
[Range Trees] In a binary search tree, what is the canonical subset P(ν)P(\nu)P(ν) of a node ν\nuν ?
The set of points stored in the leaves of the subtree rooted at ν\nuν . The canonical subset of the root is the whole set PPP ; that of a leaf is its single point.
[Range Trees] In a balanced binary search tree on the xxx -coordinates of nnn points, how can the points with xxx -coordinate in [x:x′][x : x'][x:x′] be expressed?
As the disjoint union of O(log⁡n)O(\log n)O(logn) canonical subsets, those of the roots of the subtrees selected by the 1-dimensional query. (Plus possibly the points at the two leaves μ,μ′\mu, \mu'μ,μ′ where the searches end.)
[Range Trees] What is a 2-dimensional range tree on a set PPP of nnn points in the plane?
A balanced search tree T\mathcal{T}T on xxx ; each node ν\nuν points to a balanced search tree Tassoc(ν)\mathcal{T}_{\text{assoc}}(\nu)Tassoc(ν) on yyy of its canonical subset P(ν)P(\nu)P(ν) . Tassoc(ν)\mathcal{T}_{\text{assoc}}(\nu)Tassoc(ν) is the associated structure of ν\nuν .
[Range Trees] Data structures whose nodes have pointers to associated structures are called multi-level data structures; the main tree is the first-level tree, and the associated structures are the second-level trees.
[Range Trees] What are the steps of BUILD2DRANGETREE (P)(P)(P) for a set PPP of points in the plane?
Build Tassoc\mathcal{T}_{\text{assoc}}Tassoc on the yyy -coordinates; split PPP at the median xxx -coordinate xmidx_{\text{mid}}xmid , recurse on both halves, return a node storing xmidx_{\text{mid}}xmid and Tassoc\mathcal{T}_{\text{assoc}}Tassoc . If PPP is a single point, return a leaf with Tassoc\mathcal{T}_{\text{assoc}}Tassoc instead. PleftP_{\text{left}}Pleft gets the points with xxx -coordinate ≤xmid\le x_{\text{mid}}≤xmid .
[Range Trees] Why do the leaves of the associated structures Tassoc(ν)\mathcal{T}_{\text{assoc}}(\nu)Tassoc(ν) of a range tree store whole points, not just yyy -coordinates?
A query on an associated structure must report the points themselves.
[Range Trees] Lemma 5.6 A 2-dimensional range tree on a set of nnn points in the plane requires how much storage?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn)
[Range Trees] Why does a 2-dimensional range tree on nnn points use O(nlog⁡n)O(n \log n)O(nlogn) storage?
At each depth of the main tree, a point lies in exactly one associated structure, so each of the O(log⁡n)O(\log n)O(logn) depths costs O(n)O(n)O(n) . A point is stored only in the associated structures of the nodes on its root-to-leaf path. A point ppp appears once per level of the main tree.
[Range Trees] How is a 2-dimensional range tree on nnn points built in O(nlog⁡n)O(n \log n)O(nlogn) time, rather than O(nlog⁡2n)O(n \log^2 n)O(nlog2n) ?
Keep the points in two lists, sorted on xxx and on yyy ; then each associated tree is built bottom-up in linear time from the presorted yyy -list. Building a search tree on an unsorted set costs O(nlog⁡n)O(n \log n)O(nlogn) . With presorting, the time per node is linear in its canonical subset, so the total matches the storage O(nlog⁡n)O(n \log n)O(nlogn) .
[Range Trees] How does 2DRANGEQUERY with [x:x′]×[y:y′][x : x'] \times [y : y'][x:x′]×[y:y′] differ from the 1-dimensional range query on the main tree?
Instead of reporting a selected subtree with root ν\nuν , it calls 1DRANGEQUERY (Tassoc(ν),[y:y′])(\mathcal{T}_{\text{assoc}}(\nu), [y : y'])(Tassoc(ν),[y:y′]) . The two leaves where the search paths for xxx and x′x'x′ end are checked against the whole rectangle.
[Range Trees] Lemma 5.7 A query with an axis-parallel rectangle in a range tree storing nnn points takes what time?
O(log⁡2n+k)\boldsymbol{O(\log^2 n + k)}O(log2n+k) , where kkk is the number of reported points.
[Range Trees] Why does a rectangular query on a 2-dimensional range tree with nnn points take O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) time?
Each of the O(log⁡n)O(\log n)O(logn) visited main-tree nodes ν\nuν costs O(log⁡n+kν)O(\log n + k_\nu)O(logn+kν) , where kνk_\nukν is the number of points reported at ν\nuν . ∑νkν=k\sum_\nu k_\nu = k∑νkν=k , and ∑νO(log⁡n)=O(log⁡2n)\sum_\nu O(\log n) = O(\log^2 n)∑νO(logn)=O(log2n) .
[Range Trees] Theorem 5.8 A range tree for a set PPP of nnn points in the plane: storage, construction time, rectangular query time?
O(nlog⁡n)O(n \log n)O(nlogn) storage, O(nlog⁡n)O(n \log n)O(nlogn) construction, O(log⁡2n+k)O(\log^2 n + k)O(log2n+k) query, where kkk is the number of reported points. Fractional cascading improves the query time to O(log⁡n+k)O(\log n + k)O(logn+k) .
[Higher-Dimensional Range Trees] How is a range tree on a set PPP of points in ddd -dimensional space built?
A balanced search tree on the first coordinate; each node ν\nuν has a (d−1)(d-1)(d−1) -dimensional range tree on P(ν)P(\nu)P(ν) as associated structure. The points of the canonical subset P(ν)P(\nu)P(ν) are restricted to their last d−1d - 1d−1 coordinates.The recursion stops at 1-dimensional range trees (balanced binary search trees on the last coordinate).
[Higher-Dimensional Range Trees] How is a range query answered in a ddd -dimensional range tree on nnn points?
Select O(log⁡n)O(\log n)O(logn) canonical subsets by the first coordinate, then query their associated structures recursively. The second level yields O(log⁡2n)O(\log^2 n)O(log2n) canonical subsets in total, and so on down to the 1-dimensional trees, which report the points.
[Higher-Dimensional Range Trees] Theorem 5.9 A range tree for a set PPP of nnn points in ddd -dimensional space ( d≥2d \ge 2d≥2 ): storage, construction time, rectangular query time?
O(nlog⁡d−1n)O(n \log^{d-1} n)O(nlogd−1n) storage and construction, O(log⁡dn+k)O(\log^d n + k)O(logdn+k) query, where kkk is the number of reported points.
[Higher-Dimensional Range Trees] Construction time Td(n)T_d(n)Td(n) of a ddd -dimensional range tree on nnn points: which recurrence, and why?
Td(n)=O(nlog⁡n)+O(log⁡n)⋅Td−1(n)\boldsymbol{T_d(n) = O(n \log n) + O(\log n) \cdot T_{d-1}(n)}Td(n)=O(nlogn)+O(logn)⋅Td−1(n) , with T2(n)=O(nlog⁡n)T_2(n) = O(n \log n)T2(n)=O(nlogn) , so Td(n)=O(nlog⁡d−1n)T_d(n) = O(n \log^{d-1} n)Td(n)=O(nlogd−1n) . O(nlog⁡n)O(n \log n)O(nlogn) builds the first-level tree. At each of the O(log⁡n)O(\log n)O(logn) depths every point lies in exactly one associated structure, so building them costs O(Td−1(n))O(T_{d-1}(n))O(Td−1(n)) , since building time is at…
[Higher-Dimensional Range Trees] Query time Qd(n)Q_d(n)Qd(n) of a ddd -dimensional range tree on nnn points, without the time to report: which recurrence, and what does it give?
Qd(n)=O(log⁡n)+O(log⁡n)⋅Qd−1(n)\boldsymbol{Q_d(n) = O(\log n) + O(\log n) \cdot Q_{d-1}(n)}Qd(n)=O(logn)+O(logn)⋅Qd−1(n) , with Q2(n)=O(log⁡2n)Q_2(n) = O(\log^2 n)Q2(n)=O(log2n) , so Qd(n)=O(log⁡dn)Q_d(n) = O(\log^d n)Qd(n)=O(logdn) . Search the first-level tree, then query O(log⁡n)O(\log n)O(logn) (d−1)(d-1)(d−1) -dimensional range trees. Reporting adds O(k)O(k)O(k) .
[General Sets of Points] Kd-trees and range trees assume distinct xxx - and distinct yyy -coordinates. What observation makes the assumption easy to remove?
The structures never use that the coordinates are reals, only that they come from a totally ordered universe (to compare and to compute medians).
[General Sets of Points] What is the composite number (a∣b)(a|b)(a∣b) of two reals a,ba, ba,b , and how are composite numbers ordered?
The pair (a,b)(a, b)(a,b) , ordered lexicographically: (a∣b)<(a′∣b′) ⟺ a<a′ or (a=a′ and b<b′)(a|b) < (a'|b') \iff a < a' \text{ or } (a = a' \text{ and } b < b')(a∣b)<(a′∣b′)⟺a<a′ or (a=a′ and b<b′)
[General Sets of Points] With composite numbers (a∣b)(a|b)(a∣b) (ordered lexicographically), how is each point p=(px,py)p = (p_x, p_y)p=(px,py) of a set PPP of distinct points transformed, and why?
p^=((px∣py),(py∣px))\boldsymbol{\hat{p} = ((p_x | p_y), (p_y | p_x))}p^=((px∣py),(py∣px)) Since the points of PPP are distinct, the new first coordinates are all distinct, and so are the new second coordinates. Kd-trees and range trees can then be built on Pundefined\widehat{P}P .
[General Sets of Points] Points p=(px,py)p = (p_x, p_y)p=(px,py) are replaced by p^=((px∣py),(py∣px))\hat{p} = ((p_x | p_y), (p_y | p_x))p^=((px∣py),(py∣px)) , using lexicographically ordered composite numbers (a∣b)(a|b)(a∣b) .Into what is the query range R=[x:x′]×[y:y′]R = [x : x'] \times [y : y']R=[x:x′]×[y:y′] transformed?
Rundefined=[(x∣−∞):(x′∣+∞)]×[(y∣−∞):(y′∣+∞)]\boldsymbol{\widehat{R} = [(x | -\infty) : (x' | +\infty)] \times [(y | -\infty) : (y' | +\infty)]}R=[(x∣−∞):(x′∣+∞)]×[(y∣−∞):(y′∣+∞)]
[General Sets of Points] With p^=((px∣py),(py∣px))\hat{p} = ((p_x | p_y), (p_y | p_x))p^=((px∣py),(py∣px)) and Rundefined=[(x∣−∞):(x′∣+∞)]×[(y∣−∞):(y′∣+∞)]\widehat{R} = [(x | -\infty) : (x' | +\infty)] \times [(y | -\infty) : (y' | +\infty)]R=[(x∣−∞):(x′∣+∞)]×[(y∣−∞):(y′∣+∞)] for R=[x:x′]×[y:y′]R = [x : x'] \times [y : y']R=[x:x′]×[y:y′] : why is p∈R ⟺ p^∈Rundefinedp \in R \iff \hat{p} \in \widehat{R}p∈R⟺p^∈R ?
x≤px≤x′ ⟺ (x∣−∞)≤(px∣py)≤(x′∣+∞)x \le p_x \le x' \iff (x | -\infty) \le (p_x | p_y) \le (x' | +\infty)x≤px≤x′⟺(x∣−∞)≤(px∣py)≤(x′∣+∞) in the lexicographic order, and likewise for yyy .
[General Sets of Points] p=(3,7)p = (3, 7)p=(3,7) and q=(3,4)q = (3, 4)q=(3,4) . Transformed to composite numbers, p^=((px∣py),(py∣px))\hat{p} = ((p_x | p_y), (p_y | p_x))p^=((px∣py),(py∣px)) , which of p^,q^\hat{p}, \hat{q}p^,q^ has the smaller first coordinate?
q^\hat{q}q^ : (3∣4)<(3∣7)(3|4) < (3|7)(3∣4)<(3∣7) . Equal xxx -coordinates are broken by the yyy -coordinate.
[General Sets of Points] Must the transformed points p^=((px∣py),(py∣px))\hat{p} = ((p_x | p_y), (p_y | p_x))p^=((px∣py),(py∣px)) be stored to use composite numbers in a kd-tree or range tree?
No: store the original points and compare two xxx -coordinates (or two yyy -coordinates) in the composite order. The same approach works in higher dimensions.
[Fractional Cascading] A query on a 2-dimensional range tree spends O(log⁡n+kν)O(\log n + k_\nu)O(logn+kν) in each of O(log⁡n)O(\log n)O(logn) associated structures ( kνk_\nukν = points reported there). What would reduce the query time to O(log⁡n+k)O(\log n + k)O(logn+k) ?
Searching each associated structure in O(1+kν)O(1 + k_\nu)O(1+kν) time. A single 1-dimensional range query can't be done in O(1+k)O(1 + k)O(1+k) in general; what helps is that many 1-dimensional searches are done with the same range.
[Fractional Cascading] Sets S1,S2S_1, S_2S1,S2 are stored sorted by key in arrays A1,A2A_1, A_2A1,A2 , and the keys of S2S_2S2 are a subset of those of S1S_1S1 . Which pointers avoid the binary search in A2A_2A2 when reporting the keys in [y:y′][y : y'][y:y′] ?
From each entry A1[i]A_1[i]A1[i] with key yiy_iyi , a pointer to the entry of A2A_2A2 with the smallest key ≥yi\ge y_i≥yi (nil if there is none). Binary search for yyy in A1A_1A1 only, follow the pointer from the found entry, and walk right through A2A_2A2 . Reporting from S2S_2S2 then takes O(1+k)O(1 + k)O(1+k) .
[Fractional Cascading] A1=3,10,19,23,30,37,59,62,70,80,100,105A_1 = 3, 10, 19, 23, 30, 37, 59, 62, 70, 80, 100, 105A1=3,10,19,23,30,37,59,62,70,80,100,105 and A2=10,19,30,62,70,80,100A_2 = 10, 19, 30, 62, 70, 80, 100A2=10,19,30,62,70,80,100 , with each entry of A1A_1A1 pointing to the smallest key ≥\ge≥ it in A2A_2A2 . How is the query [20:65][20 : 65][20:65] answered?
Binary search in A1A_1A1 finds 23, walk right reporting 23, 30, 37, 59, 62; follow the pointer from 23 to 30 in A2A_2A2 and walk right reporting 30, 62. Each walk stops at the first key larger than 65.
[Fractional Cascading] What is a layered range tree?
A 2-dimensional range tree whose associated structures are arrays A(ν)A(\nu)A(ν) sorted on yyy , where each entry of A(ν)A(\nu)A(ν) points into A(lc(ν))A(lc(\nu))A(lc(ν)) and A(rc(ν))A(rc(\nu))A(rc(ν)) . The pointer from the entry storing ppp goes to the entry with the smallest yyy -coordinate ≥py\ge p_y≥py . The array of the root on top, those of its children below; solid and dotted arrows point into the left and right child's array.
[Fractional Cascading] Why can each entry of the array A(ν)A(\nu)A(ν) in a layered range tree point to the right place in A(lc(ν))A(lc(\nu))A(lc(ν)) for every query value yyy ?
P(lc(ν))⊆P(ν)P(lc(\nu)) \subseteq P(\nu)P(lc(ν))⊆P(ν) : if ppp has the smallest yyy -coordinate ≥y\ge y≥y in P(ν)P(\nu)P(ν) , the entry p′p'p′ it points to has the smallest yyy -coordinate ≥y\ge y≥y in P(lc(ν))P(lc(\nu))P(lc(ν)) . Likewise for rc(ν)rc(\nu)rc(ν) . ( P(ν)P(\nu)P(ν) = canonical subset of ν\nuν .)
[Fractional Cascading] How does a query [x:x′]×[y:y′][x : x'] \times [y : y'][x:x′]×[y:y′] in a layered range tree reach the points with yyy -coordinate in [y:y′][y : y'][y:y′] in each selected array A(ν)A(\nu)A(ν) ?
One binary search for yyy in A(νsplit)A(\nu_{\text{split}})A(νsplit) ; then follow the pointers along both search paths, keeping the entry with smallest yyy -coordinate ≥y\ge y≥y in O(1)O(1)O(1) per node. A selected node's parent is on a search path, so its start entry costs O(1)O(1)O(1) ; walk right while the yyy -coordinate is ≤y′\le y'≤y′ , in O(1+kν)O(1 + k_\nu)O(1+kν) time.
[Fractional Cascading] A layered range tree on nnn points in the plane: what is the query time?
O(log⁡n+k)\boldsymbol{O(\log n + k)}O(logn+k) , where kkk is the number of reported points. O(log⁡n)O(\log n)O(logn) for the binary search at the split node and the two search paths, plus O(1+kν)O(1 + k_\nu)O(1+kν) at each of the O(log⁡n)O(\log n)O(logn) selected nodes.
[Fractional Cascading] Theorem 5.11 A layered range tree for a set PPP of nnn points in ddd -dimensional space ( d≥2d \ge 2d≥2 ): storage, construction time, rectangular query time?
O(nlog⁡d−1n)O(n \log^{d-1} n)O(nlogd−1n) storage and construction, O(log⁡d−1n+k)O(\log^{d-1} n + k)O(logd−1n+k) query, where kkk is the number of reported points. The ddd -dimensional query recurses down to 2-dimensional queries, which the layered structure answers in O(log⁡n+k)O(\log n + k)O(logn+k) : one logarithmic factor is saved.
[Fractional Cascading] The technique of adding pointers between sorted arrays so that one binary search speeds up many searches with the same key is called fractional cascading.
[Notes and Comments] Who first described kd-trees, and when?
Bentley, in 1975. They improved on quadtrees, one of the first structures for orthogonal range searching, whose worst-case behaviour is quite bad.
[Notes and Comments] What is the most efficient structure for 2-dimensional orthogonal range queries on nnn points (Chazelle)?
A modified layered range tree with O(nlog⁡n/log⁡log⁡n)O(n \log n / \log \log n)O(nlogn/loglogn) storage and O(log⁡n+k)O(\log n + k)O(logn+k) query time, which Chazelle also proved optimal. kkk = number of reported points. The lower bound holds only in certain models of computation.
[Notes and Comments] Which structure handles query ranges unbounded on one side, [x:x′]×[y:+∞][x : x'] \times [y : +\infty][x:x′]×[y:+∞] , with linear storage, and with what query time?
A priority search tree, with O(log⁡n+k)O(\log n + k)O(logn+k) query time. kkk = number of reported points.
[Notes and Comments] In databases, what are the three basic types of multi-dimensional queries?
Exact match, partial match and range queries. Exact match: is a point with given coordinates present? Partial match: values for only some of the coordinates are specified (in the plane: points on a given horizontal or vertical line).
[Notes and Comments] How fast can exact match queries in ddd dimensions on nnn points be answered with a binary tree on the lexicographic order?
O(dlog⁡n)O(d \log n)O(dlogn) , easily reduced to the optimal O(d+log⁡n)O(d + \log n)O(d+logn) . Comparing two points costs O(d)O(d)O(d) .
[Notes and Comments] A partial match query on a ddd -dimensional kd-tree with nnn points specifies s<ds < ds<d of the coordinates. What is the query time?
O(n1−s/d+k)\boldsymbol{O(n^{1 - s/d} + k)}O(n1−s/d+k) , where kkk is the number of reported points.