A Four-Sector Geometric Filtering Algorithm for Linear-Time Convex Hulls

Discarding points that cannot be hull vertices before running a standard O(n log n) algorithm is a well-known way to speed up planar convex hull computation. Classical filters (Akl–Toussaint and its octagonal extension) test every point against the edges of a polygon of extreme points, which requires cross products. This preprint describes a filter that replaces this test by range comparisons on a few linear forms (x, y, x+y, y−x, and optionally four more). From the extreme points, a region R is built once, in exact integer arithmetic, using a closed-form contraction factor. R is proved to lie inside the polygon of extreme points, so discarding the points strictly inside R never removes a hull vertex. Afterwards each point costs only additions and integer comparisons. A small probe sample then chooses between 8 directions, 16 directions, or no filtering at all. In C++ experiments on integer points (up to 10^7 points, Google Colab virtual machines), the method is up to about 20x faster than a plain monotone chain on uniform-square, Gaussian and lattice inputs. Against the original heaphull code of Ferrada et al., on integer points that float represents exactly (up to 10^6 points), it was 1.3–2.8x faster on five of six input types and about 0.8–0.9x (slower) on a lattice. On points on a circle it stays within about 7% of the baseline, where heaphull was 1.8–3.0x slower. A variant for pure Python is included; its measurements are preliminary. The octagonal filter, polygons of 16 extreme points, and sample-based extremes are known. The claims here are limited to the comparison-only inner region with its exact construction and to the probe-based choice of directions, which we did not find in the (limited) literature we surveyed. Limitations: timings come from shared cloud virtual machines; at most 10^7 points; comparison with the original heaphull only up to 10^6 points; the C++ code assumes coordinates of absolute value at most 2^30; the Python timings come from an earlier version of the region construction.