Instance-Optimal Imprecise Convex Hull

An imprecise point set [13] is defined as a family of regions $F=(R_1,\mathrm{\dots },R_n)$, where each region $R_i$ contains a unique but unknown point $p_i$. A realisation $P\sim F$ is a sequence $P=(p_1,\mathrm{\dots },p_n)$ where $p_i\in R_i$. An input instance is a pair $(F,P)$. A retrieval operation reveals the precise location of a point $p_i$, replacing $R_i$ with $p_i$.

Let $F{\odot }_{\text{P}}B$ denote the family $F$ after retrieving all $R_i\in B$, where $B\subset F$. The aim of a reconstruction algorithm is to identify a subset $B\subset F$ such that for all realisations $P_1,P_2\sim F{\odot }_{\text{P}}B$, the algorithm’s output (e.g., the cyclic order of the region indices of the points around the convex hull) is identical for $P_1$ and $P_2$. Figure 1 illustrates an example. After retrieving the subset $B=\{R_3,R_4\}$, the cycling ordering of the convex hull vertices is identically $(p_1,p_3,p_2,p_4)$ for all realisations of $F{\odot }_{\text{P}}B$.

We evaluate reconstruction algorithms by three criteria: the preprocessing time, the total number of retrievals, and the running time per retrieval. Next, we consider instance-optimal algorithms, which minimise the total number of retrievals in the strictest sense.

Many geometric problems have been studied in imprecise geometry, including Delaunay triangulations [8, 13, 19, 25], convex hulls [9, 10], Gabriel graphs [19], and onion decompositions [17]. For these geometric problems, it is known that any reconstruction algorithm must, in the worst case, use $\mathrm{\Omega }(n)$ retrievals. Most of the existing algorithms assume that the regions in $F$ are pairwise disjoint unit disks [8, 13, 19, 25, 9, 17]. Under these assumptions, deterministic worst-case optimal algorithms exist with $O(n\log n)$ preprocessing time, $O(n)$ retrievals, and $O(n)$ reconstruction time. Ezra and Mulzer [10] allow $F$ to consist of arbitrary lines and reconstruct the convex hull using $O(n)$ retrievals and $O(n\cdot \alpha (n))$ expected time where $\alpha (n)$ denotes the inverse Ackermann function. Buchin, Löffler, Morin and Mulzer [3] permit overlapping unit disks of ply $k$ (i.e., at most $k$ disks intersect each point in the plane). We summarize these results in the top three rows of Table 1.

In many instances, worst case bounds are overly pessimistic. Intuitively, an algorithm is instance-optimal if, for every input $(F,P)$, no other algorithm performs better on that instance. Constructing instance-optimal algorithms is challenging, as they must match every alternative algorithm, including those tailored for specific instances.

Afshani, Barbay, and Chan [1] proved that, for many geometric problems including constructing the convex hull, instance-optimal reconstruction time is unachievable. Likewise, it is easy to see that instance-optimality in the number of retrievals cannot be guaranteed in general: E.g., let $F$ consist of two overlapping intervals $R_1$ and $R_2$ in $ℝ$, with $R_1\setminus R_2\ne \mathrm{\varnothing }$ and $R_2\setminus R_1\ne \mathrm{\varnothing }$. Define $P_1$ with $p_1\in R_1\setminus R_2$ and $p_2\in R_1\cap R_2$, and $P_2$ with $p_1\in R_1\cap R_2$ and $p_2\in R_2\setminus R_1$. In $(F,P_1)$, retrieving $R_1$ suffices; in $(F,P_2)$, retrieving $R_2$ suffices. No algorithm can distinguish between the two instances without making a retrieval, and hence must use two retrievals on one of the instances. Since exact instance-optimality cannot be obtained, we instead aim for asymptotic instance-optimality.

Formally, we denote for any input instance by $r(F,P)$ the minimum integer such that there exists a subset $B\subset F$ of size $r(F,P)$ where all realizations $P^{\prime }\sim (F{\odot }_{\text{P}}B)$ have the same vertex-ordering along the convex hull of $P^{\prime }$. We note that $r(F,P)$ is, equivalently, the optimal number of retrievals. We say that an algorithm is instance-optimal if for all inputs $(F,P)$ it uses $\mathrm{\Theta }(r(F,P))$ retrievals. We highlight that $r(F,P)$ depends on both the region family $F$ and the specific realisation $P$. To illustrate, suppose $F$ consists of nested rectangles $R_n\subset R_{n-1}\subset \mathrm{\dots }\subset R_1$. If $P\sim F$ is such that the convex hull of $(p_1,p_2,p_3,p_4)$ contains all of $R_5$, then retrieving just those four suffices: $r(F,P)=4$. But if all $p_i$ coincide then $r(F,P)=n$.

Only a few instance-optimal reconstruction algorithms are known (see Table 1). Bruce, Hoffmann, Krizanc, and Raman [2] presented the first such algorithm for the convex hull. Their approach is computationally expensive, using an unspecified but superlinear time per retrieval (we discuss this in detail in the full version). Subsequent works show that polylogarithmic time per retrieval is achievable, albeit on geometric structures that are much simpler than the convex hull.

Van der Hoog, Kostitsyna, Löffler, and Speckmann [21] introduced the first near-linear instance-optimal algorithm, solving the sorting problem for one-dimensional intervals. Their algorithm preprocesses the intervals in $O(n\log n)$ time and uses $\mathrm{\Theta }(r(F,P))$ retrievals, with at most logarithmic time per retrieval. Later, Van der Hoog, Kostitsyna, Löffler, and Speckmann [22] extended this approach to two-dimensional inputs for Pareto front reconstruction, under the assumption that $F$ consists of pairwise disjoint axis-aligned rectangles. Their method also guarantees at most logarithmic time per retrieval.

Here, we show that polylogarithmic time per retrieval is achievable for reconstructing the convex hull with an instance-optimal number of retrievals. Moreover, our work generalises previous works in that we can handle overlapping regions in two dimensions, whereas previous works could only support one-dimensional inputs or disjoint two dimensional inputs.

Simultaneously and independently of this paper, Löffler and Raichel [18] developed an algorithm for reconstructing the convex hull when $F$ is a set of unit disks of ply $k$. Their number of retrievals (Table 1) is not instance-optimal but rather worst-case optimal for every instance $F$. Formally, they use $O(w(F))$ retrievals for some region-dependent value $w(F)$ with $r(F,P)\le w(F)\le n$. We discuss their result in more detail in the full version.

The study of instance-optimal algorithms extends beyond computational geometry. A prime example is sorting under partial information. Given a partial order $O$ over a set $X$ and an unknown linear extension $L$, the goal is to sort $X$ using a minimum number of comparisons, where a comparison queries the order of a pair $(x,y)\in X$ under $L$. This is directly analogous to retrievals. Kahn and Saks [16] introduced an exponential-time algorithm that is instance-optimal in the number of comparisons. Since then, significant progress has been made on improving the runtime of such algorithms [15, 5], culminating in near-linear time algorithms that are instance-optimal in both runtime and comparisons [24, 23, 12]. Another example is the bidirectional shortest path problem. Haeupler, Hladík, Rozhoň, Tarjan, and Tětek [11] show an algorithm that finds the shortest path between two nodes $s$ and $t$ using an instance-optimal number of edge-weight comparisons.

We present the first algorithm for convex hull reconstruction that is instance-optimal while only requiring polylogarithmic time per retrieval. If $F$ is a family of $n$ constant-complexity simple polygons, we preprocess $F$ in $O(n{\log }^{3}n)$ time and reconstruct the convex hull of any $P\sim F$ using $\mathrm{\Theta }(r(F,P))$ retrievals and $O(r(F,P){\log }^{3}n)$ total time. Our approach applies to simple $k$-gons with a linear factor in $k$ in space and time, to pairwise disjoint disks with radii in $[1,k]$, and to unit disks of ply $k$ (see Table 1). Compared to previous approaches for convex hulls that achieve optimal retrieval counts [2], we exponentially improve the runtime per retrieval from polynomial to polylogarithmic. Compared to near-linear time algorithms for convex hulls (or, Delaunay triangulations) [8, 13, 19, 18, 25, 9, 10], we significantly reduce the number of retrievals used and broaden the generality of input families. The latter comes at a cost of a polylogarithmic slowdown if $r(F,P)$ is linear in $n$.

In Section 2, we provide some preliminaries. Then, in Section 3, we present our general algorithm for reconstructing the convex hull and prove its optimality (Theorem 18). In Section 4, we present a data structure for simple $k$-gons and give an instance-optimal algorithm that uses $O(kn)$ space and $O(r(F,P)\cdot k^2{\log }^3(kn))$ time (Theorem 33). In the full version we improve the dependency on $k$ to near-linear (Theorem 34). In the full version, we study pairwise disjoint disks with a radius in $[1,k]$, or, unit disks with ply $k$.

