Rapid preconditioning of data for accelerating convex hull algorithms

Medina, Jose Cadenas and Megson, G. M. (2014) Rapid preconditioning of data for accelerating convex hull algorithms. Electronics Letters, 50 (4). pp. 270-272. ISSN 0013-5194. E-ISSN 1350-911X. (doi:https://doi.org/10.1049/el.2013.3507) (Full text available)

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.

Item Type: Article
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800 Electronics (see also: telecommunications) > TK7874 Microelectronics
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800 Electronics (see also: telecommunications) > TK7880 Applications of electronics (inc industrial & domestic) > TK7895.E42 Embedded Systems
Divisions: Faculties > Sciences > School of Engineering and Digital Arts > Instrumentation, Control and Embedded Systems
Depositing User: Jose Oswaldo Cadenas
Date Deposited: 20 Sep 2016 13:56 UTC
Last Modified: 21 Sep 2016 11:25 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/57356 (The current URI for this page, for reference purposes)
Medina, Jose Cadenas: https://orcid.org/0000-0003-4152-6458
  • Depositors only (login required):

Downloads

Downloads per month over past year