The Pairwise Intersection Problem for Monotone Polygons

Geometric intersection problems arise in a number of areas of computer science including graphics and VLSI design rule checking. Previous work has concentrated on solving the pairwise intersection problem for line segments and iso-oriented rectangles. This thesis extends that work by presenting efficient algorithms to solve the pairwise intersection problem for monotone polygons. For general segments, the problem has been solved in O(N+I)*logN) time using a sweeping line technique, where N is the number of segments and I is the number of intersections reported. We combine this technique with approaches taken to solve the iso-oriented rectangle problem to yield an algorithm which solves the pairwise intersection problem for monotone polygons in the same asymptotic time. In addition, there are certain classes of line segments for which the pairwise intersection problem may be solved in O(N*logN + I) time, the best possible. We generalize each such class of line segments to a class of polygons and present algorithms to solve the associated polygon problem. Finally, we discuss the impacts which possible improvements to the line segment problem would have on our results