A Fast Incremental Convex Hull Algorithm for Higher Dimensions
Loading...
Files
Date
1990
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
An online algorithm is described which finds the facets of the convex hull of a set of points in d-dimensional space. For point sets chosen at random from some distribution, the algorithm is O(nl +F) for fixed d, where n is the number of points, l is the expected number of sides of a polygon defined by the intersection of a 2-flat with the polytope, and F is the expected number of facets.