A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Avis, D. & Fukuda, K. Discrete \& Computational Geometry, 8(1):295--313, ACM Press, New York, New York, USA, December, 1992. ![A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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 the v vertices of a polyhedron in R(d) defined by a nondegenerate system of n inequalities (or, dually, the v facets of the convex hull of n points in R(d), where each facet contains exactly d given points) in time O(ndv) and O(nd) space. The v vertices in a simple arrangement of n hyperplanes in R(d) can be found in O(n2dv) time and O(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.
@article{ Avis1992a,
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 the v vertices of a polyhedron in R(d) defined by a nondegenerate system of n inequalities (or, dually, the v facets of the convex hull of n points in R(d), where each facet contains exactly d given points) in time O(ndv) and O(nd) space. The v vertices in a simple arrangement of n hyperplanes in R(d) can be found in O(n2dv) time and O(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.},
address = {New York, New York, USA},
author = {Avis, David and Fukuda, Komei},
doi = {10.1007/BF02293050},
file = {:Users/KunihiroWASA/Dropbox/paper/1992/Avis, Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, 1992.pdf:pdf},
isbn = {0897914260},
issn = {0179-5376},
journal = {Discrete \& Computational Geometry},
month = {December},
number = {1},
pages = {295--313},
publisher = {ACM Press},
title = {{A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra}},
url = {http://link.springer.com/10.1007/BF02293050},
volume = {8},
year = {1992}
}
Downloads: 0
{"_id":"hg3gr5jJp66Qa8xoC","authorIDs":[],"author_short":["Avis, D.","Fukuda, K."],"bibbaseid":"avis-fukuda-apivotingalgorithmforconvexhullsandvertexenumerationofarrangementsandpolyhedra-1992","bibdata":{"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 the v vertices of a polyhedron in R(d) defined by a nondegenerate system of n inequalities (or, dually, the v facets of the convex hull of n points in R(d), where each facet contains exactly d given points) in time O(ndv) and O(nd) space. The v vertices in a simple arrangement of n hyperplanes in R(d) can be found in O(n2dv) time and O(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.","address":"New York, New York, USA","author":["Avis, David","Fukuda, Komei"],"author_short":["Avis, D.","Fukuda, K."],"bibtex":"@article{ Avis1992a,\n 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 the v vertices of a polyhedron in R(d) defined by a nondegenerate system of n inequalities (or, dually, the v facets of the convex hull of n points in R(d), where each facet contains exactly d given points) in time O(ndv) and O(nd) space. The v vertices in a simple arrangement of n hyperplanes in R(d) can be found in O(n2dv) time and O(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.},\n address = {New York, New York, USA},\n author = {Avis, David and Fukuda, Komei},\n doi = {10.1007/BF02293050},\n file = {:Users/KunihiroWASA/Dropbox/paper/1992/Avis, Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, 1992.pdf:pdf},\n isbn = {0897914260},\n issn = {0179-5376},\n journal = {Discrete \\& Computational Geometry},\n month = {December},\n number = {1},\n pages = {295--313},\n publisher = {ACM Press},\n title = {{A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra}},\n url = {http://link.springer.com/10.1007/BF02293050},\n volume = {8},\n year = {1992}\n}","bibtype":"article","doi":"10.1007/BF02293050","file":":Users/KunihiroWASA/Dropbox/paper/1992/Avis, Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, 1992.pdf:pdf","id":"Avis1992a","isbn":"0897914260","issn":"0179-5376","journal":"Discrete \\& Computational Geometry","key":"Avis1992a","month":"December","number":"1","pages":"295--313","publisher":"ACM Press","title":"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra","type":"article","url":"http://link.springer.com/10.1007/BF02293050","volume":"8","year":"1992","bibbaseid":"avis-fukuda-apivotingalgorithmforconvexhullsandvertexenumerationofarrangementsandpolyhedra-1992","role":"author","urls":{"Paper":"http://link.springer.com/10.1007/BF02293050"},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.915Z","downloads":0,"keywords":[],"search_terms":["pivoting","algorithm","convex","hulls","vertex","enumeration","arrangements","polyhedra","avis","fukuda"],"title":"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra","year":1992,"dataSources":["YRMeqhMHoNu9HzJoC"]}