
Journal of Convex Analysis 30 (2023), No. 1, 249270 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, nonconvex optimization, geodesic convexity. MSC: 52A30, 52B55, 68Q25, 90C26, 65D18, 68R01. [ Fulltextpdf (2434 KB)] for subscribers only. 