Detecting the Intersection of Convex Objects in the Plane
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.