Algorithmic enumeration of surrounding polygons

Abstract We are given a set S of points in the Euclidean plane. We assume that S is in general position. A simple polygon P is a surrounding polygon of S if each vertex of P is a point in S and every point in S is either inside P or a vertex of P . In this paper, we present an enumeration algorithm of the surrounding polygons for a given point set. Our algorithm is based on reverse search by Avis and Fukuda and enumerates all the surrounding polygons in polynomial delay and quadratic space. It also provides the first space efficient method to generate all simple polygonizations on a given point set in exponential time. By relating these two problems we provide an upper bound on the number of surrounding polygons.