Given a family of regions $F$, a retrieval operation on a non-point region $R_i$ replaces $R_i$ with its associated point $p_i$ (thereby updating $F$). We write $F{\odot }_{\text{P}}A$ for the family resulting from retrieving all regions in $A\subseteq F$. We denote by $F-A$ the family obtained by removing all regions in $A$ from $F$. This removal is used in our analysis when we identify regions whose corresponding points cannot appear on the convex hull.

Since all regions in $F$ are closed, we claim that we must assume $P$ may contain duplicates and require that the convex hull of a point sequence includes all collinear and duplicate points. To illustrate, let $F$ consist of $n$ identical unit squares, and suppose $P\sim F$ includes four points forming the corners of one square. A lucky algorithm might retrieve these four points first and construct the convex hull [14]. If we assumed general position or excluded duplicates from the convex hull, this algorithm could then conclude that all remaining points cannot lie on the convex hull and terminate early. However, such behaviour cannot be guaranteed against an adversary. Since all regions are indistinguishable, an adversary may simply give these four points last. Alternatively, if $F$ consisted of open regions, we could assume general position and exclude duplicates.

We focus on the upper quarter convex hull of $P$. The other three quarters can be constructed analogously, and the full convex hull results from combining them. Let $\mathrm{CH}(P)$ denote the upper quarter convex hull: the boundary of the smallest convex set containing $P\cup \{(-\mathrm{\infty },-\mathrm{\infty }),(+\mathrm{\infty },-\mathrm{\infty })\}$. We assume that $(R_{n+1},R_{n+2})=(\{(-\mathrm{\infty },-\mathrm{\infty })\},\{(+\mathrm{\infty },-\mathrm{\infty })\})$, with corresponding points $(p_{n+1},p_{n+2})$. These are always included in $F$ and $P$. For any family of regions $F$, we denote by $\mathrm{OCH}(F)$ the upper quarter outer convex hull: the boundary of the smallest convex area enclosing all regions in $F$. Thus, $\mathrm{CH}(P)$ and $\mathrm{OCH}(F)$ represent convex hulls over point sequences and region families, respectively. As convex hulls define boundary curves, we may say that a point $p\in {ℝ}^2$ lies on, inside, or outside $\mathrm{CH}(P)$ or $\mathrm{OCH}(F)$.

We define convex hull vertices and edges of $\mathrm{OCH}(F)$. Although intuitive in simpler settings, these concepts require care due to the generality of $F$.

Intuitively, the edges of $\mathrm{OCH}(F)$ connect successive vertices lying on its boundary. Due to potential overlaps between regions, vertices may coincide. As illustrated in Figure 2(c), a single edge may therefore be considered to connect different pairs of overlapping vertices. To avoid such degeneracy, we define $V(F)={\bigcup }_{R\in F}V(R)$ as a set, and define edges robustly:

Note that a disk has infinitely many vertices but no edges under these definitions. We also define when a region appears on the outer convex hull:

We will retrieve regions until all realisations $P^{\prime }\sim F$ yield the same ordering of points along their convex hull. We formalise this via a partial order:

We say a family $F$ is finished if all realisations $P_1,P_2\sim F$ satisfy $\mathrm{⪯}(\mathrm{CH}(P_1))=\mathrm{⪯}(\mathrm{CH}(P_2))$. A reconstruction algorithm retrieves some $B\subseteq F$ such that $F{\odot }_{\text{P}}B$ is finished. Let $r(F,P)$ denote the minimum number of retrievals needed by any such algorithm.

A reconstruction algorithm is instance-optimal if for all inputs $(F,P)$ it retrieves $\mathrm{\Theta }(r(F,P))$ regions before $F$ is finished. We distinguish two types of reconstruction algorithms:

• $\mathrm{■}$

  A reconstruction strategy is any such algorithm, analysed only by the number of retrievals.

• $\mathrm{■}$

  A reconstruction program is a reconstruction algorithm executed on a pointer machine or RAM, and is analysed by both retrievals and instructions.

Bruce, Hoffmann, Krizanc, and Raman [2] present an instance-optimal reconstruction strategy for region families $F$ consisting of points and closed piecewise-$C^1$ regions. They do not present a corresponding reconstruction program. When $F$ consists of disks or polygons, a reconstruction program may be derived, albeit with unspecified polynomial-time costs per retrieval. We further discuss their algorithm in the full version. We rely on a key concept of their paper, i.e. a witness.

We observe that a reconstruction strategy is instance-optimal if, at each step, it retrieves all regions from a constant-size witness set of $F$.

