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.
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
Publishernstitution of Engineering and Technology
ISSN0013-5194
Digital Object Identifier (DOI)doi:10.1049/el.2013.3507
Publication dates
Print13 Feb 2014
Publication process dates
Deposited09 May 2017
Accepted09 Jan 2014
Accepted author manuscript
License
CC BY 4.0
Permalink -

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

  • 1
    total views
  • 22
    total downloads
  • 0
    views this month
  • 2
    downloads this month

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