Back to Search
Start Over
Preprocessing 2D data for fast convex hull computations
- Source :
- PLoS ONE, PLoS ONE, Vol 14, Iss 2, p e0212189 (2019)
- Publication Year :
- 2019
- Publisher :
- Public Library of Science (PLoS), 2019.
-
Abstract
- © 2019 Cadenas, Megson. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. 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.
- Subjects :
- Convex hull
Speedup
Convex hull algorithms
Computer science
MathematicsofComputing_GENERAL
Computational Geometry
02 engineering and technology
Wildlife
Reduction (complexity)
0302 clinical medicine
Number Theory
0202 electrical engineering, electronic engineering, information engineering
Mammals
Multidisciplinary
Applied Mathematics
Simulation and Modeling
Software Engineering
Eukaryota
Physical Sciences
Vertebrates
Medicine
Engineering and Technology
Algorithm
Algorithms
Research Article
Statistical Distributions
Computer and Information Sciences
Science
Animal Types
Computation
Geometry
Research and Analysis Methods
Set (abstract data type)
03 medical and health sciences
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
020204 information systems
Real Numbers
Animals
Preprocessing
Real number
Organisms
Biology and Life Sciences
Probability Theory
Computing Methods
Distribution (mathematics)
Amniotes
Zoology
Mathematics
Software
030217 neurology & neurosurgery
Subjects
Details
- ISSN :
- 19326203
- Volume :
- 14
- Database :
- OpenAIRE
- Journal :
- PLOS ONE
- Accession number :
- edsair.doi.dedup.....bb48f2da58bfbffca58e952ba1f47736