Preconditioning 2D integer data for fast convex hull computations
Cadenas, O (2016). Preconditioning 2D integer data for fast convex hull computations. PLoS ONE. 11 (3).
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.
|Keywords||Computing Convex Hull; 2D Integer data; Preconditioning data; MD Multidisciplinary; General Science & Technology|
|Journal citation||11 (3)|
|Publisher||Public Library of Science (PLoS)|
|Digital Object Identifier (DOI)||doi:10.1371/journal.pone.0149860|
|03 Mar 2016|
|Publication process dates|
|Deposited||08 May 2017|
|Accepted||22 Feb 2016|
CC BY 4.0
2views this month
0downloads this month