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.
Abstract
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.
Last update: August 22, 2011.