Approximating Convex Hulls via Range Queries

We first present our algorithmic result with non-adaptive orthogonal emptiness queries. Let $P\subseteq {[0,1]}^d$ be an unknown set of points and $𝒪$ be the orthogonal emptiness oracle on $P$. For an axis-parallel box $\mathrm{\square }$ in ${ℝ}^d$, let $\text{Query}(\mathrm{\square })$ denote the output of $𝒪$ when queried with $\mathrm{\square }$, which is $\mathrm{𝗒𝖾𝗌}$ if $P\cap \mathrm{\square }=\mathrm{\varnothing }$ and is $\mathrm{𝗇𝗈}$ if $P\cap \mathrm{\square }\ne \mathrm{\varnothing }$.

Our algorithm for approximating $𝒞\mathscr{H}(P)$ is very simple (presented in Algorithm 1) and is similar to the algorithm of Czumaj and Sohler [16] for testing convex position. Let $r=\lfloor q^{1/d}\rfloor$. In line 2, the sub-routine $\text{Partition}({[0,1]}^d,r)$ partitions ${[0,1]}^d$ evenly into $r^d$ cells each of which is a hypercube of side-length $\frac{1}{r}$; let $\mathrm{\Gamma }$ be the set of the $r^d$ cells. Then we query $𝒪$ with the boxes in $\mathrm{\Gamma }$, and let $A_{\mathrm{\square }}=\text{Query}(\mathrm{\square })$ for $\mathrm{\square }\in \mathrm{\Gamma }$. Define ${\mathrm{\Gamma }}_1$ as the set of cells $\mathrm{\square }\in \mathrm{\Gamma }$ with $A_{\mathrm{\square }}=\mathrm{𝗇𝗈}$ (which are just the cells containing at least one point in $P$). Finally, the algorithm simply returns $C^{\ast }=𝒞\mathscr{H}({\bigcup }_{\mathrm{\square }\in {\mathrm{\Gamma }}_1}\mathrm{\square })$. Clearly, the number of queries to $𝒪$ is at most $q$, and they are non-adaptive as the algorithm performs them at the same time.

To bound the error of our algorithm, we need the following lemma about the volume of the Minkowski sum of a convex body and a ball; we include a proof in the full version. For two convex bodies $X$ and $Y$ in ${ℝ}^d$, denote by $X+Y=\{x+y:x\in X\text{ and }y\in Y\}$ their Minkowski sum.

By construction, we have $𝒞\mathscr{H}(P)\subseteq C^{\ast }$. On the other hand, we observe that $C^{\ast }\subseteq 𝒞\mathscr{H}(P)+B$, where $B$ is the ball in ${ℝ}^d$ centered at the origin with radius $\frac{d}{r}$. As $C^{\ast }$ is a polytope, it suffices to show that every vertex of $C^{\ast }$ lies in $𝒞\mathscr{H}(P)+B$. A vertex $z$ of $C^{\ast }$ is a corner of some $\mathrm{\square }\in {\mathrm{\Gamma }}_1$. Since $A_{\mathrm{\square }}=\mathrm{𝗇𝗈}$, there exists a point $p\in P\cap \mathrm{\square }$. The distance between $z$ and $p$ is at most $\frac{d}{r}$, as the side-length of $\mathrm{\square }$ is $\frac{1}{r}$. Thus, $z\in p+B$ and $z\in 𝒞\mathscr{H}(P)+B$. It follows that $\parallel C^{\ast }\backslash 𝒞\mathscr{H}(P)\parallel \le \parallel (𝒞\mathscr{H}(P)+B)\backslash 𝒞\mathscr{H}(P)\parallel$. By Lemma 1, $\parallel (𝒞\mathscr{H}(P)+B)\backslash 𝒞\mathscr{H}(P)\parallel =O(\frac{1}{r})$. So we have $\parallel C^{\ast }\backslash 𝒞\mathscr{H}(P)\parallel =O(\frac{1}{r})=O(q^{-1/d})$.

Interestingly, the above algorithm, while being very simple, is already the best one can hope. Specifically, we show that any deterministic algorithm for Approximate Convex hull with $q$ non-adaptive orthogonal emptiness queries has error $\mathrm{\Omega }(q^{-1/d})$.

