Constructing a strongly convex superhull of points

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which co ntains CH(S) with strong convexity. An epsilon -convex delta -superhull of S is a convex polygon P satisfying the following conditions: (1) P has at m ost O(n) vertices, (2) P contains CH(S), (3) no vertex of P lies farther th an delta outside CH(S), and (4) P remains convex even if its vertices are p erturbed by as much as epsilon. The parameters epsilon and delta represent the strength of convexity of P and the degree of approximation of P to CH(S ), respectively. In this paper, we show that there exists an E-convex (2 4 root2) epsilon -superhull with at most n vertices for any S and any epsil on greater than or equal to 0 and it can be constructed in O(n log n) time (in O(n) time if S is sorted).