Solving query-retrieval problems by compacting Voronoi diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving query-retrieval problems by compacting Voronoi diagrams

Full text

Pdf (1.03 MB)

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: 331 - 340

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

A. Aggarwal	IBM Research Division T.J. Watson Research Center, Yorktown Heights, New York and Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts
M. Hansen	Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts
T. Leighton	Mathematics Department and Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, Massachusetts

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 37, Citation Count: 10

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.100260 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	P.F. Ash, E.D. Bolker, "Generalized Dirichlet tessetations," Geometriae Dedicata 20 (1986), pp. 209 - 243.
	3	F. Aurenhammer, "Voronoi Diagrams - A Survey," Technical Report, Institutes for Information Processing, Graz Technical University, Austria, 1988.
	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	F. Aurenhammer, H. Edelsbrunner, "An optimal algorithm for constructing the weighted Voronoi diagram in the plane," Pattern Recognition 17 (1984), pp. 251 - 257.
	6	F. Aurenhammer, H. Imai, "Geometric relations among Voronoi diagrams," Geometriae Dedicata 27 (1988), pp. 65 - 75."
	7	J.L. Bentley, H.A. Maurer "A note on Euclidean near neighbor searching in the plane," Infi Process. Left. 8 (1979) pp. 133- 136.
	8	M. Blum, R.W. Floyd, V. Pratt, R. Rivest, R.E. Tarjan, "Time bounds for selection", Journal of Computer and System Sciences, vol. 7, no. 4, Aug. 1973, pp. 448 - 461.
	9	Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
	10	Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
	11	B Chazelle , R Cole , P Preparata , C Yap, New upper bounds for neighbor searching, Information and Control, v.68 n.1-3, p.105-124, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80030-4]
	12	B. Chazelle , H. Edelsbrunner, Optimal solutions for a class of point retrieval problems, Journal of Symbolic Computation, v.1 n.1, p.47-56, March 1985 [doi>10.1016/S0747-7171(85)80028-6]
	13	B. Chazelle , H. Edelsbrunner, An improved algorithm for constructing kth-order voronoi diagrams, IEEE Transactions on Computers, v.36 n.11, p.1349-1354, Nov. 1987 [doi>10.1109/TC.1987.5009474]
	14	B.M. Chazelle, H. Edelsbrunner, "Linear space data structures for two types of range search," Discrete and Computational Geometry Vol. 2 (1987) pp. 113 - 126..
	15	Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
	16	B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
	17	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 [doi>10.1145/323233.323264]
	18	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]
	19	R. Cole, C.K. Yap, "Geometric retrieval problems," Proc. 24th Annual IEEE Syrup. on Foundations of Computer Science, Nov. 1983, pp. 112 - 121.
	20	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	21	H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
	22	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	23	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	24	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	25	D.S. Johnson, personal communication 1989.
	26	D.G. Kirkpatrick "Optimal search in planar subdivisions.", SIAM J. Comput. 12(1983), pp. 28 - 35.
	27	D.T. Lee, "On k-nearest neighbor Voronoi diagrams in the plane," IEEE Trans. on Computers, Vol. C-31, 1982, pp. 478 - 487.
	28	R.J. Lipton and R.E. Tarjan, "A separator theorem for planar graphs," SIAM Journal on Applied Mathematics, Vol. 36, No. 2 (April 1979), pp. 177 - 189.
	29	D. Marcotte and S. Suri, "Fast matching algorithms for points on a polygon," Proc. of the 30th Annual IEEE Conf. on Foundations of Computer Science (1989) pp. 60 - 65.
	30	H. Rosenberger, "Order-k Voronoi diagrams for sites with additive weights in the plane. Rep. UIUCDCS-R- 88-1431, Dept. Comput. Sci, Univ. Illinois, Urbana, IL, 1988.
	31	J. Spencer Ten Lectures on the Probabilistic Method, SIAM, 1987.
	32	Pravin Vaidya, Geometry helps in matching, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.422-425, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62253]
	33	F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

CITED BY 10

	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
	Pankaj K. Agarwal , Marc van Kreveld , Mark Overmars, Intersection queries for curved objects (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.41-50, June 10-12, 1991, North Conway, New Hampshire, United States
	Jeff Erickson, Space-time tradeoffs for emptiness queries (extended abstract), Proceedings of the thirteenth annual symposium on Computational geometry, p.304-313, June 04-06, 1997, Nice, France
	Prosenjit Gupta , Ravi Janardan , Michiel Smid, Efficient algorithms for generalized intersection searching on non-iso-oriented objects, Proceedings of the tenth annual symposium on Computational geometry, p.369-378, June 06-08, 1994, Stony Brook, New York, United States
	Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States
	Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994
	Liam Roditty , Michael Segal, On bounded leg shortest paths problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.775-784, January 07-09, 2007, New Orleans, Louisiana
	Yokesh Kumar , Ravi Janardan , Prosenjit Gupta, Efficient algorithms for reverse proximity query problems, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California
	Peyman Afshani , Timothy M. Chan, Optimal halfspace range reporting in three dimensions, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.180-186, January 04-06, 2009, New York, New York
	Chen Avin , Yuval Emek , Erez Kantor , Zvi Lotker , David Peleg , Liam Roditty, SINR diagrams: towards algorithmically usable SINR models of wireless networks, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada