Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k

Full text

Pdf (824 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 322 - 330

Year of Publication: 1990

ISBN:0-89791-361-2

Author

K. Mulmuley

The University of Chicago

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 13, Citation Count: 4

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/100216.100259 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	A. Aggarwal , L. Guibas , J. Saxe , P. Shor, A Linear time algorithm for computing the Voronoi diagram of a convex polygon, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.39-45, January 1987, New York, New York, United States [doi>10.1145/28395.28400]
	2	Brugggesser H., Mani P., "Shellable decompositions of cells and spheres", Math. Scand. 29(1971), 197-205.
	3	K. Clarkson, "New applications of random sampling in computational geometry", Disc. and Comp. Geom. 2, 1987.
	4	K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
	5	K. Clarkson, "A Las Vegas algorithm for linear programming when the dimension is small", FOCS 88.
	6	K. Clarkson, Edelsbrunner H., Guibas L., Sharir M., Welzl E., Combinatorial complexity bounds for arrangements of curves and surfaces, Proceeddings of the 29th FOCS, 1988.
	7	H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
	8	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
	9	P. Erdhs, J. Spenser, "Probabilistic methods in Combinatorics", Academic Press/Akademiai Kiado, New-York-Budapest, 1974.
	10	D. Haussler, E. Welzl, "e-nets and simplex range querries", Discrete and Comp. Geom., 2: 127-151, 1987.
	11	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	12	D. Lee, "On k-nearest neighbour Voronoi diagrams in the plane", IEEE Trans. on Computers, vol. c-31, 1982, pp. 478-487.
	13	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	14	K. Mulmuley, "On levels in arrangements and Voronoi diagrams", to appear in Disc. and Comp. Geom. An abstract of this paper can be found in "On obstructions in relation to a fixed viewpoint", the proceedings of the FOCS 89.
	15	K. Mulmuley, "Hidden surface removal with respect to a continuously moving view point", manuscript.
	16	K. Mulmuley, "Output sensitive construction of partitions induced by (d - 1)-dimensional polytopes in Rd, manuscript.
	17	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]

CITED BY 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
	David Eppstein , Jeff Erickson, Iterated nearest neighbors and finding minimal polytypes, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.64-73, January 25-27, 1993, Austin, Texas, United States
	Ketan Mulmuley, Hidden surface removal with respect to a moving view point, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.512-522, May 05-08, 1991, New Orleans, Louisiana, United States
	Ketan Mulmuley, Dehn-Sommerville relations, upper bound theorem, and levels in arrangements, Proceedings of the ninth annual symposium on Computational geometry, p.240-246, May 18-21, 1993, San Diego, California, United States