A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull

Afshani, Barbay, Chan prove that the algorithm by Kirkpatrick, McQueen, and Seidel [7] is universally optimal.¹¹1We note that the paper has only Kirkpatrick and Seidel as authors. However, a footnote remarks that McQueen suggests an adaption to the algorithm. Only with this adaption, the algorithm becomes universally optimal. Their proof restricts the model of computation to any algebraic decision tree model where the test functions have at most constant degree and have at most a constant number of arguments. They present an involved algebraic argument to construct a lower bound for each point set $P$ that matches the universal running time of [7].

Here, we give a different proof. Rather than restricting the model of computation, we give a more extensive but natural specification of the output. We call a point of $P$ internal if it does not appear on the boundary of the convex hull. We require that any algorithm computes (1) the convex hull and (2) for each internal point a witness for its being internal. For a point set $P$, we apply a simple combinatorial counting argument over all outputs to obtain a lower bound that matches the universal running time of [7]. Our argument is shorter, arguably simpler, and holds in more general models of computation.

Our input is an array $I_P\in {𝕀}_P$ of $n$ points $P$ in general position. Convex hull algorithms output $\mathrm{ch}(P)$ in cyclical ordering. For our analysis, we further require that the output contains, for all points in $P-\mathrm{ch}(P)$, a witness that they are internal:

Requiring the output to contain witnesses is a natural condition as it is effectively asking the algorithm $A$ to verify its correctness. The concept of certification and verifiability is central to the design of algorithms. Without this requirement, there are oblivious decision trees (defined below) that compute the convex hull in $O(k\log n)$ time.

Our output consists of two lists: A hull list $H$ encodes $\mathrm{ch}(P)$ in cyclical order, and a witness list $W$ defines for each point in $P-\mathrm{ch}(P)$ a witness. Formally, a hull list $H=(h_1,\mathrm{\dots },h_k)$ of $I_P$ is a sequence of integers such that the points $I_P[h_i]$, for $i\in [k]$, are precisely the $k$ points on the boundary of $\mathrm{CH}(P)$ in their cyclical ordering. We require that $I_P[h_1]$ is the leftmost point of $\mathrm{ch}(P)$. A witness list (we refer ahead to Figure 1) of $I_P$ is a sequence $W={(a_i,b_i,c_i)}_{i=1}^n$ of integer triples such that:

• $\mathrm{■}$

  $a_i=b_i=c_i=-1$ if $I_P[i]$ lies on $\mathrm{CH}(P)$, and otherwise

• $\mathrm{■}$

  the triangle $(I_P[a_i],I_P[b_i],I_P[c_i])$ is a witness of $I_P[i]$.

We define an algorithm for convex hull construction as any comparison-based algorithm that receives any ordered set of planar points $I_P$ and outputs a hull list and witness list of $I_P$. Given a fixed input $I_P$ and an algorithm $A$, the running time $\rho (A,I_P)$ is the number of instructions used by $A$ to terminate on the input $I_P$.

For $n\in \mathbb{N}$, we define an abstract decision tree $T$ as a tree whose inner nodes have two children. The inner nodes contain no additional information. Its leaves contain two ordered lists. The first is an arbitrary list of integers and the second is a list of $n$ integer triples. We define an oblivious decision tree $T$ as any abstract decision tree such that for any point set $P\in {\mathbb{P}}_n$, and any $I_P\in {𝕀}_P$, there exists a root-to-leaf path in $T$ where the two lists at the leaf are a hull list and witness list of $I_P$, respectively. We denote by ${𝒯}_n^O$ the set of all oblivious decision trees for $n\in \mathbb{N}$.

Let $𝒜$ denote the set of all correct algorithms. For an algorithm $A\in 𝒜$ the worst-case running time is defined as

An algorithm is worst-case optimal if there exists a constant $c$ such that, for all $n$ large enough, $\text{worst-case}(A,n)\le c\cdot \underset{A^{\prime }\in 𝒜}{\min }\text{worst-case}(A^{\prime },n).$

Afshani, Barbay and Chan [1] introduce a strictly stronger notion of algorithmic optimality which they call instance optimality in the order-oblivious setting. We will instead use the equivalent modern term universal optimality [5, 6, 9]. Intuitively, an algorithm is universally optimal if it is worst-case optimal for every fixed point set $P$. Formally, we define the universal running time of an algorithm $A$ and point set $P$ as

An algorithm is universally optimal if there exists a constant $c$ such that for all $P$, $\text{universal}(A,P)\le c\cdot \underset{A^{\prime }\in 𝒜}{\min }\text{universal}(A^{\prime },P).$ To show universal optimality, we introduce the concept of clairvoyant decision trees. For a fixed point set $P$, a clairvoyant decision tree $T$ is an abstract decision tree such that for any input $I_P\in {𝕀}_P$, there exists a root-to-leaf path in $T$ such that the two lists at the leaf are a hull list and witness list of $I_P$, respectively. We denote by ${𝒯}_P^C$ the set of all clairvoyant decision trees for a fixed planar point set $P$.

Kirkpatrick, McQueen, and Seidel [7] give an efficient algorithm to compute for any point set $P$ its convex hull. We present this algorithm in Section 4 and observe that it naturally produces a hull list and a witness list. Afshani, Barbay, and Chan [1] show that the algorithm in [7] is universally optimal in a somewhat restricted model of computation which we define below. We note for the reader that this definition is not vital to our analysis.

In the multilinear decision tree model [1], algorithms can access the input points only through tests of the form $f(p_1,\mathrm{\dots },p_c)>0$ for a multilinear function $f$ with $c$ constant.

We instead show universal optimality by a counting all possible hull and witness lists:

Any algorithm must spend $\mathrm{\Omega }(n)$ time to read the input. Denote by $\mathrm{\ell }$ the minimum height across all clairvoyant decision trees in ${𝒯}_P^C$. By Observation 7, $\mathrm{\Omega }(\mathrm{\ell })$ is a universal lower bound. What remains is to bound $\mathrm{\ell }$. Let $k=|\mathrm{ch}(P)|$. Let $T$ be an arbitrary clairvoyant decision tree in ${𝒯}_P^C$. Recall that each leaf of $T$ stores a hull list and a witness list.

For any input $I_P\in {𝕀}_P$, there is a unique hull list of $I_P$. It follows that the number of distinct hull lists, and therefore the number of distinct leaves of $T$, across all $I_P$ is at least $\frac{n!}{(n-k)!}$. Hence, $\mathrm{\ell }\ge \log (\frac{n!}{(n-k)!})\in \mathrm{\Omega }(k\log n)$. For any input $I\in {𝕀}_P$, there is at least one leaf in $T$ containing a witness list $W$ of $I$. Therefore,

$◀$

Their algorithm is recursive and it constructs the upper convex hull of $P$. The original input consists of an unordered array $I_P$, from which they find the leftmost and rightmost vertex of $P$ in linear time. Each recursive call has as input some set $S\subset P$ and two points $p_{\mathrm{\ell }},p_r\in S$ such that $(p_{\mathrm{\ell }},p_r)$ is an edge of $\mathrm{CH}(S)$ (Figure 2) – we assume that the line segment between the leftmost and rightmost vertex lies on $\mathrm{CH}(P)$. Otherwise, this line segment splits the problem into two independent convex hull construction problems.

Given $(S,p_{\mathrm{\ell }},p_r)$, the algorithm first finds a point $m\in S$ with the median $x$-coordinate in linear time. It then finds in linear time an edge $(p_i,p_j)$ of $\mathrm{CH}(P)\cap S$ with $(p_i,p_j)\ne (p_{\mathrm{\ell }},p_r)$ such that $m$ lies inside or on the quadrangle $Q=(p_{\mathrm{\ell }},p_r,p_j,p_i)$ ($Q$ may also be a triangle, for example when $p_i=p_{\mathrm{\ell }}$). The algorithm partitions $S$ in linear time into three sets:

• $\mathrm{■}$

  $S_1$ consists of all points of $S$ that lie above or on the line $p_{\mathrm{\ell }}{p}_i$,

• $\mathrm{■}$

  $S_2$ consists of all points of $S$ that lie above or on the line $p_r{p}_j$, and

• $\mathrm{■}$

  $S^{\ast }=S-S_1-S_2$. $S^{\ast }$ lies within $Q$ and, therefore, its points are not on the convex hull. Through $Q$ we assign these points a witness in $O(|S^{\ast }|)$ time at no asymptotic overhead.

The algorithm recurses on $S_1$ and $S_2$, using the segments $(p_{\mathrm{\ell }},p_i)$ and $(p_r,p_j)$, respectively.

Fix $I_P\in V(P,W)$. By our canonical ordering of the hull lists, there exists exactly one $H\in HL(P)$ for which $H$ is a hull list of $I_P$. We define our map $\mathrm{\Phi }$ by additionally constructing for $I_P$ a corner assignment $C$ and ordered downdraft $\overline{\phi }$.

For $i\in [n]$, observe that if $I_p[i]$ is not in $\mathrm{ch}(P)$ then $I_p[i]$ lies strictly inside the triangle formed by $(I_P[a_i],I_P[b_i],I_P[c_i])$. Therefore, at least one of $I_P[i]{\prec }_{𝒬}{I}_P[a_i],I_P[i]{\prec }_{𝒬}{I}_P[b_i]$ or $I_P[i]{\prec }_{𝒬}{I}_P[c_i]$ holds. We construct the corner assignment $C$ by arbitrarily choosing for each $i\in [n]$, the value $C(i)\in \{a_i,b_i,c_i\}$ such that $I_P[i]{\prec }_{𝒬}{I}_P[C(i)]$. We then construct a downdraft $\phi$ by setting $\phi (I_P[i])=I_P[C(i)]$. To obtain an ordered downdraft, we order for all $q\in P$ each fiber ${\phi }^{-1}(\{q\})$ via the following rule:

Then $\overline{\phi }$ is an ordered downdraft and we have defined the map $\mathrm{\Phi }(I_P)=(\overline{\phi },C,H)$.

