Back to Search
Start Over
Preconditioning 2D Integer Data for Fast Convex Hull Computations.
- Source :
-
PLoS ONE . 3/3/2016, Vol. 11 Issue 3, p1-11. 11p. - Publication Year :
- 2016
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 11
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- PLoS ONE
- Publication Type :
- Academic Journal
- Accession number :
- 113477285
- Full Text :
- https://doi.org/10.1371/journal.pone.0149860