Iterated nearest neighbors and finding minimal polytopes.
D. Eppstein and
J. Erickson.
Tech. Rep. 92-71, ICS, UCI, 1992.
4th ACM-SIAM Symp. Discrete Algorithms, Austin, 1993, pp. 64–73.
Disc. Comp. Geom. 11: 321–350, 1994,
doi:10.1007/BF02574012.
Showed that for various optimization criteria, the optimal polygon containing \(k\) of \(n\) points must be near one of the points, hence one can transform time bounds involving several factors of \(n\) to bounds linear in \(n\) but polynomial in \(k\). Used as a subroutine are data structures for finding several nearest neighbors in rectilinear metric spaces, and algorithms for finding the deepest point in an arrangement of cubes or spheres.