Kinetic collision detection for convex fat objects

M.A. Abam, M. Berg, de, S.H. Poon, B. Speckmann

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaten (Scopus)

Samenvatting

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 R3, 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.
Originele taal-2Engels
Pagina's (van-tot)457-473
TijdschriftAlgorithmica
Volume53
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 2009

Vingerafdruk Duik in de onderzoeksthema's van 'Kinetic collision detection for convex fat objects'. Samen vormen ze een unieke vingerafdruk.

Citeer dit