Iterated nearest neighbors and finding minimal polytopes

David Eppstein, Jeff Erickson

Research output: Contribution to journalArticlepeer-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 maintain minimal sets efficiently as new points are inserted, to generalize our algorithms 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). We also demonstrate a related technique for finding minimum area k-point sets in the plane, based on testing sets of nearest vertical neighbors to each line segment determined by a pair of points. A generalization of this technique also allows us to find minimum volume and boundary measure sets in arbitrary dimensions.

Original languageEnglish (US)
Pages (from-to)321-350
Number of pages30
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1994
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


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

Cite this