Within each leaf of $T$, corresponding to a vertex $v\in V(F)$, we maintain two doubly linked lists. The point region list stores all point regions that are $v$. The non-point region list stores the other regions $R\in F$ where $v\in V(R)$. Recall that Algorithm 1 retrieves regions corresponding to the endpoint of edges that are:

For every node $\nu \in T$ with bridge $e(\nu )=(s,t)$, we maintain pointers to the leaves containing $s$ and $t$, along with Boolean flags indicating whether $e(\nu )$ is canonical or dividing. An update to $F$ may make $O(n)$ edges occupied. So instead, we maintain a different property (Fig. 7):

Recall Definition 7, where for $\nu \in T$, $𝔼(\nu )$ denotes a balanced binary tree on $\mathrm{CH}(\nu )$. The PHT stores in $\nu$ a concatenable queue ${𝔼}^{\ast }(\nu )$ which is $𝔼(\nu )$ minus all edges that are in $𝔼(w)$ where $w$ is the parent of $\nu$. We further augment the data structure by maintaining four balanced trees associated with ${𝔼}^{\ast }(\nu )$, where edges are ordered by their appearance in ${𝔼}^{\ast }(\nu )$:

1. 1.

   a tree ${\mathrm{\Lambda }}^{\ast }(\nu )$ storing all edges $(s,t)\in {𝔼}^{\ast }(\nu )$ that are non-canonical in $F$,

2. 2.

   a tree storing all edges $(s,t)\in {𝔼}^{\ast }(\nu )$ that are canonical and non-dividing in $F$,

3. 3.

   a tree storing all contiguous subchains of ${𝔼}^{\ast }(\nu )$ that are spanning in $F$,

4. 4.

   a tree storing all contiguous subchains of ${𝔼}^{\ast }(\nu )$ that are hit in $F$.

We only give the first tree a name since all others are maintained in similar fashion. We denote by ${\mathrm{\Lambda }}_{\nu }$ a balanced tree on all non-canonical edges in $𝔼(\nu )$.

We store for every region in $F$ their maximum and minimum $x$-coordinate, this way we can test if a pair of regions is vertically separated in constant time.

Our data structure maintains for each $\nu \in T$, a collection of special edges and special chains. We observe that these chains have a special structure:

Suppose two candidate chains $C$ and $C^{\prime }$ share $(s,t)$. By the definition of candidate chains, $(s,t)$ must be the final edge of $C$ and the first edge of $C^{\prime }$. First, identify the up to two length-3 chains in $𝔼(\nu )$ containing $(s,t)$. Check each such chain in $O(1)$ time for the dividing property by consulting the Boolean flags. If all edges are dividing, we apply Observation 21 to test whether the chain satisfies the conditions of a candidate chain.

Next, consider candidate chains of length $\ge 4$ in which $(s,t)$ is an interior edge. Check, in $O(1)$ time via Observation 21, whether both $s$ and $t$ lie in a unique region $R_b$. If so, perform an in-order traversal of $𝔼(\nu )$ – moving up to $O(k)$ steps left from $s$ and up to $O(k)$ steps right from $t$ – to find the maximal contiguous chain with all edges dividing and interior vertices contained in $V(R_b)$. The chain ends when we encounter an edge whose endpoints do not lie entirely in $V(R_b)$. This identifies the unique candidate chain $C$ of length $\ge 4$ containing $(s,t)$ as an interior edge. To find chains where $(s,t)$ is the first or last edge, apply the above procedure to the edges immediately before and after $(s,t)$. $◀$

After each retrieval, we update bridges for all nodes along $O(k)$ root-to-leaf paths in $T$. For each bridge $(s,t)$, we update its leaf pointers with constant overhead. Corollaries 27, 28, 30, and 32 show how to determine whether a bridge is canonical, dividing, part of a spanning chain, or part of a hit chain in $F$, respectively, in $O(k{\log }^{2}m)$ time. Since the recourse per retrieval is $O(k\log m)$, this yields an overall update time of $O(k^2{\log }^{3}m)$.

Test, using Observation 26, whether any bridge is canonical in constant time. Since the recourse is $O(k\log m)$, the set of all bridges can be updated without incurring asymptotic overhead.

