Intersection detection and separators for simple polygons

A simple algorithm is presented for detecting whether two preprocessed simple polygons intersect one another. Given a simple polygon, A, in O(n log n) time and O(n) space we preprocess A constructing an enveloping triangulation called a scaffold. To determine whether two preprocessed polygons A and B overlap another, we start with these two envelopes and successively strip away overlapping triangles of the scaffolds until we either detect an intersection between the objects or until we have succeeded in separating them spatially. The running time of the intersection query depends on the complexity of the minimum link polygonal curve separating the two objects. Given two preprocessed simple polygons A and B, placed at arbitrary locations in the plane we can determine whether these polygons intersect one another in O(m log2n is the total number of vertices and m is the complexity of a minimum link polygonal curve separating A from B. We generalize this to the problem of computing arbitrary Boolean functions of two preprocessed polygons.