О числе вершин выпуклого многоугольника, попадающих на прямую Брезенхема
Получена: 06.11.2026 Принята: 06.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 168–171
Аннотация
В статье исследуется вопрос о максимальном числе вершин выпуклого целочисленного многоугольника, которые могут одновременно оказаться на прямой Брезенхема при её параллельном переносе вдоль рационального вектора. В отличие от классической задачи линейного программирования с непостоянной линейной целевой функцией, где экстремум достигается не более чем в двух вершинах, в дискретном случае число вершин, одновременно лежащих на прямой Брезенхема, может быть сколь угодно большим.
Ключевые слова: прямая Брезенхема, выпуклая оболочка, целочисленная решётка, рациональный тангенс.
BibTeX
@article{IS-Kasai2026,
author = {Касай, Анна Алексеевна},
title = {{О числе вершин выпуклого многоугольника, попадающих на прямую Брезенхема}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {168--171},
}
AMSBIB
\RBibitem{IS-Kasai2026}
\by А.\,А.~Касай
\paper О числе вершин выпуклого многоугольника, попадающих на прямую Брезенхема
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 168--171
EN