Preprocessing 2D data for fast convex hull computations

Journal article


Cadenas, O and Megson, GM (2019). Preprocessing 2D data for fast convex hull computations. PLoS ONE. 14 (2), p. e0212189.
AuthorsCadenas, O and Megson, GM
Abstract

© 2019 Cadenas, Megson. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. This paper presents a method to reduce a set of n 2D points to a smaller set of s 2D points with the property that the convex hull on the smaller set is the same as the convex hull of the original bigger set. The paper shows, experimentally, that such reduction accelerates computations; the time it takes to reduce from n down to s points plus the time of computing the convex hull on the s points is less than the time to compute the convex hull on the original set of n points. The method accepts 2D points expressed as real numbers and thus extends our previous method that required points as integers. The method achieves a percentage of reduction of points of over 90% in a collections of four datasets. This amount of reduction provides speedup factors of at least two for various common convex hull algorithms. Theoretically, the reduction method executes in time within O(n) and thus is suitable for preprocessing 2D data before computing the convex hull by any known algorithm.

Year2019
JournalPLoS ONE
Journal citation14 (2), p. e0212189
ISSN1932-6203
Digital Object Identifier (DOI)doi:10.1371/journal.pone.0212189
Publication dates
Print01 Feb 2019
Publication process dates
Deposited18 Mar 2019
Accepted29 Jan 2019
Publisher's version
License
CC BY 4.0
Permalink -

https://openresearch.lsbu.ac.uk/item/867wv

  • 3
    total views
  • 32
    total downloads
  • 3
    views this month
  • 6
    downloads this month

Related outputs

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.
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).
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.
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.
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.
Pipelined median architecture
Cadenas, O (2015). Pipelined median architecture. Electronics Letters. 51 (24), pp. 1999-2001.
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).
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.
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).