Let S be a set of convex polygons in the plane with a total of n vertices, where a polygon consists of the boundary as well as the interior. Efficient algorithms are given for counting and for reporting output-sensitively the I pairs of polygons that intersect. The algorithm for the counting problem takes O(n4/3+ε) time and the algorithm for the reporting problem takes O(n4/3+ε + I) time, where ε > 0 is an arbitrarily small constant. The result is based on an interesting characterization of the intersection of two convex polygons in terms of the intersection of certain trapezoids from their trapezoidal decomposition. The problem is interesting and challenging because the output size, I, can be much smaller than the total number of intersections between the polygons and because the number of polygons and their sizes can depend on n.
Bibliographical noteFunding Information:
search was supported in part by NSF grant CCR-92-00270. Also supportedi n part by a Grant-in-Aid of Researchf rom the Graduate School of the University of Minnesota. ’ Email: email@example.com. Work done while at the Max-Planck-Institut ftir Informatik, Saarbrticken, Germany and at the University of Minnesota, USA. The research was su._ pportedi n part by NSF &ant CCR-9240270. 2 Email: firstname.lastname@example.org. Part of this work was done while the author was at the Department of Computer Science, King’s College London, UK and at the Max-Plan&Institut fiir Informatik, S&bticken, Germany.
- Computational geometry
- Data structures