The circle depth of a pair of distinct points of a finite plane set
in general position is
the minimum number of points of
strictly inside a circle through
and
(Edelsbrunner et al. 1989, 2026). Here general
position means that no three points are collinear
and no four are concyclic. Write
for this depth and define
with the minimum over such sets. Thus every -point set has a pair of depth at least
.
Edelsbrunner et al. (1989) proved the lower bound , where
is big-O notation. Edelsbrunner
et al. (2026) constructed sets giving
This disproves the proposed asymptotic coefficient ; the coefficient
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 relates circle depth to
plane depth.