RECORD
An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations
Computational Geometry · Submitted 5 May 2015
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. | background 1.00 | 0.04 | 0.02 | asserted 0.99 |
| s2 | However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. | background 0.99 | 0.05 | 0.04 | asserted 0.67 |
| s3 | We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. | contribution 0.99 | 0.91 | 0.11 | asserted 0.99 |
| s4 | First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. | contribution 0.82 | 0.82 | 0.21 | asserted 0.99 |
| s5 | Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. | interpretation 0.83 | 0.29 | 0.22 | hedged possibility 0.49 |
| s6 | The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. | contribution 0.68 | 0.94 | 0.10 | asserted 0.96 |
| s7 | An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset. | result 1.00 | 0.95 | 0.57 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.