Robust algorithms for constructing strongly convex hulls in parallel

AbstractGiven a set S of n points in the plane, an ε-strongly convex δ-hull of S is defined as a convex polygon P with the vertices taken from S such that no point of S lies farther than δ outside P and such that even if the vertices of P are perturbed by as much as ε, P remains convex. This paper presents the first parallel robust method for this generalized convex hull problem (note that the convex hull of S is the 0-strongly convex 0-hull of S). We show that an ε-strongly convex O(ε+β)-hull of S can be constructed in O(log3n) time using n processors with imprecise computations, where β is the error unit of primitive operations. This result also implies an improved sequential algorithm. Our algorithm consists of two parts: (1) computing a convex O(ε+β)-hull of n points, in O(log3n) time using n processors, and (2) constructing an ε-strongly convex O(ε+β)-hull of a convex polygon with n vertices, in O(log2n) time with n processors. We also find an approximate bridge of two sets with n points each, in O(log2n) time using n processors, which we use as a subroutine. All these algorithms are fundamental and have their own applications. The parallel computational model in this paper is the EREW PRAM