Skip to main content

Preconditioning 2D integer data for fast convex hull computations

Oswaldo, José, Megson, Graham M., Hendriks, Cris L. Luengo (2016) Preconditioning 2D integer data for fast convex hull computations. PLoS ONE, 11 (3). Article Number 149860. ISSN 1932-6203. (doi:10.1371/journal.pone.0149860) (KAR id:57349)

PDF (Fast method to pre-process 2D integer data points before applying any convex hull algorithm; doing this accelerates the overall process.) Publisher pdf
Language: English


Download (1MB) Preview
[thumbnail of Fast method to pre-process 2D integer data points before applying any convex hull algorithm; doing this accelerates the overall process.]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL
http://dx.doi.org/10.1371/journal.pone.0149860

Abstract

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ? n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ? n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ? n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

Item Type: Article
DOI/Identification number: 10.1371/journal.pone.0149860
Subjects: Q Science > QA Mathematics (inc Computing science) > QA440 Geometry
Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Engineering and Digital Arts
Depositing User: Jose Oswaldo Cadenas
Date Deposited: 23 Sep 2016 07:35 UTC
Last Modified: 16 Feb 2021 13:37 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/57349 (The current URI for this page, for reference purposes)
Oswaldo, José: https://orcid.org/0000-0003-4152-6458
  • Depositors only (login required):

Downloads

Downloads per month over past year