David Eppstein - Publications

Publications with Gerhard Woeginger

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