# 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.

Authors | Cadenas, 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. |

Year | 2019 |

Journal | PLoS ONE |

Journal citation | 14 (2), p. e0212189 |

Publisher | Public Library of Science (PLoS) |

ISSN | 1932-6203 |

Digital Object Identifier (DOI) | doi:10.1371/journal.pone.0212189 |

Web address (URL) | https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0212189 |

Publication dates | |

Print | 01 Feb 2019 |

Publication process dates | |

Deposited | 18 Mar 2019 |

Accepted | 29 Jan 2019 |

Publisher's version | License CC BY 4.0 File Access Level Open |

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

##### 8

total views##### 39

total downloads##### 0

views this month##### 0

downloads this month

## Related outputs

##### 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).

##### 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.*

##### 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).