On Local Transformations of Simple Polygons

Michael E. Houle
Department of Computer Science, The University of Newcastle, Callaghan, Newcastle, NSW 2308, Australia.


This paper investigates the following fundamental problems from computational geometry:

Given an integer $k$, a set of points $S$, and a non-convex simple polygon $P$, is it always possible to transform $P$ into a new polygon $P'$ on $S$ by the modification of at most $k$ edges?

Given two polygons $P$ and $P'$ on a common vertex set $S$, is it always possible to transform $P$ into $P'$ via a finite sequence of modifications (called $k$-flips) of this type?

Conference Home Page