TOPICS
Search

Circle Depth


The circle depth of a pair of distinct points u,v of a finite plane set X in general position is the minimum number of points of X strictly inside a circle through u and v (Edelsbrunner et al. 1989, 2026). Here general position means that no three points are collinear and no four are concyclic. Write pi_X(u,v) for this depth and define

 Pi(n)=min_(|X|=n)max_(u!=v in X)pi_X(u,v),

with the minimum over such sets. Thus every n-point set has a pair of depth at least Pi(n).

Edelsbrunner et al. (1989) proved the lower bound Pi(n)>=(1/2-1/sqrt(12))n+O(1), where O is big-O notation. Edelsbrunner et al. (2026) constructed sets giving

 Pi(n)<=6[n/28]-1=3/(14)n+O(1).

This disproves the proposed asymptotic coefficient 1/4; the coefficient 1/2-1/sqrt(12) remains below the new upper bound, so the exact asymptotic value is not determined. Their construction starts with 28 points and replaces each with a small cluster. The authors report that ChatGPT and Claude found the 28-point configurations and that they independently verified the examples and wrote the proofs.

For nongeneric point sets, counting the other points on the circle as well as those inside gives the boundary-inclusive version to which these bounds extend. Lifting plane points to the paraboloid x_3=x_1^2+x_2^2 relates circle depth to plane depth.


See also

Circle, Delaunay Triangulation, Plane Depth

Explore with Wolfram|Alpha

References

Edelsbrunner, H.; Hasan, N.; Seidel, R.; and Shen, X. J. "Circles through Two Points That Always Enclose Many Points." Geom. Dedicata 32, 1-12, 1989. https://doi.org/10.1007/BF00181432.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.

Cite this as:

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

Subject classifications