Matt Duckham
Department of Geomatics
University of Melbourne
This talk presents a simple, flexible, and efficient O(n log n) algorithm for constructing a possibly non-convex, simple polygon that characterizes the shape of a set of input points in the plane. The algorithm is based on the Delaunay triangulation of the points. The shape produced by the algorithm, termed a characteristic shape, is controlled by a single normalized parameter, which can be used to generate a finite, family of related characteristic shapes.
Characteristic shapes possess a number of desirable properties, and the talk includes an empirical investigation of some the shapes produced by the algorithm. The experimental evidence indicates that with appropriate parameterization the algorithm is able to accurately characterize the shape of a wide range of different point distributions and densities.