To maintain ${\mathrm{\Lambda }}^{\ast }(\nu )$ for each node $\nu \in T$, we follow the technique from [20] for concatenable queues. For any node $\nu$ with child $x$, compute $\mathrm{\Lambda }(x)$ from $(\mathrm{\Lambda }(\nu ),e(\nu ),{\mathrm{\Lambda }}^{\ast }(x))$ in $O(\log m)$ time by splitting $\mathrm{\Lambda }(\nu )$ at the bridge $e(\nu )$, and joining the result with ${\mathrm{\Lambda }}^{\ast }(x)$. Traverse all $O(k)$ updated root-to-leaf paths, using the split operation, in $O(k{\log }^{2}m)$ total time. Then, traverse the paths bottom-up. At each node $\nu$ with children $x$ and $y$, we have access to the newly updated trees $\mathrm{\Lambda }(x)$ and $\mathrm{\Lambda }(y)$. Compute $(\mathrm{\Lambda }(\nu ),{\mathrm{\Lambda }}^{\ast }(x),{\mathrm{\Lambda }}^{\ast }(y))$ by splitting $\mathrm{\Lambda }(x)$ and $\mathrm{\Lambda }(y)$ at the endpoints of the new bridge $e(\nu )$ and joining the result. $◀$

The set of bridges has $O(k\log m)$ recourse. Once a bridge is known to be canonical, we apply Observation 21 to determine the unique areas $R(s)$ and $R(t)$ containing $s$ and $t$. We then test in constant time whether $R(s)$ and $R(t)$ are vertically separated, using stored $x$-coordinates. The tree is maintained using the same procedure as in Corollary 27. $◀$

Apply Lemma 25 to obtain all $O(1)$ candidate chains in $𝔼(\nu )$ containing $(s,t)$. Let $C=(q,\mathrm{\dots },r^{\prime })$ be such a chain. To test whether $C$ is spanning in $F$, use Observation 21 to find the unique regions $R(q)$, $R_b$, and $R(r^{\prime })$. Construct $\mathrm{OCH}(R(q)\cup R(r^{\prime }))$ in $O(k\log k)$ time and perform a convex hull intersection test with $R_b$ in $O(\log m)$ time using the algorithm of Chazelle [6]. The chain is spanning if and only if this test returns true. $◀$

Whenever the set of leaves of a node $\nu \in T$ changes (which occurs for $O(k\log m)$ nodes), invoke Lemma 29 on $e(\nu )$ to maintain all chains that are spanning in $F$ (and contiguous subchains of $\mathrm{CH}(\nu )$ but not of $\mathrm{CH}(x)$ or $\mathrm{CH}(y)$). The balanced binary tree associated to ${𝔼}^{\ast }(\nu )$ can be maintained in an identical manner as previous corollaries. $◀$

Apply Lemma 25 to find all candidate chains containing $(x,y)$. Then, for each candidate chain, consider the adjacent edge and apply the lemma again to construct all possible hit chains. For each resulting subchain, test whether the middle edge i$(s,t)$ is occupied as follows: Construct $\mathrm{band}(R(s),R(t))$ in $O(k\log k)$ time [7]. Temporarily remove $R(s)$ and $R(t)$ from $F$, and delete $s$ and $t$ from $V(F)$, in $O(k{\log }^{2}m)$ time. Update the corresponding PHT $T^{\prime }$ without updating auxiliary data. The hull $\mathrm{CH}(V(F)\setminus \{s,t\})$ is stored at the root of $T^{\prime }$. By intersection testing between $\mathrm{band}(R(s),R(t))$ and $\mathrm{CH}(T^{\prime })$ in $O(\log m)$ time [6], we can test if any hit chain is occupied. $◀$

As with Corollary 30, we invoke Lemma 31 on $O(k\log m)$ nodes where the leaf set changes. For each, we update the associated trees using split and join operations. $◀$

By Corollaries 27, 28, 30, and 32, we may maintain our augmented Partial Hull Tree in $O(k^2{\log }^3(kn))$ time per retrieval. This data structure maintains at its root four balanced trees storing all: non-canonical edges, canonical but non-dividing edges; subchains of $\mathrm{OCH}(F)$ that are spanning in $F$, or hit in $F$. We observe that Algorithm 1 only considers occupied edges if all edges on $\mathrm{OCH}(F)$ are dividing. Then, any occupied edge corresponds to a hit subchain. Thus, we may immediately use these trees to execute Algorithm 1. This procedure performs $O(r(F,P))$ retrievals and so the theorem follows. $◀$

In the full version, we note that our approach has two bottlenecks. First, the algorithm from Lemma 25 may “skip” over $O(k)$ edges to find the largest candidate chain. By applying a technique similar to skip-lists, we improve its running time by a factor $k$. Secondly, our approach frequently uses a subroutine where for any two regions $R(s)$ and $R(t)$ we construct $\mathrm{band}(R(s),R(t))$ in $O(k\log k)$ time. We show that by storing for each region $R_i$ its convex hull, this construction time becomes polylogarithmic and we obtain the following: