  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.
