Geometric Intersection Problems

We develop optimal algorithms for forming the intersection of geometric objects in the plane and apply them to such diverse problems as linear programming, hidden-line elimination, and wire layout. Given N line segments in the plane, finding all intersecting pairs requires O(N2) time. We give an O(N log N) algorithm to determine whether any two intersect and use i t to detect whether two simple plane polygons intersect. We employ an O(N log N) algorithm for finding the common intersection of N half-planes to show that the Simplex method is not optimal. The emphasis throughout i s On obtaining upper and lower bounds and relating these results to other problems in computational geometry.