Sequential and Parallel Approximate Convex Hull Algorithms

Abstract

This paper defines the area measure of the quality of approximate convex hulls and proposes two new approximate convex hull algorithms. The first one is superior to known  techniques under the area measure and comparable under the distance measure and time complexity. The second algorithm is superior to all known algorithms in both area and distance measures (including the first algorithm) while having slightly higher time complexity. Corresponding parallel algorithms for finding approximate convex hull are also described.