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

Text - Accepted Version
· Please see our End User Agreement before downloading.


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


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


Downloads per month over past year

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

Page navigation