Rapid preconditioning of data for accelerating convex hull computations

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

Full description

Saved in:
Bibliographic Details
Published in:Electronics letters 2014-02, Vol.50 (4), p.270-272
Main Authors: Cadenas, J, Megson, G.M
Format: Article
Language:English
Subjects:
2D points
accelerating convex hull computations
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Artificial intelligence
Computation
Computer science
control theory
systems
convex hull algorithm
empirical analysis
Exact sciences and technology
geometry
Hulls
Hulls (structures)
Image and vision processing and display technology
integer coordinates
Mathematical models
Pattern recognition. Digital image processing. Computational geometry
Planes
Preconditioning
rapid preconditoning
speedup factor
Theoretical computing
Two dimensional
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:0013-5194
1350-911X
1350-911X
DOI:10.1049/el.2013.3507