A new linear algorithm for intersecting convex polygons. (English) Zbl 0533.52001

Summary: An algorithm is presented that computes the intersection of two convex polygons in linear time. The algorithm is fundamentally different from the only known linear algorithms for this problem, due to Shamos and Hoey. These algorithms depend on a division of the plane into either angular sectors (Shamos) or parallel slabs (Hoey), and are mildly complex. Our algorithm searches for the intersection points of the polygons by advancing a single pointer around each polygon, and is very easy to program.


52A10 Convex sets in \(2\) dimensions (including convex curves)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI