On computing Voronoi diagrams by divide-prune-and-conquer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On computing Voronoi diagrams by divide-prune-and-conquer

Full text

Pdf (1.15 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 166 - 175

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Nancy M. Amato	Texas A&M University
Edgar A. Ramos	DIMACS/Rutgers University

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): 7, Downloads (12 Months): 24, Citation Count: 6

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/237218.237347 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	Helmut Alt , Otfried Schwarzkopf, The Voronoi diagram of curved objects, Proceedings of the eleventh annual symposium on Computational geometry, p.89-97, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220289]
	2	N.M. Amato, M.T Goodrich, and E.A. Ramos. Parallel algorithms for higher-dimensional convex hulls. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 94), 683- 694, 1994.
	3	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing faces in segment and simplex arrangements, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.672-682, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225285]
	4	F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
	5	H. Brtnnimann, B. Chazelle, and J. Matou~ek. Product range spaces, sensitive sampling, and derandomization, in Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 93), 400-409, 1993.
	6	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]
	7	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
	8	TM. Chan, J. Snoeyink, and C.-K. Yap. Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d Voronoi diagrams. Submitted to Discrete Comput. Geom.
	9	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	10	B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10 (1993) 377-409.
	11	B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica 10 (1990) 229-249.
	12	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]
	13	D.P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoret. Comput. Sci. 27 (1983) 241-253.
	14	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	15	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	16	H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142688]
	17	Herbert Edelsbrunner , Weiping Shi, An O(n log2h) time algorithm for the three-dimensional convex hull problem, SIAM Journal on Computing, v.20 n.2, p.259-269, April 1990 [doi>10.1137/0220016]
	18	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161002]
	19	M.T. Goodrich, C. (5'DQnlaing and C.-K. Yap. Constructing the Voronoi diagram of a set of line segments in parallel. Algorithmica 9 (1993) 128-141.
	20	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]
	21	R. Klein. Concrete and Abstract Voronoi diagrams. LCNS 400, Spfinger-Verlag, 1988.
	22	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
	23	Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
	24	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	25	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	26	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]
	27	John H. Reif , Sandeep Sen, Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, SIAM Journal on Computing, v.21 n.3, p.466-485, June 1992 [doi>10.1137/0221031]
	28	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]
	29	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]
	30	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	31	G. E Swart. Finding the convex hull facet by facet. Journal of Algorithms. 6 (1985) 17-48.
	32	Chee-Keng Yap, A geometric consistency theorem for a symbolic perturbation scheme, Journal of Computer and System Sciences, v.40 n.1, p.2-18, February 1990 [doi>10.1016/0022-0000(90)90016-E]

CITED BY 6

	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.705-706, January 09-11, 2000, San Francisco, California, United States
	Marina L. Gavrilova, On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets, The Journal of Supercomputing, v.22 n.1, p.87-98, May 2002
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima, Journal of Parallel and Distributed Computing, v.63 n.4, p.488-500, April 2003
	Marina L. Gavrilova, Empirical Studies of Optimization Techniques in the Event-Driven Simulation of Mechanically Alloyed Materials, The Journal of Supercomputing, v.28 n.2, p.165-176, May 2004
	A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States
	Edgar A. Ramos, Deterministic algorithms for 3-D diameter and some 2-D lower envelopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.290-299, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong