Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On the number of vertices of a convex polygon that lie on the Bresenham line.

Abstract

The article examines the question of the maximum number of vertices of a convex integer polygon that can simultaneously lie on a Bresenham line when it is translated parallel to a rational vector. Unlike the classical linear programming problem with a non-constant linear objective function, where the extremum is achieved in no more than two vertices, in the discrete case the number of vertices simultaneously lying on a Bresenham line can be arbitrarily large.

Keywords: Bresenham’s line algorithm, convex hull, integer lattice, rational tangent.

BibTeX
@article{IS-Kasai2026,
  author  = {Kasai, Anna Alekseevna},
  title   = {{On the number of vertices of a convex polygon that lie on the Bresenham line.}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {168--171},
}
AMSBIB
\Bibitem{IS-Kasai2026}
\by A.\,A.~Kasai
\paper On the number of vertices of a convex polygon that lie on the Bresenham line.
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 168--171
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover