Research On A Solution Of Finding A Minimum Convex Hull For The Disjoint Segments Given In The Plane

In this paper,we research on a solution of finding a minimum convex hull for disjoint segments given in the plane.Our purpose is to obtain a shortest perimeter that contain or partly contain these segments.This problem not only has significant theoretical value,but also has more important practical application value.Because it is helpful to solve practical application problems such as walking route of robot,optimal distribution route of logistics planning and cutting machine components.This paper firstly gives a discussion of the TSP,WRP,Rubber-band algorithm and other relevant research results.Then on the basis of existing research results,research and analysis the problem about minimum boundary convex hull of given disjoint segments.And it points out that the problems existing in previous research,for example,high time complexity.In order to solve these problems,this paper presents an algorithm which the complexity is in O(n4)through the analysis of the position of segment and convex polygon and other geometric elements.This algorithm can be divided into two main processes.Firstly,find the convex hull of containing all the segments with the Graham Scan Algorithm.Secondly,contract the convex hull and make sure no segment is completely outside the convex hull to obtain a convex hull with a minimum boundary through the organic integration of the algorithm.