The plane depth of a pair of distinct points in a finite set
is the minimum number of points on either open
side of a plane through
and
(Ramos and Viaña 2009, Edelsbrunner et al. 2026). The set is assumed
in general position, with no four points coplanar.
Equivalently, it is the minimum number of points to delete so that
and
span an polyhedron edge of the convex
hull of the remaining set. The quantity depends on the whole point set, not just
on the line segment joining the pair.
Let be the minimum, over
-point sets in convex position, meaning that every point is
a vertex of their convex hull, of their maximum pair
depth. Paraboloid lifting gives
, where
is the corresponding extremal circle
depth. The 2026 circle-depth construction therefore also disproves the proposed
asymptotic coefficient for
(Edelsbrunner et al. 2026).
Without assuming convex position, Edelsbrunner et al. (2026) proved that every -point set in general
position contains a pair of plane depth at least
.
More precisely, if
counts pairs of depth at most
, then for integers
,
For , they also proved
,
with equality attainable for every
even in convex position. These lower-depth and shallow-pair
bounds do not settle the sharp asymptotic maximum-pair depth for general point sets.