Proximity problems on moving points

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Proximity problems on moving points

Full text

Pdf (1.25 MB)

Source

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

Nice, France

Pages: 344 - 351

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Julien Basch	Computer Science Department, Stanford University, Stanford, CA
Leonidas J. Guibas	Computer Science Department, Stanford University, Stanford, CA
Li Zhang	Computer Science Department, Stanford University, Stanford, CA

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

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/262839.262998 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.

	AMS92	Pankaj K. Agarwal , Jiří Matoušek , Subhash Suri, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Computational Geometry: Theory and Applications, v.1 n.4, p.189-201, April 1992 [doi>10.1016/0925-7721(92)90001-9]
	AS89	C. Aragon and R. Seidel. Randomized search trees. In Proc. 30th Annu. IEEE Sympos. Found. Comput. Sci., pages 540-545, 1989.
	BDIZ	J. Basch, H. Devarajan, P. Indyk, and L. Zhang. Probabilistic analysis for combinatorial functions of moving points. This volume.
	BGH97	Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
	BS80	J.L. Bentley and j. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms, 1:301-358, 1980.
	GGST86	H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
	KGS	Dong Jin Kim , Leonidas J. Guibas , Sung Yong Shin, Fast collision detection among multiple moving spheres, Proceedings of the thirteenth annual symposium on Computational geometry, p.373-375, June 04-06, 1997, Nice, France [doi>10.1145/262839.263007]
	KKT95	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
	KTI95	N. Katoh, T. Tokuyama, and K. Iwano. On minimum and maximum spanning trees of linearly moving points. Discrete Comput. Geom., 13:161-176, 1995.
	Meh84	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	Mul94	K. Mulmuley. Computat{onal Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
	Ove83	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	Smi92	Michiel Smid, Maintaining the minimal distance of a point set in polylogarithmic time, Discrete & Computational Geometry, v.7 n.4, p.415-431, 1992 [doi>10.1007/BF02187852]
	ST83	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	Vai84	P.M. Vaidya. A fast approximation for minimum spanning trees in k-dimensional space. In Proc. #Sth Annu. IEEE Sympos. Found. Comput. Sci., pages 403-407, 1984.
	WL85	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
	Yao82	A.C. Y#o. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11:721-736, 1982.

CITED BY 17

	David Eppstein , Jeff Erickson, Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions, Proceedings of the fourteenth annual symposium on Computational geometry, p.58-67, June 07-10, 1998, Minneapolis, Minnesota, United States
	Frederick Wieland , David Carnes , Gregory Schultz, Using quad trees for parallelizing conflict detection in a sequential simulation, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.117-123, May 15-18, 2001, Lake Arrowhead, California, United States
	Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States
	David Kirkpatrick , Jack Snoeyink , Bettina Speckmann, Kinetic collision detection for simple polygons, Proceedings of the sixteenth annual symposium on Computational geometry, p.322-330, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Artur Czumaj , Christian Sohler, Soft kinetic data structures, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.865-872, January 07-09, 2001, Washington, D.C., United States
	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
	Qun Li , Daniela Rus, Communication in disconnected ad hoc networks using message relay, Journal of Parallel and Distributed Computing, v.63 n.1, p.75-86, January 2003
	Qun Li , Daniela Rus, Sending messages to mobile users in disconnected ad-hoc wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.44-55, August 06-11, 2000, Boston, Massachusetts, United States
	Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points, Journal of Computer and System Sciences, v.66 n.1, p.207-243, 01 February 2003
	Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States
	Christopher L. Barrett , Madhav V. Marathe , D. Charles Engelhart , Anand Sivasubramaniam, Approximating the connectivity between nodes when simulating large-scale mobile ad hoc radio networks, Journal of Systems and Software, v.73 n.1, p.63-74, September 2004
	Peter Corke , Ron Peterson , Daniela Rus, Localization and Navigation Assisted by Networked Cooperating Sensors and Robots, International Journal of Robotics Research, v.24 n.9, p.771-786, September 2005
	David Carnes , Frederick Wieland, Advanced aviation concepts via simulation: techniques to enhance performance of an existing aviation simulation, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	Mohammad Ali Abam , Mark de Berg , Bettina Speckmann, Kinetic KD-trees and longest-side KD-trees, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Arnon Amir , Alon Efrat , Jussi Myllymaki , Lingeshwaran Palaniappan , Kevin Wampler, Buddy tracking - efficient proximity detection among mobile friends, Pervasive and Mobile Computing, v.3 n.5, p.489-511, October, 2007
	Mohammad Ali Abam , Mark de Berg, Kinetic spanners in R^d, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	David Harmon , Etienne Vouga , Breannan Smith , Rasmus Tamstorf , Eitan Grinspun, Asynchronous contact mechanics, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009