Finding minimum area \(k\)-gons.(English)Zbl 0746.68038
Let \(P\) be a set of \(n\) points in the plane. Assume \(k\geq 3\). The problem considered is to find a convex polygon \(C\) with vertices from \(P\) of minimum area that satisfies one of the following conditions:
(1) \(C\) is a convex \(k\)-gon,
(2) \(C\) is an empty convex \(k\)-gon (i.e., \(P\cap\text{int} C=\emptyset\)),
(3) \(C\) is the convex hull fo exactly \(k\) points of \(P\).
It is shown here that each of these problems can be solved by an algorithm of time complexity \(O(kn^ 3)\) and space complexity \(O(kn^ 2)\) (for \(k=4\) this is only \(O(n)\)). The algorithms are based on dynamic programming. The method extends to several similar extremum problems.
(1) \(C\) is a convex \(k\)-gon,
(2) \(C\) is an empty convex \(k\)-gon (i.e., \(P\cap\text{int} C=\emptyset\)),
(3) \(C\) is the convex hull fo exactly \(k\) points of \(P\).
It is shown here that each of these problems can be solved by an algorithm of time complexity \(O(kn^ 3)\) and space complexity \(O(kn^ 2)\) (for \(k=4\) this is only \(O(n)\)). The algorithms are based on dynamic programming. The method extends to several similar extremum problems.
Reviewer: I.Bárány (Budapest)
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 52A10 | Convex sets in \(2\) dimensions (including convex curves) |
| 90C39 | Dynamic programming |
Keywords:
convex \(k\)-gonCite
Online Encyclopedia of Integer Sequences:
a(n) is twice the least possible area enclosed by a convex lattice n-gon.References:
| [1] | A. Aggarwal and J. Wein,Computational Geometry, Lecture Notes for 18.409, MIT Laboratory for Computer Science, 1988. |
| [2] | A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm,Algorithmica2 (1987), 195-208. ·Zbl 0642.68078 ·doi:10.1007/BF01840359 |
| [3] | 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. ·Zbl 0715.68082 |
| [4] | 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. |
| [5] | J. E. Boyce, D. P. Dobkin, R. L. Drysdale, and L. J. Guibas, Finding extremal polygons,SIAM J. Comput.14 (1985), 134-147. ·Zbl 0557.68034 ·doi:10.1137/0214011 |
| [6] | Dobkin, D. P.; Drysdale, R. L.; Guibas, L. J., Finding smallest polygons, 181-214 (1983), Greenwich, CT |
| [7] | 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. ·Zbl 0697.68034 |
| [8] | H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical. Computer Science, Springer-Verlag, Berlin, 1987. ·Zbl 0634.52001 ·doi:10.1007/978-3-642-61568-9 |
| [9] | H. Edelsbrunner and L. J. Guibas, Topologically sweeping in an arrangement,Proc. 18th ACM Symp. on Theory of Computing, 1986, pp. 389-403. ·Zbl 0676.68013 |
| [10] | H. Edelsbrunner, J. O’Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput.15 (1986), 341-363. ·Zbl 0603.68104 ·doi:10.1137/0215024 |
| [11] | D. Eppstein, New algorithms for minimum areak-gons,Proc. 3rd ACM/SIAM Symp. on Discrete Algorithms, 1992, to appear. ·Zbl 0829.68117 |
| [12] | J. D. Horton, Sets with no empty convex 7-gons,Canad. Math. Bull.26 (1983), 482-484. ·Zbl 0521.52010 ·doi:10.4153/CMB-1983-077-8 |
| [13] | J. I. Munro and R. J. Ramirez, Reducing space requirements for shortest path problems,Oper. Res.30 (1982), 1009-1013. ·Zbl 0492.90080 ·doi:10.1287/opre.30.5.1009 |
| [14] | M. H. Overmars, B. Scholten, and I. Vincent, Sets without empty convex 6-gons,Bull. EATCS37 (1989), 160-160. ·Zbl 1023.68686 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
