David Eppstein – Publications

Publications with Mark Overmars

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

• Application Challenges to Computational Geometry.
  The Computational Geometry Impact Task Force Report.
  Tech. Rep. TR-521-96, Princeton University, April 1996.
  Advances in Discrete and Computational Geometry – Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 407–423.