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
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


checked on May 28, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.