- 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.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.