An Optimal Convex Hull Algorithm for Points Sets in Any Fixed Dimension
Report ID: TR-336-91Author: Chazelle, Bernard
Date: 1991-06-00
Pages: 37
Download Formats: |PDF|
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.