Preconditioning 2D integer data for fast convex hull computations

Journal article


Cadenas, O, Megson, G.M. and Luengo Hendriks, C.L. (2016). Preconditioning 2D integer data for fast convex hull computations. PLoS ONE. 11 (3). https://doi.org/10.1371/journal.pone.0149860
AuthorsCadenas, O, Megson, G.M. and Luengo Hendriks, C.L.
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.

KeywordsComputing Convex Hull; 2D Integer data; Preconditioning data; MD Multidisciplinary; General Science & Technology
Year2016
JournalPLoS ONE
Journal citation11 (3)
PublisherPublic Library of Science (PLoS)
ISSN1932-6203
Digital Object Identifier (DOI)https://doi.org/10.1371/journal.pone.0149860
Publication dates
Print03 Mar 2016
Publication process dates
Deposited08 May 2017
Accepted22 Feb 2016
Publisher's version
License
File Access Level
Open
Permalink -

https://openresearch.lsbu.ac.uk/item/874xz

Download files


Publisher's version
journal.pone.0149860.pdf
License: CC BY 4.0
File access level: Open

  • 45
    total views
  • 98
    total downloads
  • 3
    views this month
  • 1
    downloads this month

Export as

Related outputs

Preprocessing 2D data for fast convex hull computations
Cadenas, O and Megson, GM (2019). Preprocessing 2D data for fast convex hull computations. PLoS ONE. 14 (2), p. e0212189. https://doi.org/10.1371/journal.pone.0212189
KurSL: Model of anharmonic coupled oscillations based on Kuramoto coupling and Sturm-Liouville problem
Cadenas, O, Laszuk, D and Slawomir, N (2018). KurSL: Model of anharmonic coupled oscillations based on Kuramoto coupling and Sturm-Liouville problem. Advances in Data Science and Adaptive Analysis. 10 (02). https://doi.org/10.1142/S2424922X18400028
Running Median Algorithm and Implementation for Integer Streaming Applications
Cadenas, O and Megson, GM (2018). Running Median Algorithm and Implementation for Integer Streaming Applications. IEEE Embedded Systems Letters. 11 (2), pp. 58-61. https://doi.org/10.1109/LES.2018.2868409
Rapid preconditioning of data for accelerating convex hull algorithms
Cadenas, O and Megson, G (2014). Rapid preconditioning of data for accelerating convex hull algorithms. Electronics Letters. 50 (4), pp. 270-272. https://doi.org/10.1049/el.2013.3507
Virtualization for cost-effective teaching of assembly language
Cadenas, O, Sherratt, S, Howlett, D, Guy, C and Lundqvist, K (2015). Virtualization for cost-effective teaching of assembly language. IEEE Transactions on Education. 58 (4), pp. 282-288. https://doi.org/10.1109/TE.2015.2405895
Median architecture by accumulative parallel counters
Cadenas, O, Megson, G and Sherratt, S (2015). Median architecture by accumulative parallel counters. IEEE Transactions on Circuits and Systems II: Express Briefs. 62 (7), pp. 661-665. https://doi.org/10.1109/TCSII.2015.2415655
Pipelined median architecture
Cadenas, O (2015). Pipelined median architecture. Electronics Letters. 51 (24), pp. 1999-2001. https://doi.org/10.1049/el.2015.1898
EMD performance comparison: single vs double floating points
Laszuk, D, Cadenas, O. and Nasuto, J (2016). EMD performance comparison: single vs double floating points. International journal of signal processing systems. 4 (4), pp. 349-353. https://doi.org/10.18178/ijsps.4.4.349-353
On the Phase Coupling of Two Components Mixing in Empirical Mode Decomposition
Laszuk, D, Cadenas, O. and Nasuto, Slawomir J. (2016). On the Phase Coupling of Two Components Mixing in Empirical Mode Decomposition. Advances in Data Science and Adaptive Analysis. 8 (1). https://doi.org/10.1142/S2424922X16500042