Two-Dimensional Voronoi Diagrams in the Lp-Metric

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two-Dimensional Voronoi Diagrams in the Lp-Metric

Full text

Pdf (805 KB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 4 (October 1980) table of contents

Pages: 604 - 618

Year of Publication: 1980

ISSN:0004-5411

Author

D. T. Lee

Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, Illinois and University of Illinois at Urbana-Champaign, Urbana, Illinois

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 98, Citation Count: 24

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/322217.322219 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	CHERITON, R, AND TAR JAN, R E Finding minimum spanning trees SIAM J Comput S(1976), 724-742
	2	DOBKIN, D, AND LIPTON, R On the complexity of computauons under varying sets of pnm Comput and Syst Sct 18 (1979), 86-91
	3	Michael L. Fredman , Bruce Weide, On the complexity of computing the measure of ∪[a_i,b_i], Communications of the ACM, v.21 n.7, p.540-544, July 1978 [doi>10.1145/359545.359553]
	4	HORTON, R E Rational study of rainfall data makes possible better estimates of water yield Engmeermg News-Record (1917), 211-213
	5	F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
	6	KOPEC, R J An alternative method for the construction of Thiessen polygons Professional Geographer 15 (1963), 24-26
	7	LEE, D T On finding k-nearest neighbors in the plane Masters Thesis, Umv of llhnols, Urbana, 111, 1976 Avadable as Tech Rep R-728, Coordinated Science Lab, Umv of ilhnols. Urbana, i11, May 1976
	8	LEE, D T, AND PREPARATA, F P Location of a point in a planar subdivision and Its apphcauons SIA M J Comput 6 (1977), 594-606
	9	LEE, D T, AND WONG, C K Voronol dmgrams in L~(L=) memcs wRh 2-dimensional storage applications SlAM J Comput 9 (1980), 200--211
	10	PREPARATA, F P, Ed Steps into computational geometry Tech Rep R-760, Coordinated Soence Lab, Umv of Illinois. Urbana, Ill, March 1977
	11	PREPARATA, F P A new approach to planar point location Tech Rep ACT-I I, Coordinated Science Lab. Umv of Ilhnols, Urbana, I11, Aug 1979
	12	RaY~qSBURC~ER, D. Analytical delineation of Thl~ssin polygons. Geographic Analysis 5 (1973), 133-144.
	13	ROGER, C.A. Packing and Covenng. Cambridge Umverslty Press, Cambridge, England, 1964.
	14	SH~,vlOS, M.I. Computational Geometry. Springer-Verlag, to appear.
	15	SHAMOS, M.I., AND HOEY, D.Closest-point problems. Proc. 16th IEEE Symp on Foundations of Computer Science, Berkeley, Calif., Oct. 1975, pp. 151-162.
	16	THIr~SEN, A.H. Precipitation averages for large areas. Monthly Weather Review 39 (1911), 1082-1084.
	17	YAO, A.An O(IEllog log{ VI) algorithm for muumum spanning trees. Inf. Process Lett. 4 (1975), 21-23.

CITED BY 24

	Robert L. (Scot) Drysdale, III, A practical algorithm for computing the Delaunay triangulation for convex distance functions, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.159-168, January 22-24, 1990, San Francisco, California, United States
	C. Wang , L. Schubert, An optimal algorithm for constructing the Delaunay triangulation of a set of line segments, Proceedings of the third annual symposium on Computational geometry, p.223-232, June 08-10, 1987, Waterloo, Ontario, Canada
	Sergei N. Bespamyatnikh, An efficient algorithm for the three-dimensional diameter problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 25-27, 1998, San Francisco, California, United States
	Niels Catsimpoolas , Jed Marti, Scripting highly autonomous simulation behavior using case-based reasoning, Proceedings of the 25th annual symposium on Simulation, p.13-19, April 1992, Orlando, Florida, United States
	J. W. Jaromczyk , M. Kowaluk, A note on relative neighborhood graphs, Proceedings of the third annual symposium on Computational geometry, p.233-241, June 08-10, 1987, Waterloo, Ontario, Canada
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	B. Aronov, On the geodesic Voronoi diagram of point sites in a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.39-49, June 08-10, 1987, Waterloo, Ontario, Canada
	Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.39-50, June 05-07, 1995, Vancouver, British Columbia, Canada
	C.-S. Jeong , T. D. Lee, Parallel geometric algorithms on mesh-connected computers, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.311-318, December 1987, Dallas, Texas, United States
	Ying-Meng Li , Marwan A. Jabri, A zero-skew clock routing scheme for VLSI circuits, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.458-463, November 1992, Santa Clara, California, United States
	Christian Icking , Rolf Klein , Ngoc-Minh Lê , Lihong Ma, Convex distance functions in 3-space are different, Proceedings of the ninth annual symposium on Computational geometry, p.116-123, May 18-21, 1993, San Diego, California, United States
	R A Dwyer, A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time, Proceedings of the second annual symposium on Computational geometry, p.276-284, June 02-04, 1986, Yorktown Heights, New York, United States
	A. Corbalan , M. Mazon , T. Recio , F. Santos, On the topological shape of planar Voronoi diagrams, Proceedings of the ninth annual symposium on Computational geometry, p.109-115, May 18-21, 1993, San Diego, California, United States
	David Dobkin , Subhash Suri, Maintenance of geometric extrema ∈ , Journal of the ACM (JACM), v.38 n.2, p.275-298, April 1991
	Yirng-An Chen , Youn-Long Lin , Long-Wen Chang, A Systolic Algorithm for the k-Nearest Neighbors Problem, IEEE Transactions on Computers, v.41 n.1, p.103-108, January 1992
	Vladimir Estivill-Castro , Ickjai Lee, Fast spatial clustering with different metrics and in the presence of obstacles, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA
	J. J. Little , G. E. Blelloch , T. A. Cass, Algorithmic Techniques for Computer Vision on a Fine-Grained Parallel Machine, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.3, p.244-257, March 1989
	Michael A. Bekos , Michael Kaufmann , Katerina Potika , Antonios Symvonis, Polygon labelling of minimum leader length, Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, p.15-21, February 01, 2006, Tokyo, Japan
	Joonsoo Choi , Chee-Keng Yap, Rectilinear geodesics in 3-space (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.380-389, June 05-07, 1995, Vancouver, British Columbia, Canada
	Tetsushi Nishida , Kokichi Sugihara , Masato Kimura, Stable marker-particle method for the Voronoi diagram in a flow field, Journal of Computational and Applied Mathematics, v.202 n.2, p.377-391, May, 2007
	P. Widmayer , Y. F. Wu , C. K. Wong, Distance problems in computational geometry with fixed orientations, Proceedings of the first annual symposium on Computational geometry, p.186-195, June 05-07, 1985, Baltimore, Maryland, United States
	L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States
	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Proceedings of the first annual symposium on Computational geometry, p.251-262, June 05-07, 1985, Baltimore, Maryland, United States
	Thomas Iwaszko , Mahmoud Melkemi , Lhassane Idoumghar, A theoretical structure for computational geometry: regions of point-free overlapping circles, Proceedings of the 9th WSEAS international conference on Signal processing, computational geometry and artificial vision, p.117-122, August 20-22, 2009, Moscow, Russia