On the maximal number of edges of convex digital polygons included into an \(m \times m\)-grid. (English) Zbl 0815.68112
Summary: Let \(e(m)\) denote the maximal number of edges of a convex digital polygon included into an \(m\times m\) square area of lattice points and let \(s(n)\) denote the minimal (side) size of a square in which a convex digital polygon with \(n\) edges can be included. We prove that
\[
\begin{aligned} e(m) & ={12\over (4\pi^ 2)^{1/3}} m^{2/3}+ O(m^{1/3}\log m),\\ s(n) & = {2\pi\over 12^{3/2}} n^{3/2}+ O(n\log n).\end{aligned}
\]
{}.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52A37 | Other problems of combinatorial convexity |
| 90C27 | Combinatorial optimization |
References:
| [1] | Acketa, D. M.; Ẑunić, J. D., On the number of linear partitions of the (m, n)-grid, Inform. Process. Lett., 38, 163-168 (1991) · Zbl 0737.68080 |
| [2] | Balog, A.; Barany, I., On the convex hull of the integer points in a disc, (Proceedings of Seventh Annual ACM Symposium on Computational Geometry (1991)), 162-165 |
| [3] | Barany, I.; Howe, R.; Lovasz, L., On integer points in polyhedra, a lower bound, Combinatorica, 12, 2, 135-141 (1992) · Zbl 0754.52005 |
| [4] | Berenstein, C. A.; Lavine, D., On the number of digital line segments, IEEE Trans. Pattern Anal. Mach. Intell., 10, No. 6, 880-887 (1988) · Zbl 0674.68054 |
| [5] | Cook, W.; Hartman, M.; Kannon, R.; McDiarmid, C., On integer points in polyhedra, Combinatorica, 12, 1, 27-37 (1992) · Zbl 0757.52013 |
| [6] | Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1968), Oxford Univ. Press: Oxford Univ. Press New York · Zbl 0020.29201 |
| [7] | Rabinowitz, A. S., On the number of lattice points inside a convex lattice \(n\)-gon, (Congr. Numer., 73 (1990)), 99-124 · Zbl 0694.52007 |
| [8] | Simpson, R. J., Convex lattice polygons of minimum area, Bull. Austral. Math. Soc., 42, 353-367 (1990) · Zbl 0707.52006 |
| [9] | Voss, K.; Klette, R., On the maximal number of edges of a convex digital polygon included into a square, Pocitace a umela inteligencia, Vol. 1, No. 6, 549-558 (1982) · Zbl 0502.68016 |
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.
