Rapid preconditioning of data for accelerating convex hull algorithms

Journal article

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
AuthorsCadenas, O and Megson, G
Abstract

Given a dataset of two-dimensional points in the plane with integer coordinates, the method proposed reduces a set of n points down to a set of s points s ≤ n, such that the convex hull on the set of s points is the same as the convex hull of the original set of n points. The method is O(n). It helps any convex hull algorithm run faster. The empirical analysis of a practical case shows a percentage reduction in points of over 98%, that is reflected as a faster computation with a speedup factor of at least 4.

KeywordsConvex hull; Acceleration of computation; 0906 Electrical And Electronic Engineering; 0801 Artificial Intelligence And Image Processing; 1005 Communications Technologies; Electrical & Electronic Engineering
Year2014
JournalElectronics Letters
Journal citation50 (4), pp. 270-272
PublisherInstitute of Engineering and Technology (IET)
ISSN0013-5194
Digital Object Identifier (DOI)https://doi.org/10.1049/el.2013.3507
Publication dates
Print13 Feb 2014
Publication process dates
Deposited09 May 2017
Accepted09 Jan 2014
Accepted author manuscript
License
Permalink -

https://openresearch.lsbu.ac.uk/item/87873

Download files

Accepted author manuscript
ELLPolyline-R6.pdf
License: CC BY 4.0

  • 87
    total views
  • 157
    total downloads
  • 3
    views this month
  • 0
    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
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
Preconditioning 2D integer data for fast convex hull computations
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
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