Convex hulls and output-sensitive bounds

After sorting distinct points lexicographically, the monotone-chain algorithm constructs lower and upper boundaries. While appending a point, it removes the current last point whenever the new triple fails the required strict counterclockwise turn on the lower chain. Removing collinear intermediate points implements our extreme-vertex convention. The maintained chain stays convex, and each removed point lies on or above the candidate lower boundary rather than becoming a missing extreme point. The upper chain uses the corresponding reversed traversal.

Every point is pushed once and popped at most once on each chain, so the scan after sorting is linear. Sorting dominates at the usual logarithmic factor. Retaining every collinear boundary input changes the zero-orientation policy and requires special care on an entirely collinear input to avoid duplicated traversal. Deduplication is likewise part of the specification: repeated identifiers at one position do not create extra geometric vertices. The output order, rather than an unordered set of locations, is what makes subsequent polygon operations straightforward.

Gift wrapping chooses the next supporting vertex by scanning all input points, so a small number of hull vertices can make it attractive. Chan's method instead partitions the input into groups of at most a guessed size, builds each small hull, and uses tangent queries to choose the next wrapped vertex. It stops a phase after the guessed number of wrapping steps. If the hull closes, the phase succeeds; otherwise a larger guess is required. Collinear tangent ties choose the farther extreme point consistently.

Building the small hulls costs the input size times the logarithm of the guess. The bounded wrapping phase has the same asymptotic cost because tangent queries on the small convex polygons are logarithmic. Doubly exponential guesses make the logarithms grow geometrically, so failed phases do not accumulate an extra logarithmic factor. The successful guess is large enough to cover the actual output size. Ordinary exponential guesses would require a different summation and do not yield this particular simple accounting argument.

When every input point is extreme, the output-sensitive bound becomes the usual sorting-scale bound. Points on a suitable strictly convex curve can encode a sorting problem through their hull order, explaining the familiar worst-case lower bound in a comparison or algebraic decision-tree setting. Conversely, a huge collection of interior points with a tiny hull can benefit from output sensitivity. These statements depend on the computational model; bounded integer grids or special preordered inputs may permit different algorithmic tradeoffs.

The hull also behaves predictably under an invertible affine transformation: taking the hull and transforming commute, and extreme vertices remain extreme. Area scales by the absolute determinant, although Euclidean lengths and angles generally change. This gives a useful test of geometry without claiming that an affine map preserves every later structure, such as a Euclidean Delaunay triangulation. Hull construction, nearest-neighbor geometry, and geometric measurement each have their own invariant quantities.