Journal of Convex Analysis 30 (2023), No. 1, 249--270
Copyright Heldermann Verlag 2023
Finding Approximately Convex Ropes in the Plane
Le Hong Trang
Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology
and: Vietnam National University Ho Chi Minh City, Thu Duc City, Ho Chi Minh City, Vietnam
Nguyen Thi Le
Institute of Mathematics, Vietnam Academy of Science and Technology, Hanoi, Vietnam
Phan Thanh An
Institute of Mathematical and Computational Sciences and Faculty of Applied Science, Ho Chi Minh City University of Technology, Vietnam
and: Vietnam National University Ho Chi Minh City, Thu Duc City, Ho Chi Minh City, Vietnam
thanhan@hcmut.edu.vn
The convex rope problem is to find a counterclockwise or clockwise convex rope starting at the vertex a and ending at the vertex b of a simple polygon P, where a is a vertex of the convex hull of P and b is visible from infinity. The convex rope mentioned is the shortest path joining a and b that does not enter the interior of P. In this paper, the problem is reconstructed as one of finding such shortest path in a simple polygon and solved by the method of multiple shooting. We then show that if the collinear condition of the method holds at all shooting points, then these shooting points form the shortest path. Otherwise, the sequence of paths obtained by the update of the method converges to the shortest path. The algorithm is implemented in C++ for numerical experiments.
Keywords: Convex hull, approximate algorithm, convex rope, shortest path, non-convex optimization, geodesic convexity.
MSC: 52A30, 52B55, 68Q25, 90C26, 65D18, 68R01.
[ Fulltext-pdf (2434 KB)] for subscribers only.