On Local Transformations of Simple Polygons

Michael E. Houle
Department of Computer Science, The University of Newcastle, Callaghan, Newcastle, NSW 2308, Australia.
mike@cs.newcastle.edu.au

Abstract

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