caa a22 4500 469074973 CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF02293050 doi (NATIONALLICENCE)springer-10.1007/BF02293050 A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra [Elektronische Daten] [David Avis, Komei Fukuda] 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. Springer-Verlag New York Inc., 1992 Avis David School of Computer Science, McGill University, 3480 University Street, H3A 2A7, Montreal, Quebec, Canada aut Fukuda Komei Graduate School of Systems Management, University of Tsukuba, Otsuka, Bunkyo-ku, 112, Tokyo, Japan aut Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 295-313 0179-5376 8:3<295 1992 8 454 https://doi.org/10.1007/BF02293050 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293050 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Avis David School of Computer Science, McGill University, 3480 University Street, H3A 2A7, Montreal, Quebec, Canada aut NATIONALLICENCE 700 1- Fukuda Komei Graduate School of Systems Management, University of Tsukuba, Otsuka, Bunkyo-ku, 112, Tokyo, Japan aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 295-313 0179-5376 8:3<295 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer