Preprocessing 2D data for fast convex hull computations

Oswaldo Cadenas and Graham M Megson

PLOS ONE, 2019, vol. 14, issue 2, 1-15

Abstract: This paper presents a method to reduce a set of n 2D points to a smaller set of s 2D points with the property that the convex hull on the smaller set is the same as the convex hull of the original bigger set. The paper shows, experimentally, that such reduction accelerates computations; the time it takes to reduce from n down to s points plus the time of computing the convex hull on the s points is less than the time to compute the convex hull on the original set of n points. The method accepts 2D points expressed as real numbers and thus extends our previous method that required points as integers. The method achieves a percentage of reduction of points of over 90% in a collections of four datasets. This amount of reduction provides speedup factors of at least two for various common convex hull algorithms. Theoretically, the reduction method executes in time within O(n) and thus is suitable for preprocessing 2D data before computing the convex hull by any known algorithm.

Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0212189 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 12189&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0212189

DOI: 10.1371/journal.pone.0212189

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().