Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Нефедов В. Н., Саушкин М. Н. Описание множества допустимых кусочно-прямолинейных маршрутов с n поворотами // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2026. Т. 26, вып. 3. С. 350-373. DOI: 10.18500/1816-9791-2026-26-3-350-373, EDN: KBRIXO

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.08.2026
Полный текст:
(downloads: 11)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
514.112.4+514.177.2
EDN: 
KBRIXO

Описание множества допустимых кусочно-прямолинейных маршрутов с n поворотами

Авторы: 
Нефедов Виктор Николаевич, Московский авиационный институт (национальный исследовательский университет)
Саушкин Михаил Николаевич, Самарский государственный технический университет
Аннотация: 

Рассматриваются кусочно-прямолинейные ломаные, соединяющие две заданные точки $A,B\in\mathbb{R}^2$ и состоящие ровно из $n+1$ звена (т.е. имеющие $n$ точек поворота). Абсолютная величина угла поворота в каждой внутренней точке ограничена заданным числом $\varphi\in(0,\pi/2)$. При условии $n\varphi<\pi$ описано множество, которому принадлежат все внутренние вершины такой ломаной. Доказано, что для любой точки $B^{(1)}$ из этого множества существует ломаная с заданными параметрами. На основе этих результатов получена явная формула, описывающая множество всех допустимых последовательностей $\bigl(B^{(1)},\ldots,B^{(n)}\bigr)$ угловых точек ломаной. Полученное описание может служить основой для построения алгоритмов перечисления допустимых ломаных и решения задач оптимизации целевой функции, учитывающей стоимость прохождения звеньев и стоимость поворотов.

Список источников: 
  1. Ranjbar Divkoti M. R., Nouri-Baygi M. Path planning in polygonal domains for robots with limited turning abilities // 2017 7th International Conference on Computer and Knowledge Engineering (ICCKE). Mashhad, Iran, 2017. P. 308–313. DOI: https://doi.org/10.1109/ICCKE.2017.8167897
  2. Wang C., Liu Q. Projection and geodesic-based pipe routing algorithm // IEEE Transactions on Automation Science and Engineering. 2011. Vol. 8, iss. 3. P. 641–645. DOI: https://doi.org/10.1109/TASE.2010.2099219
  3. De Smith M. J. Determination of gradient and curvature constrained optimal paths // Computer-Aided Civil and Infrastructure Engineering. 2006. Vol. 21, iss. 1. P. 24–38. DOI: https://doi.org/10.1111/j.1467-8667.2005.00414.x
  4. Bicchi A., Casalino G., Santilli C. Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles // Proceedings of 1995 IEEE International Conference on Robotics and Automation. Nagoya, Japan, 1995. Vol. 2. P. 1349–1354. DOI: https://doi.org/10.1109/ROBOT.1995.525466
  5. Chen D. Z., Daescu O., Hershberger J., Kogge P. M., Mi N., Snoeyink J. Polygonal path simplification with angle constraints // Computational Geometry. 2005. Vol. 32, iss. 3. P. 173–187. DOI: https://doi.org/10.1016/j.comgeo.2004.09.003
  6. Gholami Rudi A. Approximate curve-restricted simplification of polygonal curves // International Journal of Computer Mathematics: Computer Systems Theory. 2021. Vol. 6, iss. 2. P. 178–187. DOI: https://doi.org/10.1080/23799927.2021.1905717
  7. Agarwal P. K., Biedl T., Lazard S., Robbins S., Suri S., Whitesides S. Curvature-constrained shortest paths in a convex polygon // SIAM Journal on Computing. 2002. Vol. 31, iss. 6. P. 1814–1851. DOI: https://doi.org/10.1137/S0097539700374550
  8. Gewali L., Roman V. Generalization of shortest path map // 2010 Seventh International Conference on Information Technology: New Generations. Las Vegas, NV, USA, 2010. P. 296–300. DOI: https://doi.org/10.1109/ITNG.2010.247
  9. Bárány I., Pór A., Valtr P. Paths with no small angles // SIAM Journal on Discrete Mathematics. 2010. Vol. 23, iss. 4. P. 1655–1666. DOI: https://doi.org/10.1137/080716931
  10. Fekete S. P., Woeginger G. J. Angle-restricted tours in the plane // Computational Geometry. 1997. Vol. 8, iss. 4. P. 195–218. DOI: https://doi.org/10.1016/S0925-7721(96)00012-0
  11. Нефедов В. Н., Наседкин Г. К. Задача нахождения оптимального кусочно-прямолинейного маршрута с n поворотами // Материалы XXIV Международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС’2025) (Алушта, 07–13 сентября 2025 г.). Москва : МАИ, 2025. С. 283–284. EDN: DTTYXZ
  12. Nefedov V. N. Problem of finding an optimal piecewise linear path connecting two given points with the possibility of making n turns. arXiv: 2605.15449 [math.OC]. May 14, 2026. 99 p. DOI: https://doi.org/10.48550/arXiv.2605.15449
  13. Нефедов В. Н., Свойкин Ф. В., Гарибян Б. А., Ряпухин А. В., Королько Н. С. Методы аппроксимации двумерных множеств конечными множествами и их приложение к некоторым геометрическим задачам оптимизации // Вестник Самарского государственного технического университета. Серия: Физико-математические науки. 2025. Т. 29, № 1. С. 129–157. DOI: https://doi.org/10.14498/vsgtu2131, EDN: DMJLWE
  14. Ефимов Н. В. Краткий курс аналитической геометрии. Москва : Физматлит, 2006. 240 с.
  15. Брёндстед А. Введение в теорию выпуклых многогранников. Москва : Мир, 1988. 240 с.
Поступила в редакцию: 
05.05.2026
Принята к публикации: 
11.06.2026
Опубликована: 
31.08.2026