3D Dominance Range Reporting

In the problem of 3D dominance reporting, we are given a set $P$ of $n$ points in 3D. The query is given by a query point $q$, and we want to report all points $p\in P$ such that $p$ is ''dominated'' by $q$, i.e., the $x,y,z$ coordinates of $p$ are all at most those of $q$. This problem can be solved in $O(\log n + k)$ time using $O(n)$ space [A'08]. In this post, let us see how it is done.

2D Dominance Range Reporting

We first solve the 2D version. We sort $P$ in terms of their $x$ coordinates and build a binary search tree on top of it. Given a query point $q$, we use the binary search tree to reduce the problem to $O(\log n)$ 1D dominance range reporting problems. Note that this is equivalent to a concurrent point location problem. Then by the famous result of Fractional Cascading [CG'86], we can solve all the $O(\log n)$ problems in $O(n)$ space and $O(\log n + k)$ time.

A Sub-optimal 3D Dominance Reporting Solution

Now we apply the same idea to 3D. This time by building a binary search tree, we decompose a query into $O(\log n)$ 2D dominance reporting problems. Using the 2D solution, we get a $O(n)$ space, $O(\log^2n + k)$ time solution, which has the optimal space, but the query time is off by a factor of $\log n$. 

A Optimal 3D Dominance Reporting Solution

To get rid of the $\log n$ factor above, we use shallow-cuttings. We first present several definitions.

Definition 1. Let $r$ be a point in 3D, we define the level of $r$ (w.r.t. $P$) to be the number of points in $P$ dominated by $r$. The $(\le k)$-level of $P$ is defined to be the set of all points in 3D with level at most $k$.

Definition 2 ($k$-shallow cuttings). A $k$-shallow cutting for $P$ is a set $S$ of points such that the level of each point $s\in S$ is $O(k)$ and any point in the $(\le k)$-level is dominated by some point in $S$.

The following two lemmas show some nice features of shallow cuttings.

Lemma 1[A'08]. The size of a $k$-shallow cutting $S$, i.e., $|S|$, is $O(n/k)$.

Lemma 2[AAL'10, MT'98]. Given a $k$-shallow cutting $S$, we can build a structure of size $|S|$ such that given any point $q$ in 3D, we can in $O(\log n)$ time find the point $s\in S$ which dominates $q$ or report no such point exists.

With these tools in place, now we are ready ro solve the 3D dominance reporting problem.

We first build a $\log^2n$-cutting $S$. Then for each point $s\in S$, we collect all the points dominated by $s$ and build the sub-optimal 3D dominance reporting structure for them. Then we build a data structure for $S$ using Lemma 2. Finally, we build the sub-optimal 3D dominance reporting structure for $P$.

The space usage is clearly linear: each sub-optimal 3D built a point in $S$ takes $O(k)$ space and the size of $S$ is $O(n/k)$ by Lemma 1. The space for the data structure in Lemma 2 is also $O(n)$.

Given a query point $q$, we first query the data structure built using Lemma 2 for $S$ to try to find a point $s\in S$ that dominates $q$, which takes $O(\log n)$ time. If we can find such a point $s$, we use the sub-optimal structure built for it, which takes $O(\log^2\log^2n + k)=o(\log n)+O(k)$ time. On the other hand, the output size is $\Omega(\log^2 n)$, and so the query time will be $O(k)$. So the total query time is $O(\log n + k)$.

References:

[A'08] Afshani, Peyman. "On dominance reporting in 3D." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 2008.

[AAL'10] Afshani, Peyman, Lars Arge, and Kasper Dalgaard Larsen. "Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements." Proceedings of the twenty-sixth annual symposium on Computational geometry. 2010.

[CG'86] Chazelle, Bernard, and Leonidas J. Guibas. "Fractional cascading: I. A data structuring technique." Algorithmica 1.1 (1986): 133-162.

[MT'98] Makris, Christos, and Athanasios Tsakalidis. "Algorithms for three-dimensional dominance searching in linear space." Information Processing Letters 66.6 (1998): 277-283.