## Abstract

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are: (i) If the objects are 3-dimensional balls that roll on a plane, then we can detect collisions with a KDS of size O(nlog∈n) that can handle events in O(log∈ ^{2} n) time. This structure processes O(n ^{2}) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. (ii) If the objects are convex fat 3-dimensional objects of constant complexity that are free-flying in ℝ ^{3}, then we can detect collisions with a KDS of O(nlog∈ ^{6} n) size that can handle events in O(log∈ ^{7} n) time. This structure processes O(n ^{2}) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects have similar sizes then the size of the KDS becomes O(n) and events can be handled in O(log∈n) time.

Original language | English |
---|---|

Pages (from-to) | 457-473 |

Number of pages | 17 |

Journal | Algorithmica |

Volume | 53 |

Issue number | 4 |

DOIs | |

Publication status | Published - Apr 2009 |

Externally published | Yes |

## Keywords

- Collision detection
- Fat objects
- Kinetic data structures

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics