David Eppstein - Publications
- Finding minimum area k-gons.
G. Rote, and
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
"New algorithms for minimum area k-gons",
which however continues to use the same dynamic program as a subroutine.
- Application Challenges to Computational Geometry.
Computational Geometry Impact Task Force
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.
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
from a common source file.