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.
Original language | English |
---|---|
Pages (from-to) | 270-272 |
Journal | Electronics Letters |
DOIs | |
Publication status | Published - 13 Feb 2014 |
Keywords
- 0906 Electrical And Electronic Engineering
- Acceleration of computation
- Electrical & Electronic Engineering
- Convex hull
- 1005 Communications Technologies
- 0801 Artificial Intelligence And Image Processing