Finding extremal polygons

Reviewer: Joseph J. O'Rourke

This delightful paper examines the problem of finding maximum area or perimeter k-gons inscribed in a given convex polygon of n vertices. The authors first show that the search may be restricted to k-gons whose vertices coincide with k of the n given vertices. Next they find a maximum “rooted” k-gon, one with a fixed root vertex, by finding successively maximum rooted j-gons, j=3,4,. . . k, via dynamic programming. Finally they “float” the root by exploiting an interleaving property of rooted and unrooted maximum k-gons. The same algorithm works for both area and perimeter measures (although leading to different k-gons in general) in time O( kn log n+ n log 2:0- E n). The proof of the interleaving property uses a clever “crossing transform” that always increases area or perimeter, but may temporarily detour through a non-simple polygon. The authors break with the unfortunate tradition of only presenting polished positive results in a section that presents counterexamples to a half-dozen plausible approaches to improving on their algorithm. The discussion of negative results conveys a clear image of the outer edge of the envelope (so to speak) of their algorithm.