We now show that this map $\mathrm{\Phi }$ is injective. Suppose that $I_P$ and $I_P^{\prime }$ are elements of $V(P,W)$ such that $\mathrm{\Phi }(I_P)=(\overline{\phi },C,H)=\mathrm{\Phi }(I_P^{\prime })$. Observe that, per definition, the hull list $H\in \mathrm{\Phi }(I_P)=\mathrm{\Phi }(I_P^{\prime })$ is a sequence of integers with the following property: if $u$ is the $x$’th point on $\mathrm{ch}(P)$ then $I_P[H[x]]=I_P^{\prime }[H[x]]=u$. Suppose for the sake of contradiction that there exist integers $i,i^{\prime }\in [n]$ with $i\ne i^{\prime }$ such that $u=I_P[i]=I_P^{\prime }[i^{\prime }]$. We pick the pair $(i,i^{\prime })$ such that $u$ is maximal in the partial order ${\prec }_{𝒬}$.

First, consider the case where $u$ is a point on $\mathrm{ch}(P)$. Let $u$ be the $x$’th element in the canonical ordering of $\mathrm{ch}(P)$. Then $u=I_P[H[x]]=I_P^{\prime }[H[x]]$. However, we chose $u$ such that $u=I_P[i]=I_P^{\prime }[i^{\prime }]$ and so $i=i^{\prime }$, a contradiction.

Alternatively, suppose that $u\notin \mathrm{ch}(P)$. By maximality of our choice of $u$, it follows that for all points $v^{\prime }$ with $u{\prec }_{𝒬}{v}^{\prime }$, there exists a unique integer $j^{\prime }$ such that $v^{\prime }=I_P[j^{\prime }]=I_P^{\prime }[j^{\prime }]$. We define $v:=\phi (u)$. By the definition of a downdraft, $u{\prec }_{𝒬}v$ and so there is a unique integer $j\in [n]$ with $v=\phi (u)=I_P[j]=I_P^{\prime }[j]$.

We observe that the objects $I_P,I_P^{\prime },\phi$ and $C$ are all maps. In Figure 4 we illustrate the diagram corresponding to these maps. Recall that $H$ is the hull list of both $\mathrm{\Phi }(I_P)$ and $\mathrm{\Phi }(I_P^{\prime })$. The left diagram in Figure 4 commutes. Indeed, by our definition of the downdraft $\phi$, we chose $\phi$ such that $\phi (I_p[x])=I_P[C(x)]$ for all $x\in [n]\setminus H$.

Consider chasing the left square of this diagram from $v=\phi (u)$ (see Figure 4, right). From $v$, we may first apply $I_P^{-1}$ to obtain $j$. We then apply $C^{-1}$ to $j$ to get a set of indices $X:=C^{-1}(I_P^{-1}(\{v\}))$. Conversely, we may chase this diagram from $v$ by first applying ${\phi }^{-1}$ to obtain a set of points, and then applying $I_P^{-1}$ to obtain a set of indices. Since the diagram commutes, also $I_P^{-1}({\phi }^{-1}(\{v\}))=X$. Next, we focus on the right square of the diagram. Since $v=I_P^{\prime }[j]$, we have $C^{-1}(I_P^{\prime -1}(\{v\}))=X$. We may chase the right square from $v$ by first applying ${\phi }^{-1}$ to obtain a set of points, and then applying $I_P^{\prime -1}$. Since this diagram commutes, it follows that $I_P^{\prime -1}({\phi }^{-1}(\{v\}))=X$ too. We now use this set $X$ to obtain a contradiction:

We assumed that $(\overline{\phi },C,H)=\mathrm{\Phi }(I_P)=\mathrm{\Phi }(I_P^{\prime })$. Recall that ${\prec }_{\overline{\phi }}$ induces a total order on ${\phi }^{-1}(\{v\})$. Per definition of $\mathrm{\Phi }(I_P)$, all points $p\in {\phi }^{-1}(\{v\})$ are ordered by their index $x$ defined via $p=I_P[x]$. The rank of a value $u$ with respect to an ordered set is its index in the order. We can consider the rank of $u$ in two sets: $X$ and ${\phi }^{-1}(\{v\})$. Recall that we ordered for all $q\in P$ each fiber ${\phi }^{-1}(\{q\})$ via the following rule:

It follows that the rank of $u$ satisfies:

Similarly,

Since $i$ and $i^{\prime }$ both have the same rank in $X$, it follows that $i=i^{\prime }$, contradiction. This shows that $I_P=I_P^{\prime }$, so our constructed map $\mathrm{\Phi }$ is injective. $◀$ The above lemma immediately implies the following relation between $V_{\max }(P)$ and $\mathrm{OD}(P,𝒬)$:

Finally, we are ready to show universal optimality of Algorithm 1:

Let $𝒬$ denote the quadrangle tree that corresponds to executing Algorithm 1. We apply Theorem 19 to note that there exists a constant $c$ such that:

By Corollary 25,

Since $\log (3)\le 2$ and $\log n^n\le 2n+\log n!$, this yields

We may now apply the universal lower bound from Theorem 12 to obtain the theorem. $◀$