Connect-the-dots: A new heuristic

The problem considered in this paper is that of finding a simple polygon through a given set of points in the plane that is “natural” in some perceptual sense. We propose that a particular geometric object called the minimal spanning Voronoi tree captures the essence of the problem. Despite the fact that we can neither prove the existence of this geometric object nor design an exact algorithm for finding it, a search heuristic results in remarkably pleasing solutions to the problem.