title: Preconditioning 2D Integer Data for Fast Convex Hull Computations.
abstract: In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.
authors.affiliation: School of Systems Engineering, The University of Reading, Reading, RG6 6AX, United Kingdom.
authors.forename: José Oswaldo
authors.initials: JO
authors.lastname: Cadenas
authors.affiliation: School of Electronics and Computer Science, University of Westminster, London, W1W 6XH, United Kingdom.
authors.forename: Graham M
authors.initials: GM
authors.lastname: Megson
authors.affiliation: Department of Information Technology, Uppsala University, Box 337, SE-751 05 Uppsala, Sweden.
authors.forename: Cris L
authors.initials: CL
authors.lastname: Luengo Hendriks
mesh_terms: D000465:Algorithms; D000818:Animals; D021621:Imaging, Three-Dimensional; D008279:Magnetic Resonance Imaging; D008322:Mammals; D016571:Neural Networks, Computer; D010163:Paleontology