Efficient generation of simple polygons for characterizing the shape of a set of points in the plane

Abstract

This paper presents a simple, flexible, and efficient algorithm for constructing a possibly non-convex, simple polygon that characterizes the shape of a set of input points in the plane, termed a characteristic shape. The algorithm is based on the Delaunay triangulation of the points. The shape produced by the algorithm is controlled by a single normalized parameter, which can be used to generate a finite, totally ordered family of related characteristic shapes, varying between the convex hull at one extreme and a uniquely defined shape with minimum area. An optimal O (n log n) algorithm for computing the shapes is presented. Characteristic shapes possess a number of desirable properties, an..