David Eppstein - Publications

Publications with Günter Rote

• Finding minimum area \(k\)-gons.
  D. Eppstein, M. Overmars, G. Rote, and G. Woeginger.
  Disc. Comp. Geom. 7 (1): 45–58, 1992.

  Uses dynamic programming to choose sets of \(k\) points optimizing various criteria on the quality of their convex hull (in particular area). The time complexity (cubic in \(n\)) was later improved to quadratic in my paper "New algorithms for minimum area \(k\)-gons", which however continues to use the same dynamic program as a subroutine.