New lower bounds for convex hull problems in odd dimensions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New lower bounds for convex hull problems in odd dimensions

Full text

Pdf (978 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 1 - 9

Year of Publication: 1996

ISBN:0-89791-804-5

Author

Jeff Erickson

Computer Science Division, University of California, Berkeley, CA

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): 13, Downloads (12 Months): 44, 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/237218.237225 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	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
	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	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	4	Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220281]
	5	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	6	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]
	7	B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10:377-409, 1993.
	8	B. Chazelle and J. Matou~ek. Derandomizing an output-sensitive convex hull algorithm in three dimensions. Technical report, Dept. Comput. Sci., Princeton Univ., 1992.
	9	K. L. Clarkson. More output-sensitive geometric algorithms. In Prec. 35th Annu. IEEE Sympos. Found. Comput. Sci., pages 695-702, 1994.
	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	Jeff Erickson, Lower bounds for linear satisfiability problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.388-395, January 22-24, 1995, San Francisco, California, United States
	12	J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete Cornput. Geom., 13(1):41-57, 1995.
	13	Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2]
	14	D. Gale. Neighborly and cyclic polytopes. In V. Klee, editor, Convexity, volume VII of Prec. Symposia in Pure Mathematics, pages 225-232. Amer. Math. Soc., 1963.
	15	R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 1:132-133, 1972.
	16	B. Grfinbaum. Convex Polytopes. Wiley, New York, NY, 1967. Revised edition, V. Klee and P. Klainschmidt, editors, Graduate Texts in Mathematics, Springer-Verlag, in preparation.
	17	C. G. J. Jacobi. De functionibus alternantibus earumque divisione per productum e differentiis elementorum confiatum. J. Reine Angew. Mathematik, 22:360-371, 1841. Reprinted in Gesammelten Werke III, G. Reimer, Berlin, 1884.
	18	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	19	J. Matou~ek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10(2):215- 232, 1993.
	20	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	21	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	22	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]
	23	I. Schur. Uber eine Klasse yon Matrizen, die sich einer gegebenen Matrix zuordnen lassen. Thesis, Berlin, 1901. Reprinted in Gesammelte Abhandlungen, Springer, 1973.
	24	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	25	R. Seidel. A method for proving lower bounds for certain geometric problems. In G. T. Toussaint, editor, Computational Geometry, pages 319-334. North- Holland, Amsterdam, Netherlands, 1985.
	26	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	27	Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
	28	Jorge Stolfi, Oriented projective geometry, Academic Press Professional, Inc., San Diego, CA, 1991
	29	G. F. Swart. Finding the convex hull facet by facet. J. Algorithms, 6:17-48, 1985.
	30	Andrew Chi-Chih Yao, A Lower Bound to Finding Convex Hulls, Journal of the ACM (JACM), v.28 n.4, p.780-787, Oct. 1981 [doi>10.1145/322276.322289]
	31	G. M. Ziegler. Lectures on Polytopes, volume t52 of Graduate Texts in Mathematics. Springer-Verlag, 1994.