“We can use the interval tree [Ede83] for static query, as well as for the
rectangle intersection problem. Each query of interval intersection takes
O(logn + k) time where k is the number of reported intersection and n
is the number of intervals. Therefore, reporting intersection among n
rectangles can be done in O(nlogn + K) where K is the total number of
intersecting rectangles.”
Collision detection between geometricmodels: a survey
Ming C. Lin & Stefan Gottschalk
Advertisement
