Kinetic collision detection for simple polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Kinetic collision detection for simple polygons

Full text

Pdf (917 KB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 322 - 330

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

David Kirkpatrick	Department of Computer Science, University of British Columbia
Jack Snoeyink	Department of Computer Science, UNC Chapel Hill
Bettina Speckmann	Department of Computer Science, University of British Columbia

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

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/336154.336219 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	Pankaj K. Agarwal , Julien Basch , Mark de Berg , Leonidas J. Guibas , John Hershberger, Lower bounds for kinetic planar subdivisions, Proceedings of the fifteenth annual symposium on Computational geometry, p.247-254, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304961]
	2	P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang. Deformable free space tilings for kinetic collision detection, in To appear Proc. 5th Workshop Algorithmic Found. Robotics, 2000.
	3	Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , Li Zhang, Kinetic collision detection between two simple polygons, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.102-111, January 17-19, 1999, Baltimore, Maryland, United States
	4	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
	5	Julien Basch , Leonidas J. Guibas , Craig D. Silverstein , Li Zhang, A practical evaluation of kinetic data structures, Proceedings of the thirteenth annual symposium on Computational geometry, p.388-390, June 04-06, 1997, Nice, France [doi>10.1145/262839.263016]
	6	Julien Basch , Leonidas J. Guibas , Li Zhang, Proximity problems on moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.344-351, June 04-06, 1997, Nice, France [doi>10.1145/262839.262998]
	7	B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12:54-68, 1994.
	8	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	9	Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
	10	L. Guibas, J. Snoeyink, and L. Zhang. Compact voronoi diagrams for moving convex polygons.
	11	Leonidas J. Guibas, Kinetic data structures: a state of the art report, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.191-209, August 1998, Houston, Texas, United States
	12	L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink. Approximating polygons and subdivisions with minimum link paths. Internat. J. Comput. Geom. Appl., 3(4):383-415, Dec. 1993.
	13	S. Kapoor , S. N. Maheshwari, Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles, Proceedings of the fourth annual symposium on Computational geometry, p.172-182, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73411]
	14	S. Kapoor, S. N. Maheshwari, and J. S. B. Mitchell. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete Comput. Geom., 18:377-383, 1997.
	15	Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
	16	M. McAllister, D. Kirkpatrick, and J. Snoeyink. A compact piecewise-linear voronoi diagram for convex sites in the plane. Discrete Comp. Geom., 15:73-105, 1996.
	17	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
	18	C. O'Dfinlaing and C. K. Yap. A "retraction" method for planning the motion of a disk. J. Algorithms, 6:104-111, 1985.
	19	F. P. Preparata. Planar point location revisited. Internat. J. Found. Comput. Sci. , 1 (1):71-86, 1990.
	20	T. Roos. Dynamic Voronoi diagrams. Ph.D. thesis, Bayerische Julius-Maximilians-Univ., Wfirzburg, Germany, Sept. 1991.
	21	M. Sharir and S. Sifrony. Coordinated motion planning for two independent robots. Ann. Math. Artif. Intell., 3:107-130, 1991.
	22	Subhash Suri, Minimum link paths in polygons and related problems, 1987

CITED BY 12

	Joseph O'Rourke, Computational geometry column 43, ACM SIGACT News, v.33 n.1, March 2002
	Pierre Angelier , Michel Pocchiola, A sum of squares theorem for visibility, Proceedings of the seventeenth annual symposium on Computational geometry, p.302-311, June 2001, Medford, Massachusetts, United States
	Lutz Kettner , David Kirkpatrick , Andrea Mantler , Jack Snoeyink , Bettina Speckmann , Fumihiko Takeuchi, Tight degree bounds for pseudo-triangulations of points, Computational Geometry: Theory and Applications, v.25 n.1-2, p.3-12, May 2003
	Pankaj Agarwal , Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Computational Geometry: Theory and Applications, v.28 n.2-3, p.137-163, June 2004
	Sergey Bereg, Transforming pseudo-triangulations, Information Processing Letters, v.90 n.3, p.141-145, 16 May 2004
	Pankaj K. Agarwal , Leonidas J. Guibas , Herbert Edelsbrunner , Jeff Erickson , Michael Isard , Sariel Har-Peled , John Hershberger , Christian Jensen , Lydia Kavraki , Patrice Koehl , Ming Lin , Dinesh Manocha , Dimitris Metaxas , Brian Mirtich , David Mount , S. Muthukrishnan , Dinesh Pai , Elisha Sacks , Jack Snoeyink , Subhash Suri , Ouri Wolefson, Algorithmic issues in modeling motion, ACM Computing Surveys (CSUR), v.34 n.4, p.550-572, December 2002
	Pankaj K. Agarwal , Leonidas J. Guibas , Herbert Edelsbrunner , Jeff Erickson , Michael Isard , Sariel Har-Peled , John Hershberger , Christian Jensen , Lydia Kavraki , Patrice Koehl , Ming Lin , Dinesh Manocha , Dimitris Metaxas , Brian Mirtich , David Mount , S. Muthukrishnan , Dinesh Pai , Elisha Sacks , Jack Snoeyink , Subhash Suri , Ouri Wolefson, Algorithmic issues in modeling motion, ACM Computing Surveys (CSUR), v.34 n.4, p.550-572, December 2002
	Sergey Bereg, Enumerating pseudo-triangulations in the plane, Computational Geometry: Theory and Applications, v.30 n.3, p.207-222, March 2005
	Stephane Redon , Young J. Kim , Ming C. Lin , Dinesh Manocha, Fast continuous collision detection for articulated models, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Young J. Kim , Stephane Redon , Ming C. Lin , Dinesh Manocha , Jim Templeman, Interactive Continuous Collision Detection Using Swept Volume for Avatars, Presence: Teleoperators and Virtual Environments, v.16 n.2, p.206-223, April 2007
	Joachim Gudmundsson , Christos Levcopoulos, Minimum weight pseudo-triangulations, Computational Geometry: Theory and Applications, v.38 n.3, p.139-153, October, 2007
	Xinyu Zhang , Stephane Redon , Minkyoung Lee , Young J. Kim, Continuous collision detection for articulated models using Taylor models and temporal culling, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007