Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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 Geometry10, 1993, pp. 377-409.