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.

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

Semi-automatically filtered from a common source file.