Degenerate convex hulls on-line in any fixed dimension

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Degenerate convex hulls on-line in any fixed dimension

Full text

Pdf (1.24 MB)

Source

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

Minneapolis, Minnesota, United States

Pages: 249 - 258

Year of Publication: 1998

ISBN:0-89791-973-4

Author

Hervé Brönnimann

INRIA Sophia-Antipolis, 2004 Route des Lucioles, B.P. 93, 06902 Sophia-Antipolis Cedex, France

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): 2, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

references 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/276884.276913 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 , David Bremner , Raimund Seidel, How good are convex hull algorithms?, Computational Geometry: Theory and Applications, v.7 n.5-6, p.265-301, April 1997 [doi>10.1016/S0925-7721(96)00023-5]
	2	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]
	3	Louis J. Billera , Anders Björner, Face numbers of polytopes and complexes, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	4	Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
	5	Jean-Daniel Boissonnat , Mariette Yvinec, Algorithmic geometry, Cambridge University Press, New York, NY, 1998
	6	E. Brisson, Representing geometric structures in d dimensions: topology and order, Proceedings of the fifth annual symposium on Computational geometry, p.218-227, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73858]
	7	Christoph Burnikel , Kurt Mehlhorn , Stefan Schirra, On degeneracy in geometric computations, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.16-23, January 23-25, 1994, Arlington, Virginia, United States
	8	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]
	9	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	10	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	11	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	12	James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
	13	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	14	B. Gritnbaum. Convex Polytopes. Wiley, New York, NY, 1967.
	15	L. Kettner. Polyhedra in half.edge data-structures. These proceedings.
	16	Günter Rote, Degenerate convex hulls in high dimensions without extra storage, Proceedings of the eighth annual symposium on Computational geometry, p.26-32, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142685]
	17	Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
	18	R. Seidel, Output-size sensitive algorithms for constructive problems in computational geometry, Cornell University, Ithaca, NY, 1987
	19	G. F. Swart. Finding the convex hull facet by facet. J. Algorithms, 6:17-48, 1985.
	20	M. Teillaud. Towards dynamic randomized algorithms in computational geometry, volume 758 of Lecture Notes Comput. Sci. Springer-Verlag, 1993.