EFFICIENT CONVEX HULL ALGORITHMS FOR PATTERN RECOGNITION APPLICATIONS.

The role of the convex hull in the field of pattern recognition is briefly reviewed. Two efficient algorithms for obtaining the convex hull of n points in the plane are proposed and their theoretical analyses presented. The first algorithm is applicable when the points are distinct, as in the pattern classification problem or the image processing problem in which the pattern is not connected. The algorithm has worst case complexity of 0(n log n), and an expected running time of 0(n). Experiments with the algorithm are described that confirm its intuitive and theoretical merits. The second algorithm is applicable for connected patterns.