TOPICS
Search

Plane Depth


The plane depth of a pair of distinct points a,b in a finite set Y subset R^3 is the minimum number of points on either open side of a plane through a and b (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 a and b 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 Psi(n) be the minimum, over n-point sets in convex position, meaning that every point is a vertex of their convex hull, of their maximum pair depth. Paraboloid lifting gives Psi(n)<=Pi(n), where Pi(n) is the corresponding extremal circle depth. The 2026 circle-depth construction therefore also disproves the proposed 1/4 asymptotic coefficient for Psi(n) (Edelsbrunner et al. 2026).

Without assuming convex position, Edelsbrunner et al. (2026) proved that every n-point set in general position contains a pair of plane depth at least (2-sqrt(2))n/6+O(1). More precisely, if D_j(Y) counts pairs of depth at most j, then for integers 0<=j<=n/4-1,

 D_j(Y)<=3[(2j+1)n-(3j^2+6j+2)].

For n>=4, they also proved D_1(Y)<=6n-18, with equality attainable for every n>=9 even in convex position. These lower-depth and shallow-pair bounds do not settle the sharp asymptotic maximum-pair depth for general point sets.


See also

Circle Depth, Convex Hull

Explore with Wolfram|Alpha

References

Edelsbrunner, H.; Garber, A.; Saghafian, M.; and Welzl, E. "The Deepest Pairs of Points Are Not as Deep as Conjectured." 14 Nov 2026. https://arxiv.org/abs/2611.19600v1.Ramos, P. and Viaña, R. "Depth of Segments and Circles through Points Enclosing Many Points: A Note." Comput. Geom. 42, 338-341, 2009. https://doi.org/10.1016/j.comgeo.2008.07.001.

Cite this as:

Weisstein, Eric W. "Plane Depth." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PlaneDepth.html

Subject classifications