Preconditioning 2D integer data for fast convex hull computations
Contribuinte(s) |
Rocchini, Duccio |
---|---|
Data(s) |
01/03/2016
|
Resumo |
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. |
Formato |
text |
Identificador |
http://centaur.reading.ac.uk/62042/1/journal.pone.0149860.PDF Cadenas, J. O. <http://centaur.reading.ac.uk/view/creators/90000433.html>, Megson, G. M. and Luengo Hendriks, C. L. (2016) Preconditioning 2D integer data for fast convex hull computations. PLoS ONE, 11 (3). e0149860. ISSN 1932-6203 doi: 10.1371/journal.pone.0149860 <http://dx.doi.org/10.1371/journal.pone.0149860> |
Idioma(s) |
en |
Publicador |
Public Library of Science |
Relação |
http://centaur.reading.ac.uk/62042/ creatorInternal Cadenas, José Oswaldo http://dx.doi.org/10.1371/journal.pone.0149860 10.1371/journal.pone.0149860 |
Direitos |
cc_by_4 |
Tipo |
Article PeerReviewed |