ABSTRACT
Planning collision-free motion and recognizing shapes are central tasks in robotics and automated assembly systems, in particular. In both cases, the process is complicated by the necessity to operate in real-time and the occasional presence of fairly complex objects. To cope with the complexity of the geometric problems at hand, two lines of attack can be contemplated: one involves simplifying the shapes by computing approximations of them; the other calls for rewriting the objects as combinations of simple parts. Both of these approaches have met with considerable success in computer graphics and automated design, and their relevance to robotics as a whole is evident. It is the aim of this paper to
2.1. Convex Hulls
The convex hull of a set S of n points is the intersection of all convex sets containing S. We omit the proof that the convex hull of S, denoted C. is a convex polygon whose vertices (the extreme points) are points of S. A simple characterization of a vertex of the convex hull states that a point is extreme if and only if it does not lie strictly inside any triangle formed by any three points. This leads to a trivial 0(n4 ) time algorithm. For each such triangle, eliminate each point lying inside. The remaining points will be extreme. A number of more efficient algorithms have been (only recently) discovered. We propose here to review some of the most important, practical, and/or original methods. The honor of discovering the first optimal convex hull algorithm goes to R. Graham (1972). Graham Scan: The method involves sorting the points in a preliminary stage and then retrieving the convex hull in linear time via a procedure traditionally known as a Graham scan. Let {p 1 , ••• ,p11} be the points of S sorted angularly clockwise around p 1, the point of S with largest y-coordinate (take the one with largest x-coordinate to break ties, if necessary). Computing the list of p/s can be done in O(nlogn) time.
