Convex layers

In computational geometry, the convex layers of a set of points in the Euclidean plane are a sequence of nested convex polygons having the points as their vertices.

The outermost one is the convex hull of the points and the rest are formed in the same way recursively.

The innermost layer may be degenerate, consisting only of one or two points.

[1] An early application of the convex layers was in robust statistics, as a way of identifying outliers and measuring the central tendency of a set of sample points.

[5] Convex layers may be used as part of an efficient range reporting data structure for listing all of the points in a query half-plane.

The points in the half-plane from each successive layer may be found by a binary search to find the most extreme point in the direction of the half-plane, and then searching sequentially from there.

Fractional cascading can be used to speed up the binary searches, giving total query time