Connect-the-dots: A new heuristic. (English) Zbl 0657.68118

The problem considered 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.


68U99 Computing methodologies and applications
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI