# David Eppstein - Publications

##

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

(Jeff's pub list entry)

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

Semi-automatically filtered
from a common source file.