Efficient algorithms for counting and reporting pairwise intersections between convex polygons

Let S be a set of convex polygons in the plans with a total of ii vertices, where a polygon consists of the boundary as well as the interior. Efficien t algorithms are given for counting and for reporting output-sensitively th e I pairs of polygons that intersect. The algorithm for the counting proble m tales O(n(4/3+epsilon)) time and the algorithm for the reporting problem takes O(n(4/3+epsilon) + I) time, where epsilon > 0 is an arbitrarily small constant. The result is based on an interesting characterization of the in tersection of two convex polygons in terms of the intersection of certain t rapezoids from their trapezoidal decomposition. The problem is interesting and challenging because the output size, I, can be much smaller than the to tal number of intersections between the polygons and because the number of polygons and their sizes can depend on n. (C) 1999 Elsevier Science B.V. Al l rights reserved.