Authors: | Žunić, Joviša | Affiliations: | Mathematical Institute of the Serbian Academy of Sciences and Arts | Title: | Extremal problems on convex lattice polygons in sense of lp-metrics | Journal: | Discrete Mathematics | Volume: | 259 | Issue: | 1-3 | First page: | 237 | Last page: | 250 | Issue Date: | 28-Dec-2002 | Rank: | M22 | ISSN: | 0012-365X | DOI: | 10.1016/S0012-365X(02)00384-9 | Abstract: | This paper expresses the minimal possible lp-perimeter of a convex lattice polygon with respect to its number of vertices, where p is an arbitrary integer or p = ∞. It will be shown that such a number, denoted by sp(n), has n3/2 as the order of magnitude for any choice of p. Moreover, sp(n) = 2π/√54Apn3/2 + (n), where n is the number of vertices, Ap equals the area of planar shape \x\p + \y\p < 1, and p is an integer greater than 1. A consequence of the previous result is the solution of the inverse problem. It is shown that Np(s)=33√Ap/3√2π2s2/3 + (s1/3) equals the maximal possible number of vertices of a convex lattice polygon whose lp-perimeter is equal to s. The latter result in a particular case p=2 follows from a well known Jarnik's result. The method used cannot be applied directly to the cases p = 1 and ∞. A slight modification is necessary. In the obtained results the leading terms are in accordance with the above formulas (A1 =2 and A∞ =4), while the rest terms in the expressions for sp(n) and Np(s) are replaced with (n log n) and (s1/3 logs), respectively. |
Keywords: | Combinatorial optimization | Convex lattice polygon | Publisher: | Elsevier |
Show full item record
SCOPUSTM
Citations
1
checked on Oct 13, 2024
Page view(s)
14
checked on Oct 13, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.