An Optimal Convex Hull Algorithm for Points Sets in Any Fixed Dimension

Abstract:

We present a deterministic algorithm for computing the convex hull of
$n$ points in $E sup d$ in optimal $O(n sup {left floor ^d/2^ right
floor})$ time, for $d^<^3$. This result settles an open question of
long standing: optimal solutions were previously known only in two and
three dimensions or alternatively by allowing randomization. The
algorithm involves a fairly elaborate dynamic search process, whose
fine points are clarified by using an analogy with statistical
thermodynamics: this allows us to uncover some unexpected phenomena
relating to the convergence of the algorithm. By duality, the
algorithm can be used to construct the full lattice structure of the
feasible set of $n$ linear constraints in optimal $O(n$ log $n^+^n sup
{left floor ^d/2^ right floor})$ time, for any fixed $d$. As an
immediate corollary, we obtain an algorithm for computing the Voronoi
diagram of $n$ points in $d$-space in optimal $O(n$ log $n^+^ n sup
{left ceiling ^d/2^ right ceiling})$ time, which is also a new result.

This technical report has been published as

An Optimal Convex Hull Algorithm in Any Fixed Dimension. Bernard
Chazelle, Discrete and Computational Geometry
10, 1993, pp. 377-409.