Some Applications of Optimal Control Problems in Computational Geometry

Convex hulls and shortest paths are fundamental problems in Computational Geometry. Firstly, based on the idea of the Method of Orienting Curves (introduced by Phu in Optimization, 18 (1987) pp. 65-81 for solving optimal control problems with state constraints), we present an efficient algorithm to determine the convex hull of a finite planar set. The convex hull is determined by parts of orienting lines and a final line. Two advantages of this algorithm over some variations of Graham’s convex hull algorithm are presented. Secondly, we discuss the use of the Method of Orienting Curves in finding the shortest path between two points in a polygon. We deal with the convex rope problem, posed by Peshkin and Sanderson in IEEE J. Robotics Automat, 2 (1986) pp. 53-58, for finding the counterclockwise and clockwise convex ropes starting at the vertex a and ending at the vertex b of a simple polygon, where a is on the boundary of the convex hull of the polygon and b is visible from infinity. Based on the idea of the Method of Orienting Curves, an algorithm to determine the convex ropes, without resorting to a linear-time triangulation algorithm and without resorting to a convex hull algorithm for the polygon, is proposed. Next, we present an efficient algorithm for finding the Euclidean shortest path in the polygon between two vertices a and b without resorting to a linear-time triangulation algorithm, that provides a contribution to the solution of the open question raised by J. S. B. Mitchell in J. R. Sack and J. Urrutia, eds, Handbook of Computational Geometry, Elsevier Science B. V., 2000, p. 642. The use of the idea of the direct multiple shooting method (introduced by Bock in 1984 for direct solution of optimal control problems) in finding the shortest path problem above is also discussed.