О числе вершин выпуклого многоугольника, попадающих на прямую Брезенхема

Аннотация

В статье исследуется вопрос о максимальном числе вершин выпуклого целочисленного многоугольника, которые могут одновременно оказаться на прямой Брезенхема при её параллельном переносе вдоль рационального вектора. В отличие от классической задачи линейного программирования с непостоянной линейной целевой функцией, где экстремум достигается не более чем в двух вершинах, в дискретном случае число вершин, одновременно лежащих на прямой Брезенхема, может быть сколь угодно большим.

Ключевые слова: прямая Брезенхема, выпуклая оболочка, целочисленная решётка, рациональный тангенс.

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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover