Finding large sticks and potatoes in polygons
Olaf A. Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, Arik Sityon · 2006
We study a class of optimization problems in polygons that seek to compute the "largest" subset of a prescribed type, e.g., a longest line segment ("stick") or a maximum-area triangle or convex body ("potato"). Exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., O(n^7) for the largest convex polygon in a simple n-gon). We devise efficient approximation algorithms for these problems. In particular, we give near-linear time algorithms for a (1-ε)-approximation of the biggest stick, an O(1)-approximation of the maximum-area convex body, and a O(1-ε)-approximation of the maximum-area fat triangle or rectangle. In addition, we give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of a closed smooth curve). Our algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve).