A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra |
| |
Authors: | David Avis Komei Fukuda |
| |
Institution: | 1. School of Computer Science, McGill University, 3480 University Street, H3A 2A7, Montreal, Quebec, Canada 2. Graduate School of Systems Management, University of Tsukuba, Otsuka, Bunkyo-ku, 112, Tokyo, Japan
|
| |
Abstract: | We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the
convex hull of a set of points, or for the enumeration of the vertices of an arrangement or of a convex polyhedron, in arbitrary
dimension. The algorithm has the following properties:
(a) |
Virtually no additional storage is required beyond the input data.
|
(b) |
The output list produced is free of duplicates.
|
(c) |
The algorithm is extremely simple, requires no data structures, and handles all degenerate cases.
|
(d) |
The running time is output sensitive for nondegenerate inputs.
|
(e) |
The algorithm is easy to parallelize efficiently.
|
For example, the algorithm finds thev vertices of a polyhedron inR
d defined by a nondegenerate system ofn inequalities (or, dually, thev facets of the convex hull ofn points inR
d, where each facet contains exactlyd given points) in timeO(ndv) andO(nd) space. Thev vertices in a simple arrangement ofn hyperplanes inR
d can be found inO(n
2
dv) time andO(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|