Iterated nearest neighbors and finding minimal polytypes

David Eppstein, Jeff Erickson

Research output: Contribution to conferencePaperpeer-review


We introduce a new method for finding several types of optimal k-point sets, minimizing perimeter, diameter, circumradius, and related measures, by testing sets of the O(k) nearest neighbors to each point. We argue that this is better in a number of ways than previous algorithms, which were based on high order Voronoi diagrams. Our technique allows us for the first time to efficiently dynamize our algorithms, to generalize them to higher dimensions, to find minimal convex k-vertex polygons and polytopes, and to improve many previous results. We achieve many of our results via a new algorithm for finding rectilinear nearest neighbors in the plane in time O(n log n+kn). Finally, we demonstrate a related method for finding k-point sets with minimum boundary measure or volume in arbitrary dimensions, generalizing our results for minimizing perimeter and an earlier result of the first author for minimizing area.

Original languageEnglish (US)
Number of pages10
StatePublished - 1993
Externally publishedYes
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993


OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Iterated nearest neighbors and finding minimal polytypes'. Together they form a unique fingerprint.

Cite this