On the maximal number of edges of convex digital polygons included into an \(m \times m\)-grid

DOI10.1016/0097-3165(95)90058-6zbMath0815.68112OpenAlexW2025410619WikidataQ57926999 ScholiaQ57926999MaRDI QIDQ1345882

Dragan M. Acketa, Joviša D. Žunić

Publication date: 19 March 1995

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(95)90058-6

zbMATH Keywords

optimization problemsconvex digital polygon

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Other problems of combinatorial convexity (52A37)

Related Items

Embedding stacked polytopes on a polynomial-size grid ⋮ A characterization of 2-threshold functions via pairs of prime segments ⋮ Unnamed Item ⋮ An exact construction of digital convex polygons with minimal diameter ⋮ Distance between vertices of lattice polytopes ⋮ Realizing Planar Graphs as Convex Polytopes ⋮ Asymptotics of convex lattice polygonal lines with a constrained number of vertices ⋮ Broadcast Transmission to Prioritizing Receivers ⋮ Shape elongation from optimal encasing rectangles ⋮ Algorithms for pixelwise shape deformations preserving digital convexity ⋮ Small grid embeddings of 3-polytopes ⋮ The diameter of lattice zonotopes ⋮ Upper bounds on the maximal number of facets of 0/1-polytopes ⋮ The Perimeter of optimal convex lattice polygons in the sense of different metrics ⋮ Grid drawings of graphs with constant edge-vertex resolution ⋮ Improved bounds on the diameter of lattice polytopes ⋮ On the polyhedral complexity of the integer points in a hyperball ⋮ On maximal convex lattice polygons inscribed in a plane convex set ⋮ Primitive zonotopes ⋮ Measure of circularity for parts of digital boundaries and its fast computation ⋮ Drawing graphs as spanners ⋮ Computational determination of the largest lattice polytope diameter ⋮ Elementary moves on lattice polytopes ⋮ An extremal property of lattice polygons ⋮ An elementary algorithm for digital arc segmentation ⋮ Limit shape of convex lattice polygons having the minimal \(L_\infty\) diameter w. r. t. the number of their vertices ⋮ Short simplex paths in lattice polytopes

Cites Work

• On the number of linear partitions of the \((m,n)\)-grid
• On integer points in polyhedra
• On integer points in polyhedra: A lower bound
• Convex lattice polygons of minimum area
• On the number of digital straight line segments
• Unnamed Item
• Unnamed Item
• Unnamed Item