Paper by Erik D. Demaine

Reference:

Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, 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 Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.

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, 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 visibility-increasing edge where, as a point travels from one endpoint of the edge to the other, the visibility region of the point increases.

Length:

The paper is 6 pages.

Availability:

The paper is available in PDF (2480k).

See information on file formats.

[Google Scholar search]