Smallest Quadrilateral

In $\textbf{Ex 1.18}$ of Jay Cummings’ $\underline{Proofs}$, the reader is asked to show (via. pigeonhole principle) that given 19 random points from the interior of a $6 \times 4$ box, the smallest quadrilateral will have an area no larger than $4$. Let’s look at a related problem.

$\textbf{N.B}$ — “Smallest Quadtrilateral” sounds like a LeetCode problem. Yuck.

Given $n$ points selected from $\left[0, 1 \right]^{2}$, can we come up with an algorithm that finds the smallest quadrilateral in “reasonable” time? The naive solution runs in ${n \choose 4} \sim O\Big(n^4)$ time, but we can do better by ignoring subsets of points that will not produce a near-optimal result. Consider the following algorithm:

1. Duplicate the points and sort them two separate arrays ($A_x$, $A_y$) by their $\textit{x}$ and $\textit{y}$ values respectively.

2. Locate each point ($p_i$) in $A_x$ and $A_y$ and access the points “near” $p_i$. We’ll use this set to compute the smallest quadrilateral which includes $p_i$ as a vertex. Formally, we build a set $S_{i}$:

   $$\begin{equation} S_i = \left\{p_j \mid \operatorname{min}\left( \ d_x\big(p_i, p_j), \ d_y\big(p_i, p_j) \ \right) \leq 3 \right\} \end{equation}$$

   Where $d_x$ and $d_y$ return the distance between the indexes of two points in $A_x$ or $A_y$. Collecting $p_i$ and its neighbors in either direction guarantees $7 \leq \lvert S_i \rvert \leq 13$.

3. With the size of $S_i$ bounded, we can apply the naive algorithm on $S_i$ and find the smallest quadrilateral which includes $p_i$ by enumerating no more than ${12 \choose 3}$ quadrilaterals.

4. We proceed by performing $\textbf{Step 2}$ and $\textbf{Step 3}$ for each of $n$ points and storing the minimal area (and optionally the associated points) observed thus far. After $n$ iterations, the result is our minimal quadrilateral.

Overall, this algorithm runs in $\mathcal{O}\big(n\ln\big(n))$ and is limited by the performance of the sort in $\textbf{Step 1}$. In $\textbf{Step 2}$, we can locate $p_i$ in either array in $\mathcal{O}\big(\log\big(n))$ and locate points “near” $p_i$ in $\mathcal{O}\big(1)$. In $\textbf{Step 3}$ we can compute the size of all quadrilaterals in $\mathcal{O}\big(1)$. The constant in $\textbf{Step 3}$ may be a little too large for comfort, but can be probably be reduced with more careful study.