An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
- 1 April 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 20 (2) , 259-269
- https://doi.org/10.1137/0220016
Abstract
An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time $O(n\log ^2 h)$and storage $O(n)$, where h is the number of extreme points. This is an improvement of the $O(nh)$ time gift-wrapping algorithm and, if $h = o(2^{\sqrt {\log _2 n} } )$, of the $O(n\log n)$ time divide-and-conquer algorithm.
Keywords
This publication has 18 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- Algorithms in Combinatorial GeometryPublished by Springer Nature ,1987
- Searching and storing similar listsJournal of Algorithms, 1986
- Optimal Point Location in a Monotone SubdivisionSIAM Journal on Computing, 1986
- Linear Time Algorithms for Two- and Three-Variable Linear ProgramsSIAM Journal on Computing, 1984
- Optimal Search in Planar SubdivisionsSIAM Journal on Computing, 1983
- Efficient Planarity TestingJournal of the ACM, 1974
- An Algorithm for Convex PolytopesJournal of the ACM, 1970