For citation:
Nefedov V. N., Saushkin M. N. Description of the set of admissible piecewise linear routes with n turns. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2026, vol. 26, iss. 3, pp. 350-373. DOI: 10.18500/1816-9791-2026-26-3-350-373, EDN: KBRIXO
Description of the set of admissible piecewise linear routes with n turns
In this study, we consider polygonal lines connecting two given points $A,B\in\mathbb{R}^2$ and consisting of exactly $n+1$ segments (i.e., having $n$ turn points). The absolute value of the turn angle at each interior point is bounded by a given number $\varphi\in(0,\pi/2)$. Under the condition $n\varphi<\pi$, we describe the set to which all interior vertices of such a polygonal line belong. It is proved that for any point $B^{(1)}$ from this set there exists a polygonal line satisfying the given constraints. Based on these results, an explicit formula is obtained that describes the set of all admissible sequences $\bigl(B^{(1)},\ldots,B^{(n)}\bigr)$ of corner points. The resulting description can serve as a foundation for constructing algorithms for enumerating admissible polygonal lines and for solving optimization problems for an objective function that takes into account both the cost of traversing the segments and the cost of making turns.
- 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, pp. 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, pp. 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, pp. 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. In: Proceedings of 1995 IEEE International Conference on Robotics and Automation. Nagoya, Japan, 1995, vol. 2, pp. 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, pp. 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, pp. 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, pp. 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, pp. 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, pp. 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, pp. 195–218. DOI: https://doi.org/10.1016/S0925-7721(96)00012-0
- Nefedov V. N., Nasedkin G. K. The problem of finding an optimal piecewise-linear route with n turns. Materialy XXIV Mezdunarodnoj konferentsii po vychislitel’noi mekhanike i sovremennym prikladnym programmnym sistemam (VMSPPS’2025) [Proceedings of the XXIV International Conference on Computational Mechanics and Modern Applied Software Systems (VMSPPS’2025)] (Alushta, September 7–13, 2025). Moscow, Moscow Aviation Institute Publ., 2025, pp. 283–284 (in Russian). 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
- Nefedov V. N., Svoikin F. V., Garibyan B. A., Ryapukhin A. V., Korolko N. S. Finite approximation methods for two-dimensional sets and their application to geometric optimization problems. Journal of Samara State Technical University. Ser. Physical and Mathematical Sciences, 2025, vol. 29, iss. 1, pp. 129–157 (in Russian). DOI: https://doi.org/10.14498/vsgtu2131, EDN: DMJLWE
- Efimov N. V. Kratkij kurs analiticheskoj geometrii [Short course in analytic geometry]. Moscow, Fizmatlit, 2006. 240 p. (in Russian).
- Brøndsted A. An introduction to convex polytopes. Moscow, Mir, 1988. 240 p. (in Russian).
- 159 reads