**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.(BibTeX – Citations – Jeff's pub list entry – CiteSeer)

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.