Detecting the Intersection of Convex Objects in the Plane

Abstract:

Numerous applications require intersection detection. Many algorithms have been developed for telling whether two polygons intersect. We have extended one such algorithm to allow us to determine in C log n operations whether two convex planar regions intersects. Our algorithm is significant because it can be presented as a combination of two ideas. First, there is a revision of previous algorithms for detecting whether two convex polygons intersect. Second, there is a general method for transforming algorithms which work for polygons to make them work for piecewise curved boundaries. The constant C depends strictly upon the complexity of the piecewise curves. The algorithms presented here have
been implemented and details of their implementation are included.