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(n2) moves, where each move translates a single vertex. The proof involves a new visibility property of polygons, namely that every simple polygon has a visibility- increasing edge where, as a point travels from one endpoint of the edge to the other, the visibility region of the point increases.

Additional Metadata
Conference 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Citation
Aichholzer, O. (Oswin), Aloupis, G, Demaine, E.D. (Erik D.), Demaine, M.L. (Martin L.), Dujmović, V, Hurtado, F. (Ferran), … Winslow, A. (Andrew). (2011). Convexifying polygons without losing visibilities. Presented at the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011.