An improved algorithm for constructing kth-order Voronoi diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An improved algorithm for constructing kth-order Voronoi diagrams

Full text

Pdf (564 KB)

Source

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

Baltimore, Maryland, United States

Pages: 228 - 234

Year of Publication: 1985

ISBN:0-89791-163-6

Authors

Bernard Chazelle	Department of Computer Science, Brown University, Providence, RI
Herbert Edelsbrunner	Institutes for Information Processing, Technical, University of Graz, SchieDstattgasse 4a., A-8010 Graz, Austria

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

Additional Information:

abstract 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/323233.323263 What is a DOI?

ABSTRACT

The kth-order Voronoi diagram of a set of points in E2 (called sites) subdivides E2 into maximal regions such that each point within a given region has the same k nearest sites. Two versions of an algorithm are developed for constructing the kth-order Voronoi diagram of a set of n sites in &Ogr;(n2logn+k(n-k)log2n) time, &Ogr;(k(n-k)) storage, and &Ogr;(n2+k(n-k)log2n) time, &Ogr;(n2) storage, respectively.

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	[B] Brown, K. Q. Voronoi diagrams for convex hulls. Inform. Process. Lett. 9 (1979), 223-228.
	2	[CGL] Chazelle, B., Guibas, L. J., and Lee, D. T. The power of geometric duality. Proc. 24th Ann. IEEE Symp. Found. Comput. Sci. (1983), 217-225.
	3	Richard Cole , Micha Sharir , Chee K. Yap, On k-hulls and related problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.154-166, December 1984 [doi>10.1145/800057.808677]
	4	[E] Edelsbrunner, H. Constructing edge-skeletons in three dimensions with applications to power diagrams and dissecting three-dimensional point-sets. Rep. F140, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1984.
	5	[EOS] Edelsbrunner, H., O'Rourke, J. and Seidel, R. Constructing arrangements of lines and hyperplanes with applications. Proc. 24th Ann. IEEE Symp. Found. Comput. Sci. (1983), 83-91.
	6	[EW] Edelsbrunner, H. and Welzl, E. Constructing belts in two-dimensional arrangements with applications. To appear in SIAM J. Comput.
	7	[L] Lee, D. T. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. C-31 (1982), 478-487.
	8	[OvL] Overmars, M. H. and van Leeuwen, J. Maintenance of configurations in the plane. J. Comput. System Sci. 23 (1981), 166-204.
	9	Michael Ian Shamos, Computational geometry., Yale University, New Haven, CT, 1978
	10	[SH] Shamos, M. I. and Hoey, D. Closest-point problems. Proc. 16th Ann. IEEE Symp. Found. Comput. Sci. (1975), 151-162.
	11	[V] Voronoi, G. Nouvelles applications des parametres continus a la theorie des formes quadratiques. J. Reine Angew. Math. 134 (1908), 198-287 and 136 (1909), 67-181.

CITED BY 2

	K L Clarkson, Further applications of random sampling to computational geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.414-423, May 28-30, 1986, Berkeley, California, United States
	Gordon Wilfong, Nearest neighbor problems, Proceedings of the seventh annual symposium on Computational geometry, p.224-233, June 10-12, 1991, North Conway, New Hampshire, United States