Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Ferran Hurtado, Anna Lubiw, Günter Rote, André Schulz, Diane L. Souvaine, and Andrew Winslow:

Convexifying polygons without losing visibilities

In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Vancouver, August 10–12, 2011, pp. 229–234.


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.

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.

  pdf file (gzipped)
other papers about this subject
Last update: August 22, 2011.