Accessibility navigation


Rapid preconditioning of data for accelerating convex hull algorithms

Cadenas Medina, J. and Megson, G. M. (2014) Rapid preconditioning of data for accelerating convex hull algorithms. Electronics Letters, 50 (4). pp. 270-272. ISSN 0013-5194

[img]
Preview
Text - Accepted Version
· Please see our End User Agreement before downloading.

173kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1049/el.2013.3507

Abstract/Summary

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
Refereed:Yes
Divisions:Faculty of Science
ID Code:39797
Publisher:Institution of Engineering and Technology (IET)

Downloads

Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation