×

zbMATH — the first resource for mathematics

A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. (English) Zbl 0752.68082
Summary: 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(n^ 2dv)\) time and \(O(nd)\) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05A15 Exact enumeration problems, generating functions
52B55 Computational aspects related to convexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Avis, D.; Chvátal, V., Notes on Bland’s Pivoting Rule, Math. Programming Study., 8, 24-34, (1978) · Zbl 0403.65025
[2] Bland, R. G., New Finite Pivoting Rules for the Simplex Method, Math. Oper. Res., 2, 103-107, (1977) · Zbl 0408.90050
[3] Chand, D. R.; Kapur, S. S., An Algorithm for Convex Polytopes, J. Assoc. Comput. Mach., 17, 78-86, (1970) · Zbl 0199.50902
[4] B. Chazelle, An Optimal Convex Hull Algorithm and New Results on Cuttings,Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 29-38, 1991.
[5] V. Chvátal,Linear Programming, Freeman, San Francisco, 1983. · Zbl 0537.90067
[6] Dyer, M. E., The Complexity of Vertex Enumeration Methods, Math. Oper. Res., 8, 381-402, (1983) · Zbl 0531.90064
[7] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987. · Zbl 0634.52001
[8] Edelsbrunner, H.; Guibas, L., Topologically Sweeping an Arrangement, J. Comput. Syst. Sci., 38, 165-194, (1989) · Zbl 0676.68013
[9] Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing Arrangements of Lines and Hyperplanes with Applications, SIAM J. Comput. Sci., 15, 341-363, (1986) · Zbl 0603.68104
[10] K. Fukuda, Oriented Matroid Programming, Ph.D. Thesis, University of Waterloo, 1982.
[11] K. Fukuda and T. Matsui, On the Finiteness of the Criss-Cross Method,European J. Oper. Res., to appear. · Zbl 0747.90062
[12] M. E. Houle, H. Imai, K. Imai, J.-M. Robert, and P. Yamamoto, Orthogonal Weighted Linear \(L\_{}\{1\} andL\_{}\{∞\}\) Approximation and Applications, Manuscript, September 1990. · Zbl 0767.68093
[13] Mattheiss, T. H.; Rubin, D. S., A Survey and Comparison of Methods for Finding all Vertices of Convex Polyhedral Sets, Math. Oper. Res., 5, 167-185, (1980) · Zbl 0442.90050
[14] T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall,The Double Description Method, Annals of Mathematical Studies, vol. 8, Princeton University Press, Princeton, NJ, 1953.
[15] Paparrizos, K., Pivoting Rules Directing the Simplex Method Through all Feasible Vertices of Klee-Minty Examples, OPSEARCH, 26, 77-95, (1989) · Zbl 0674.90063
[16] G. Rote, Degenerate Convex Hulls in High Dimensions Without Extra Storage,Proc. 8th Annual Symposium on Computational Geometry, ACM Press, New York, pp. 26-32, 1992.
[17] R. Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, Report 81-14, Department of Computer Science, University of British Columbia, 1981.
[18] R. Seidel, Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face,Proc. 1986 Symposium on the Theory of Computing, pp. 404-413.
[19] Terlaky, T., A Convergent Criss-Cross Method, Math. Operationsforsch. Statist. Ser. Optim., 16, 683-690, (1985) · Zbl 0581.90052
[20] Terlaky, T., A Finite Criss-Cross Method for Oriented Matroids, J. Combin. Theory Ser. B, 42, 319-327, (1987) · Zbl 0588.05010
[21] Todd, M., Linear and Quadratic Programming in Oriented Matroids, J. Combin. Theory Ser. B, 39, 105-133, (1985) · Zbl 0555.05026
[22] Wang, Z., A Conformal Elimination Free Algorithm for Oriented Matroid Programming, Chinese Ann. Math., 8, 1-1, (1987)
[23] D. Avis and K. Fukuda, Reverse Search for Enumeration, Research Report 92-5, GSSM, University of Tsukuba, April 1992. · Zbl 0854.68070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.