TY - JOUR
T1 - Kinetic collision detection between two simple polygons
AU - Basch, Julien
AU - Erickson, Jeff
AU - Guibas, Leonidas J.
AU - Hershberger, John
AU - Zhang, Li
N1 - Funding Information:
* Corresponding author. E-mail addresses: julien@basch.org (J. Basch), jeffe@cs.uiuc.edu (J. Erickson), guibas@cs.stanford.edu (L.J. Guibas), john_hershberger@mentor.com (J. Hershberger), l.zhang@hp.com (L. Zhang). URLs: http://www.uiuc.edu/ph/www/jeffe/ (J. Erickson), http://graphics.stanford.edu/~guibas/ (L.J. Guibas), http://graphics.stanford.edu/~lizhang/ (L. Zhang). 1 Portions of this research were done at the International Computer Science Institute, Berkeley, CA. Research supported by National Science Foundation grant DMS-9627683 and by US Army Research Office MURI grant DAAH04-96-1-0013. 2 Research partially supported by National Science Foundation grant CCR-9623851 and by US Army Research Office MURI grant DAAH04-96-1-0007.
PY - 2004/3
Y1 - 2004/3
N2 - We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. We show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting.
AB - We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. We show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting.
KW - Collision detection
KW - Geodesic triangulation
KW - Kinetic data structures
UR - http://www.scopus.com/inward/record.url?scp=84867954569&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867954569&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2003.11.001
DO - 10.1016/j.comgeo.2003.11.001
M3 - Article
AN - SCOPUS:84867954569
SN - 0925-7721
VL - 27
SP - 211
EP - 235
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 3
ER -