Primal-dual methods for vertex and facet enumeration (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Primal-dual methods for vertex and facet enumeration (preliminary version)

Full text

Pdf (951 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 49 - 56

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

David Bremner	School of Computer Science, McGill University, Montréal, Canada
Komei Fukuda	Department of Mathematics, Swiss Federal Institute of Technology, Lausanne and Institute for Operations Research, Swiss Federal Institute of Technology, Zurich, Switzerland
Ambros Marzetta	Institute for Theoretical Computer Science, Swiss Federal Institute of Technology, Zurich, Switzerland

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 29, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.262861 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	David Avis , Komei Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete & Computational Geometry, v.8 n.3, p.295-313, 1992 [doi>10.1007/BF02293050]
	2	A. Bl'#ndsted. Introduction to Convex Polytopes. Springer- Verlag, 1981.
	3	A. Briingger, A. Marzetta, K. Fukuda, and J. Nievergelt. The parallel search bench ZRAM and its applications. Annals of Operations Research, to appear.
	4	Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
	5	V. Chv#ttal. Linear Progranuning. W. H. Freeman, New York, NY, 1983.
	6	K. L. Clarkson. More output-sensitive geometric algorithms. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., pages 695-702, 1994.
	7	M. Dyer. The complexity of vertex enumeration methods. Math. Oper. Res., 8(3):381-402, 1983.
	8	J. Edmonds. Decomposition using Minkowski. Abstracts of the 14th International Sysmposium on Mathematical Programming, Amsterdam, 1991.
	9	Komei Fukuda , Thomas M. Liebling , François Margot, Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, Computational Geometry: Theory and Applications, v.8 n.1, p.1-12, June 1997 [doi>10.1016/0925-7721(95)00049-6]
	10	E Gritzmann and V. Klee. On the complexity of some basic problems in computational convexity: II. volume and mixed volumes. In T. Bistztricz#, E McMullen, and R. I. Weis, editors, Polytopes: abstract, convex and computational (Scarborough, ON, 1993), NATO Adv. Sci. Inst. Set. C Math. Phys. Sci., 440, pages 373-466. Kluwer Acad. Publ., Dordrecht, 1994.
	11	James P. Ignizio , Tom M. Cavalier, Linear programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
	12	P. McMullen. The maximal number of faces of a convex polytope. Mathematika, 17:179-184, 1970.
	13	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	14	R. Seidel, Output-size sensitive algorithms for constructive problems in computational geometry, Cornell University, Ithaca, NY, 1987
	15	G. Swart. Finding the convex hull facet by facet. J. Algorithms, pages 17--48, 1985.

CITED BY 2

	Nora H. Sleumer, Output-sensitive cell enumeration in hyperplane arrangements, Nordic Journal of Computing, v.6 n.2, p.137-147, Summer 1999
	Lusine Yepremyan , James E. Falk, Delaunay partitions in Rⁿ applied to non-convex programs and vertex/facet enumeration problems, Computers and Operations Research, v.32 n.4, p.793-812, April 2005