Для цитирования:
Нефедов В. Н., Саушкин М. Н. Описание множества допустимых кусочно-прямолинейных маршрутов с n поворотами // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2026. Т. 26, вып. 3. С. 350-373. DOI: 10.18500/1816-9791-2026-26-3-350-373, 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)$ угловых точек ломаной. Полученное описание может служить основой для построения алгоритмов перечисления допустимых ломаных и решения задач оптимизации целевой функции, учитывающей стоимость прохождения звеньев и стоимость поворотов.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Нефедов В. Н., Наседкин Г. К. Задача нахождения оптимального кусочно-прямолинейного маршрута с n поворотами // Материалы XXIV Международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС’2025) (Алушта, 07–13 сентября 2025 г.). Москва : МАИ, 2025. С. 283–284. EDN: DTTYXZ
- 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
- Нефедов В. Н., Свойкин Ф. В., Гарибян Б. А., Ряпухин А. В., Королько Н. С. Методы аппроксимации двумерных множеств конечными множествами и их приложение к некоторым геометрическим задачам оптимизации // Вестник Самарского государственного технического университета. Серия: Физико-математические науки. 2025. Т. 29, № 1. С. 129–157. DOI: https://doi.org/10.14498/vsgtu2131, EDN: DMJLWE
- Ефимов Н. В. Краткий курс аналитической геометрии. Москва : Физматлит, 2006. 240 с.
- Брёндстед А. Введение в теорию выпуклых многогранников. Москва : Мир, 1988. 240 с.
- 58 просмотров