Consider such an algorithm $𝐀$. Since the $q$ queries $𝐀$ performs are non-adaptive, these queries are independent of the point set $P$ (as well as the range-emptiness oracle). Let ${\mathrm{\square }}_1,\mathrm{\dots },{\mathrm{\square }}_q$ be these queries, each of which is a box in ${ℝ}^d$. Without loss of generality, we may assume ${\mathrm{\square }}_1,\mathrm{\dots },{\mathrm{\square }}_q\subseteq {[0,1]}^d$. Set $n=\lceil q^{1/d}\rceil +1$ and $\delta =q^{-1/d}/c$ where $c$ is a sufficiently large constant (which only depends on $d$). Define a sequence $H_0,H_1,\mathrm{\dots },H_n$ of parallel hyperplanes in ${ℝ}^d$ where the equation of $H_i$ is $x_1+\mathrm{\cdots }+x_d=1+\delta i$. For $i\in [n]$, we say a box $\mathrm{\square }$ is $i$-good if $H_i\cap \mathrm{\square }\ne \mathrm{\varnothing }$ and $H_{i-1}\cap \mathrm{\square }=\mathrm{\varnothing }$. See figure 1.

We now consider adaptive orthogonal emptiness queries, and show how to approximate $𝒞\mathscr{H}(P)$ with error $O(q^{-1/(d-1)})$ via $O(q)$ queries. We shall define $2^d$ supersets of $𝒞\mathscr{H}(P)$, one-to-one corresponding to the vectors in ${\{-1,1\}}^d$. Our algorithm independently approximates these supersets and then merges them together. For each $\overrightarrow{v}=(v_1,\mathrm{\dots },v_d)\in {\{-1,1\}}^d$, let $O_v$ be the orthant $\{(x_1,\mathrm{\dots },x_d):x_i{v}_i\ge 0\text{ for all }i\in [d]\}$. We define $𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)=(𝒞\mathscr{H}(P)+O_{-\overrightarrow{v}})\cap {[0,1]}^d$. The following observation relates $𝒞\mathscr{H}(P)$ with the supersets $𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)$ (proof in full version).

Algorithm 2 presents how to approximate $𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)$ for each $\overrightarrow{v}\in {\{-1,1\}}^d$. It essentially “sandwiches” the hull between two convex boundaries, refining the estimate at each iteration. Figure 2 illustrates one such refinement step. The subroutine $\text{Subdivide}(R)$ evenly partitions the hypercube $R$ into $2^d$ smaller hypercubes (each of which has side-length half of the side-length of $R$) and returns the set of these $2^d$ hypercubes. For a hypercube $R$ and a vector $\overrightarrow{v}\in {\{-1,1\}}^d$, we define $\mathrm{𝖼𝗈𝗋}(R,\overrightarrow{v})=\arg {\max }_{p\in R}⟨p,\overrightarrow{v}⟩$ as the corner of $R$ in the direction $\overrightarrow{v}$. The algorithm starts with a set $ℛ$ of hypercubes which initially consists of only ${[0,1]}^d$, and runs in $\lceil \frac{\log q}{d-1}\rceil$ rounds. In each round, we perform emptiness queries for the hypercubes in $ℛ$, and let ${ℛ}^{\prime }\subseteq ℛ$ consist of the nonempty ones. Then define $U=𝒞{\mathscr{H}}_{\overrightarrow{v}}(\{\mathrm{𝖼𝗈𝗋}(R,\overrightarrow{v}):R\in {ℛ}^{\prime }\})$ and $L^{\prime }=𝒞{\mathscr{H}}_{\overrightarrow{v}}(\{\mathrm{𝖼𝗈𝗋}(R,-\overrightarrow{v}):R\in {ℛ}^{\prime }\})$. Let $L=L^{\prime }\setminus \partial L^{\prime }$ be the interior of $L^{\prime }$. This is simply to ensure that $\partial 𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)$ is contained in $U\setminus L$. We then take all hypercubes in $ℛ$ that intersect $U\backslash L$, partition them using the subroutine Subdivide, and let the new $ℛ$ be the set of the resulting smaller hypercubes. (Technically, we only need to consider the nonempty queries in ${ℛ}^{\prime }$, but this is equivalent in the worst case, and this way nicely ensures that our queries continue to cover all of $\partial C{H}_{\overrightarrow{v}}(P)$). Finally, we return the convex body $U$ in the last iteration as an approximation of $𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)$.

At a high level, the algorithm maintains an upper and lower bound (the sets $U$ and $L$ respectively) on the unknown convex body $𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)$. At each iteration of the loop, we reduce the error volume $\parallel (U\backslash 𝒞{\mathscr{H}}_{\overrightarrow{v}}(P))\cap {[0,1]}^d\parallel$ by half. Let $t=\lceil \frac{\log q}{d-1}\rceil$ be the number of iterations. For $i\in [t]$, denote by ${ℛ}_i$ the set $ℛ$ at the end of the $i$-th iteration of the loop, and likewise for $L_i$, $U_i$, ${ℛ}_i^{\prime }$, ${ℛ}_i^{\prime \prime }$. Without loss of generality, we assume that $\overrightarrow{v}=(1,\mathrm{\dots },1)$. The following two lemmas are used to bound the error and number of queries; their proofs are included in the full version.

As $d$ is a constant, Lemma 11 implies the number of queries in the $i$-th iteration is $O({(2^i+1)}^{d-1})$. So the total number of queries is bounded by ${\sum }_{i=1}^t{(2^i+1)}^{d-1}=O(q)$. Since each query box in the $i$-th iteration has volume $2^{-id}$, we have

By Lemma 10, this further implies $\parallel (U_t\backslash 𝒞{\mathscr{H}}_{\overrightarrow{v}}(P))\cap {[0,1]}^d\parallel =O(q^{-1/(d-1)})$, simply because $(U_t\backslash 𝒞{\mathscr{H}}_{\overrightarrow{v}}(P))\cap {[0,1]}^d\subseteq (U_t\backslash L_t)\cap {[0,1]}^d\subseteq {\bigcup }_{R\in {ℛ}_t}R$.

We run Algorithm 2 for all $\overrightarrow{v}\in {\{-1,1\}}^d$ and let $U_{\overrightarrow{v}}$ be the output for $\overrightarrow{v}$. Finally, we return $C^{\ast }=({\bigcap }_{\overrightarrow{v}\in {\{-1,1\}}^d}{U}_{\overrightarrow{v}})\cap {[0,1]}^d$ as the approximation of $𝒞\mathscr{H}(P)$. The total number of queries is still $O(q)$. To bound the error $\parallel C^{\ast }\oplus 𝒞\mathscr{H}(P)\parallel$, we first observe $𝒞\mathscr{H}(P)\subseteq C^{\ast }$. Indeed, since $𝒞{\mathscr{H}}_{\overrightarrow{v}}(P)\subseteq U_{\overrightarrow{v}}$ for all $\overrightarrow{v}\in {\{-1,1\}}^d$, we have $𝒞\mathscr{H}(P)\subseteq {\bigcap }_{\overrightarrow{v}\in {\{-1,1\}}^d}{U}_{\overrightarrow{v}}$ by Lemma 9, which implies $𝒞\mathscr{H}(P)\subseteq C^{\ast }$ because $P\subseteq {[0,1]}^d$. Again, by Lemma 9, we have

Therefore, the error of our algorithm is $O(q^{-1/(d-1)})$.

We complement this result by showing that any deterministic algorithm with $q$ adaptive orthogonal queries has error $\mathrm{\Omega }(q^{-1/(d-1)})$. The argument is similar to and simpler than that of Theorem 8, so we include the precise details in the full version. The key difference is that Lemma 3 no longer holds for adaptive queries, but we can still apply the same argument for a single pair of hyperplanes and only lose a factor $n=q^{1/d}$ in the resulting error bound.

We first present our algorithmic result with non-adaptive halfplane emptiness queries. Let $P\subseteq {[0,1]}^2$ be a (unknown) set of points. We shall show how to approximate $𝒞\mathscr{H}(P)$ with error $O(\frac{1}{q}+\delta )$ via $q$ non-adaptive queries to a $\delta$-accurate extreme halfplane oracle $ℰ$ on $P$. Setting $\delta =\frac{1}{q}$ and applying Lemma 15 yields an algorithm with error $O(1/q)$ that makes $q^2$ non-adaptive halfplane emptiness queries. Equivalently, $q$ queries achieve error $O(1\sqrt{q})$.

For a unit vector $\overrightarrow{v}\in {𝕊}^1$, let $\text{Query}(\overrightarrow{v})$ denote the output of $ℰ$ when queried with $\overrightarrow{v}$. Our algorithm for approximating $𝒞\mathscr{H}(P)$ is very simple, and is presented in Algorithm 3. Let $V=\{(\sin \frac{2i\pi }{q},\cos \frac{2i\pi }{q}):i\in [q]\}$ be $q$ unit vectors uniformly picked on ${𝕊}^1$. We query $ℰ$ with the vectors in $V$, and let $H_{\overrightarrow{v}}=\text{Query}(\overrightarrow{v})$ for all $\overrightarrow{v}\in V$. After that, we simply return $C^{\ast }\cap {[0,1]}^2$ where $C^{\ast }={\bigcap }_{\overrightarrow{v}\in V}{H}_{\overrightarrow{v}}$. Clearly, the number of queries to $ℰ$ is $q$, and they are non-adaptive as the algorithm performs them at the same time. We bound the error to $O(1/\sqrt{q})$ in the full version.

Next, we show that any deterministic algorithm that performs $q$ non-adaptive halfplane queries must have error $\mathrm{\Omega }(1/\sqrt{q})$. Consider an algorithm $𝐀$. As the $q$ queries performed by $𝐀$ are non-adaptive, they are independent of the point set $P$. Let $H_1,\mathrm{\dots },H_q$ be these queries, each of which is a halfplane in ${ℝ}^2$. For $x,y\in (0,1)$, denote by ${\mathrm{\ell }}_{x,y}$ the line that goes through the points $(x,0)$ and $(0,y)$. Also, for $X,Y\subseteq (0,1)$, define ${ℒ}_{X,Y}=\{{\mathrm{\ell }}_{x,y}:x\in X\text{ and }y\in Y\}$. Fix a parameter $\delta =\frac{1}{10\sqrt{q}}$, and let $A=\{i\delta :i\in \mathbb{Z}\}\cap [\frac{1}{3},\frac{2}{3}]$.

We first present our algorithm with adaptive halfplane emptiness queries. Let $P\subseteq {[0,1]}^2$ be a (unknown) set of points. We shall show how to approximate $𝒞\mathscr{H}(P)$ with error $O(\frac{1}{q^2}+q^2\delta )$ via $O(q\log q)$ adaptive queries to a $\delta$-accurate extreme halfplane oracle $ℰ$ on $P$. Combining this with Lemma 15 will give us the desired result.

Same as before, for a unit vector $\overrightarrow{v}\in {𝕊}^1$, let $\text{Query}(\overrightarrow{v})$ denote the output of $ℰ$ when queried with $\overrightarrow{v}$. Our algorithm for approximating $𝒞\mathscr{H}(P)$ is presented in Algorithm 4. We begin with a set $V$ of unit vectors which is initially $\{(1,0),(0,1),(-1,0),(0,-1)\}$. We query $ℰ$ with the vectors in $V$ and let $H_{\overrightarrow{v}}=\text{Query}(\overrightarrow{v})$. Then we iteratively add more vectors to $V$ and query $ℰ$ with these vectors (the repeat-until loop in the algorithm). In each round, we first compute $C^{\ast }={\bigcap }_{\overrightarrow{v}\in V}{H}_{\overrightarrow{v}}$ for the current $V$ (line 4). Then line 5 sorts the vectors in the current $V$ in clockwise order; let ${\overrightarrow{v}}_1,\mathrm{\dots },{\overrightarrow{v}}_n$ be the sorted sequence. Let ${\overrightarrow{v}}_0={\overrightarrow{v}}_n$ and ${\sigma }_i=C^{\ast }\cap \partial H_{{\overrightarrow{v}}_i}$, which is the edge of $C^{\ast }$ corresponding to the halfplane $H_{{\overrightarrow{v}}_i}$. We consider each pair $({\overrightarrow{v}}_{i-1},{\overrightarrow{v}}_i)$ of adjacent vectors satisfying $\mathrm{𝖺𝗇𝗀}({\overrightarrow{v}}_{i-1},{\overrightarrow{v}}_i)\cdot |{\sigma }_i|>\frac{1}{q^2}$, where $\mathrm{𝖺𝗇𝗀}({\overrightarrow{v}}_{i-1},{\overrightarrow{v}}_i)$ denotes the magnitude of the angle from ${\overrightarrow{v}}_{i-1}$ to ${\overrightarrow{v}}_i$. For each such pair $({\overrightarrow{v}}_{i-1},{\overrightarrow{v}}_i)$, we add a new unit vector $\overrightarrow{v}$ to $V$, which is the bisector of ${\overrightarrow{v}}_{i-1}$ and ${\overrightarrow{v}}_i$, and query $ℰ$ with $\overrightarrow{v}$ to obtain the halfplane $H_{\overrightarrow{v}}=\text{Query}(\overrightarrow{v})$. After this, we proceed to the next round. The procedure terminates when no more vectors are added to $V$ in a round. At the end, the algorithm returns the convex polygon $C^{\ast }\cap {[0,1]}^2$ as its output.