Abstract

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\mathcal{P}, where a is a vertex of the convex hull of P\mathcal{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\mathcal{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.

Author information

Contact details are reproduced from the original publication and may be historical.

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

Keywords

  • Convex hull
  • approximate algorithm
  • convex rope
  • shortest path
  • non-convex optimization
  • geodesic convexity

Mathematics Subject Classification

52A30, 52B55, 68Q25, 90C26, 65D18, 68R01

References

  1. P. T. An: Reachable gasps on a polygon of a robot arm: finding the convex rope without triangulation, J. Robotics Automation 25/4 (2010) 304–310.https://doi.org/10.2316/Journal.206.2010.4.206-3325Google Scholar
  2. P. T. An: Optimization Approaches for Computational Geometry, Publishing House for Science and Technology, Vietnam Academy of Science and Technology, Hanoi (2017).Google Scholar
  3. P. T. An, N. N. Hai, T. V. Hoai: Direct multiple shooting method for solving approximate shortest path problems, J. Comp. Appl. Math. 244 (2013) 67–76.https://doi.org/10.1016/j.cam.2012.11.001Google Scholar
  4. P. T. An, N. N. Hai, T. V. Hoai, L. H. Trang: On the performance of triangulationbased multiple shooting method for 2D geometric shortest path problems, Trans. Large-Scale Data Knowledge Centered Syst. 16 (2014) 45–56.https://doi.org/10.1007/978-3-662-45947-8_4Google Scholar
  5. P. T. An, T. V. Hoai: Incremental convex hull as an orientation to solving the shortest path problem, Int. J. Inf. Elect. Eng. 2/5 (2012) 652–655.Google Scholar
  6. P. T. An, L. H. Trang: Multiple shooting approach for computing shortest descending paths on convex terrains, Comp. Appl. Math. 37/4 (2018) 1–31.Google Scholar
  7. B. Chazelle: A theorem on polygon cutting with applications, in: Proc. 23rd IEEE Symposium on Foundations of Computer Science, Chicago (1982) 339–349.https://doi.org/10.1109/SFCS.1982.58Google Scholar
  8. L. Guibas, J. Hershberger, D. Leven, M. Sharir, R. E. Tarjan: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica 2 (1987) 209–233.https://doi.org/10.1007/BF01840360Google Scholar
  9. N. N. Hai, P. T. An: Blaschke-type theorem and separation of disjoint closed geodesic convex sets, J. Optimization Theory Appl. 151/3 (2011) 541–551.https://doi.org/10.1007/s10957-011-9868-5Google Scholar
  10. N. N. Hai, P. T. An, P. T. T. Huyen: Shortest paths along a sequence of line segments in Euclidean spaces, J. Convex Analysis 26/4 (2019) 1089–1112.https://doi.org/10.68381/jca26060Google Scholar
  11. P. J. Heffernan, J. S. B. Mitchell: Structured visibility profiles with applications to problems in simple polygons, in: Proc. 6th Annual ACM Symposium on Computational Geometry (1990) 53–62.https://doi.org/10.1145/98524.98536Google Scholar
  12. T. V. Hoai, P. T. An, N. N. Hai: Multiple shooting approach for computing approximately shortest paths on convex polytopes, J. Comp. Appl. Math. 317 (2017) 235–246.https://doi.org/10.1016/j.cam.2016.10.026Google Scholar
  13. D. T. Lee, F. P. Preparata: Euclidean shortest paths in the presence of rectilinear barriers, Networks 14/3 (1984) 393–410.https://doi.org/10.1002/net.3230140304Google Scholar
  14. F. Li, R. Klette: Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm, in: Pacific-Rim Symposium on Image and Video Technology, Springer, Berlin (2006) 280–291.https://doi.org/10.1007/11949534_28Google Scholar
  15. T. Lozano-Perez: Automatic planning of manipulator transfer movements, IEEE Trans. Systems Man Cybernetics SMC-11/10 (1981) 681–698.https://doi.org/10.1109/TSMC.1981.4308589Google Scholar
  16. A. A. Melkman: On-line construction of the convex hull of a simple polyline, Inf. Processing Letters 25 (1987) 11–12.https://doi.org/10.1016/0020-0190(87)90086-XGoogle Scholar
  17. M. A. Peshkin, A. C. Sanderson: Reachable grasps on a polygon: the convex rope algorithm, IEEE J. Robotics Automation 2/1 (1986) 5–58.https://doi.org/10.1109/JRA.1986.1087030Google Scholar
  18. P. Song, Z. Fu, L. Liu: Grasp planning via hand-object geometric fitting, The Visual Computer 34/2 (2018) 257–270.https://doi.org/10.1007/s00371-016-1333-xGoogle Scholar
  19. G. T. Toussaint: Computing geodesic properties inside a simple polygon, Revue d’Intelligence Artificielle 3/2 (1989) 9–42.Google Scholar
  20. Z. Xue, J. M. Zoellner, R. Dillmann: Automatic optimal grasp planning based on found contact points, in: IEEE International Conference on Advanced Intelligent Mechatronics (2008) 1053–1058.https://doi.org/10.1109/AIM.2008.4601807Google Scholar

Suggested citation

L. H. Trang, N. T. Le, P. T. An. “Finding Approximately Convex Ropes in the Plane.” Journal of Convex Analysis 30 (2023), No. 1, 249–270. https://doi.org/10.68381/jca30014

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press LLC.