Abstract
Given a setP ofn points in the plane and a numberk, we want to find a polygon
with vertices inP of minimum area that satisfies one of the following properties: (1)
is a convexk-gon, (2)
is an empty convexk-gon, or (3)
is the convex hull of exactlyk points ofP. We give algorithms for solving each of these three problems in timeO(kn 3). The space complexity isO(n) fork=4 andO(kn 2) fork≥5. The algorithms are based on a dynamic programming approach. We generalize this approach to polygons with minimum perimeter, polygons with maximum perimeter or area, polygons containing the maximum or minimum number of points, polygons with minimum weight (for some weights added to vertices), etc., in similar time bounds.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Aggarwal and J. Wein,Computational Geometry, Lecture Notes for 18.409, MIT Laboratory for Computer Science, 1988.
A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm,Algorithmica 2 (1987), 195–208.
A. Aggarwal, H. Imai, N. Katoh, and S. Suri, Findingk points with minimum diameter and related problems,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 283–291.
D. Avis and D. Rappaport, Computing the largest empty convex subset of a set of points,Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 161–167.
J. E. Boyce, D. P. Dobkin, R. L. Drysdale, and L. J. Guibas, Finding extremal polygons,SIAM J. Comput. 14 (1985), 134–147.
D. P. Dobkin, R. L. Drysdale, and L. J. Guibas, Finding smallest polygons, In:Advances in Computing Research, Vol. 1, JAI Press, Greenwich, CT, 1983, pp. 181–214.
D. P. Dobkin, H. Edelsbrunner, and M. H. Overmars, Searching for empty convex polygons,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 224–228.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical. Computer Science, Springer-Verlag, Berlin, 1987.
H. Edelsbrunner and L. J. Guibas, Topologically sweeping in an arrangement,Proc. 18th ACM Symp. on Theory of Computing, 1986, pp. 389–403.
H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341–363.
D. Eppstein, New algorithms for minimum areak-gons,Proc. 3rd ACM/SIAM Symp. on Discrete Algorithms, 1992, to appear.
J. D. Horton, Sets with no empty convex 7-gons,Canad. Math. Bull. 26 (1983), 482–484.
J. I. Munro and R. J. Ramirez, Reducing space requirements for shortest path problems,Oper. Res. 30 (1982), 1009–1013.
M. H. Overmars, B. Scholten, and I. Vincent, Sets without empty convex 6-gons,Bull. EATCS 37 (1989), 160–160.
Author information
Authors and Affiliations
Additional information
This paper includes work done while David Eppstein was at Columbia University, Department of Computer Science, and while Günter Rote and Gerhard Woeginger were at the Freie Universität Berlin, Fachbereich Mathematik, Institut für Informatik. Research was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).
Rights and permissions
About this article
Cite this article
Eppstein, D., Overmars, M., Rote, G. et al. Finding minimum areak-gons. Discrete Comput Geom 7, 45–58 (1992). https://doi.org/10.1007/BF02187823
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187823