An Efficient Algorithm for Finding the Minimum Perimeter Convex Hull of Disjoint Segments

In this paper1, we propose an efficient algorithm about a convex hull of a disjoint segment collection given in the plane, which has the minimum perimeter. That is to say each segment is completely or partly contained in the convex hull. We present an algorithm to solve this problem by contracting a larger convex polygon containing all end points of given segments, constructed by Graham Scanning Algorithm, to the smallest which only comprised by some indispensable points. To achieve the minimum perimeter, we also assess the relationships between the triangle that formed by three adjacent points and some segments and add segments that inside the triangle by determining the shortest route of a series of segments. Then we give an O(n4) algorithm to solve this problem. Our novel algorithm holds the complexity of O(n4) and is applicable to the robot walking route, the optimal distribution route in logistics planning, the minimum cost travel route and the cutting of machine parts.