Convexifying polygons without losing visibilities
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.
|Conference||23rd Annual Canadian Conference on Computational Geometry, CCCG 2011|
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.