Computer Science – Computational Geometry
Scientific paper
1998-09-18
Computer Science
Computational Geometry
10 pages, 8 figures; to appear in Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999; see also http://www.uiu
Scientific paper
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during their motion. For two convex polygons in the plane, let $D$ be the maximum diameter of the polygons, and let $s$ be the minimum distance between them during their motion. Our separation certificate changes $O(\log(D/s))$ times when the relative motion of the two polygons is a translation along a straight line or convex curve, $O(\sqrt{D/s})$ for translation along an algebraic trajectory, and $O(D/s)$ for algebraic rigid motion (translation and rotation). Each certificate update is performed in $O(\log(D/s))$ time. Variants of these data structures are also shown that exhibit \emph{hysteresis}---after a separation certificate fails, the new certificate cannot fail again until the objects have moved by some constant fraction of their current separation. We can then bound the number of events by the combinatorial size of a certain cover of the motion path by balls.
Erickson Jeff
Guibas Leonidas J.
Stolfi Jorge
Zhang Lianchang
No associations
LandOfFree
Separation-Sensitive Collision Detection for Convex Objects does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Separation-Sensitive Collision Detection for Convex Objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Separation-Sensitive Collision Detection for Convex Objects will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-230802