On the number of vertices of a convex polygon that lie on the Bresenham line.
Received: 06 Nov 2026 Accepted: 06 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 168–171
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
RU