Convexifying Polygons Without Losing Visibilities
Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovi, Ferrán Hurtado, Anna Lubiw, Gunter Rote Andr, Diane L. Souvaine · 2011
We show that any simple n-vertex polygon can be made convex, without losing internal visibilities between vertices, using n moves. Each move translates a vertex of the current polygon along an edge to a neighbouring vertex. In general, a vertex of the current polygon represents a set of vertices of the original polygon that have become co-incident. We also show how to modify the method so that vertices become very close but not co-incident, in which case we need O(n²) moves, where each move translates a single vertex. The proof involves a new visibility property of polygons, namely that every simple polygon has a visibilityincreasing edge where, as a point travels from one endpoint of the edge to the other, the visibility region of the point increases.