WorksMathematics
The Deepest Pairs of Points Are Not as Deep as Conjectured
Abstract
Given any finite set of points in , Neumann-Lara and Urrutia \cite{NLUr88} proved in 1988 that there is always a pair such that every circle through the two points encloses a positive fraction of all points. While Edelsbrunner et al.\ \cite{EHSS89} showed that the fraction is at least \sfrac{1}{2} - \sfrac{1}{\sqrt{12}} = 0.211\ldots, Urrutia \cite{Urr02} conjectured that the constant \sfrac{1}{4} = 0.25 in the upper bound proved by Hayward, Rappaport and Wenger \cite{HRW89} is best possible. We disprove this conjecture by lowering the constant to \sfrac{3}{14} = 0.214\ldots. The new bound also disproves a related conjecture by Ramos and Viaña \cite{RaVi09} on finite sets in convex position in . Finally, we generalize the latter extremal question to finite sets in possibly non-convex position, for which we prove the first linear lower bound, with constant \sfrac{(2-\sqrt{2})}{6} = 0.097\ldots.
Introduction
Given a generic set of points in , each pair defines a pencil of circles that pass through them, and we define the circle depth of the pair as the minimum—over the circles in this pencil—of the number of points of strictly inside the circle. Denoting this number , we study the minimum depth we find in every generic set of points in the plane,
For non-generic point sets, the appropriate definition of the circle depth of a pair is the minimum—over all circles passing through and $v—of the number of other points strictly inside or on the circle. With this modification, all bounds extend from generic to possibly non-generic sets of the same number of points.
Mapping each point to , we get a set of points on the unit paraboloid in , and the circle depth of is the minimum—over all non-vertical planes that pass through and —of the number of points in strictly below the plane. This motivates the following related but different concept. Given a generic set of points in , each pair defines a cyclic pencil of planes passing through them, and we define the plane depth of the pair as the minimum—over all planes in this pencil—of the number of points strictly on one side of this plane. Denoting this number , we study the minimum depth in every generic set of points in convex position in ,
Observe that the plane depth of a pair is the number of points that need to be removed before the pair spans an edge of the convex hull. A convex polytope is 2-neighborly if every pair of vertices spans an edge, and in the tetrahedron is the only such polytope with non-zero volume. The minimum plane depth, over all vertex pairs, can thus be interpreted as a combinatorial measure of how close a convex polytope is to being 2-neighborly.
We have , and there are two reasons why the minmax plane depth may be smaller than the minmax circle depth. The first is that we maximize over possibly higher numbers in than in : if , then because the circle depth effectively minimizes over the sides below the planes, while the plane depth minimizes over both sides. The second reason is that we minimize over a smaller family of sets in than in : every finite set in lifts to a set in convex position in , but not every set in convex position in is the lifted image of a set in .
Prior work. The historically older of the two questions is about the circle depth. In 1988, Neumann-Lara and Urrutia [15] introduced and proved by showing that the average circle depth, over all pairs , is at least as much. It was clear that the constant is not best possible, so they asked for improved bounds. A year later, Hayward [11] improved the lower bound to , and Hayward, Rappaport and Wenger [12] proved . In the same year, Edelsbrunner, Hasan, Seidel and Shen [10] further improved the lower bound to , which is the best known lower bound today. In 2002, Urrutia [21] put his trust into the upper bound by conjecturing that is the correct constant.
In 2009, Ramos and Viaña [17] proved using a result on counting -facets of finite sets of points in convex position in . Since , this furnishes an alternative proof of the lower bound for the circle depth in [10]. Ramos and Viaña also put their trust in the upper bound by conjecturing that the number of pairs with plane depth is at most , which would imply .
Further afield, there are extensions beyond two dimensions and different notions of depth. Already in 1989, Bárány and coauthors proved that for any finite set of points in there are points such that every -sphere that encloses these points also encloses a positive fraction of all points [6]. For example, in any finite set contains three such points, and indeed two are not sufficient since any two points of a finite set on the moment curve can be separated from the others by a sphere. The current best lower bound for the constant is proved in [19], in which is Euler’s number, which is unlikely to be tight. Finally, we mention extensions to ellipsoids instead of spheres [5], to shapes different from circles and ellipses in the plane [20], and to colored point sets [8, 16]. In addition, there are specializations of the circle depth question to point sets in convex position [12] and to the smallest sphere in every pencil [3].
Our results. We disprove both conjectures, the one by Urrutia [21] on the circle depth, and the one of Ramos and Viaña [17] on the plane depth. Specifically, we show , which implies the same upper bound for . We do this in two steps, first proving using an initial set of just 9 points, and then expanding to 28 points, while noting that
Although our upper bounds for the two notions of depth are the same, and also the current best lower bound is the same for both, we have no evidence that the two functions are not different.
Outline. Section 2 presents the first construction in , which proves that is an upper bound for the minmax circle depth. Section 3 suggests a direction to further improve this upper bound. Section 4 takes one step in the suggested direction and proves that is an upper bound for the minmax plane depth. Section 5 shows that this upper bound also applies to the circle depth question. Section 6 considers a related questions about the plane depth for not necessarily convex sets in and proves a linear lower bound for the minmax depth. Section 7 discusses extensions of our results to related combinatorial questions.
Statement of AI use. The authors of this paper used AI for some of the constructions in this paper. In particular, the 28-point constructions in Sections 4 and 5 (together with the accompanying directed arcs in Figure 5) were found using ChatGPT and Claude. An original 9-point construction with circle depth at most 1 was found using ChatGPT but the construction given in Section 2.2 with the 3-fold rotational symmetry was developed by the authors. The generalizations from 9 and 28 to and points in Sections 2.3, 4.2, and 5.1 require specific sufficient properties from the initial points, which were provided as input to the AI searches of the spatial and planar points sets with 28 points in Sections 4.2 and 5.1, respectively. All examples were independently verified, and all proofs were created and written by the authors.
Figure 5. Left panel: one third of the directed arcs representing the pairs at plane depth 5. The points are arranged like in Table 2, with O at the top, to in the left column, to in the middle columns (labels not shown), and to in the right column. Right panel: the planes passing through points , , and , , constructed for the two arcs with common target , together with a sketch of the circular arc on which the points substituted for are placed.
Acknowledgments. The second author was partially supported by the Simons Foundation and the UTRGV SMSS Research Collaboration Enhancement Program.
Construction in the Plane
This section gives a proof of our new upper bound for the minmax circle depth. Specifically, we prove the
Theorem 2.1. , for every positive integer .
The main step in the argument is the establishment of nine points that imply . We begin with a counting argument in § 2.1 that narrows down the possibilities, continue with a description of the nine points in § 2.2, and generalize to in § 2.3 while pointing out that for this generalization, it is not enough to have a set of nine points witnessing .
Counting Edges
Given a set of nine points in , denoted , we have pairs of points. We argue it is possible that each pair has a circle passing through its two points such that at most one of the remaining seven points lies strictly inside the circle, and all other points lie outside the circle.
If there is no point inside the circle, then the pair is an edge of the Delaunay triangulation, denoted ; see [9]. Let be the number of points that are vertices of the convex hull of , and recall that has edges. We have , so the number of edges is at most 21, just like for the set of points illustrated in Figure 1.
Figure 1. The Delaunay triangulation of 9 points, 3 of which are vertices of the convex hull. It contains edges and triangles, not counting the outside region.
Assuming , we have 21 pairs or edges whose circle depth is 0, so we need the remaining pairs to have circle depth 1. To see whether this is possible, we ask for each point how many circles passing through two of the other points enclose but no additional points of . Equivalently, we can remove from the Delaunay triangulation and ask how many new edges appear in . Assuming there are only 3 vertices on the convex hull after removing , has 3 fewer edges than , so if the degree of is , then we see new edges. The sum of degrees of the vertices in is twice the number of edges, which is 42. Each degree is at least 3, so in total we see at most new edges, and it is less than 15 if one or more edges appear more than once as we remove points from the Delaunay triangulation. In words, there is no combinatorial obstacle to the existence of 9 points with the desired properties.
Nine Points
Encouraged by the absence of a contradiction in our counting exercise, we proceed to exhibiting a set of nine points such that every pair has circle depth 0 or 1. To begin the construction, we draw three lines that support the sides of an equilateral triangle, and three circles centered at the barycenter of the triangle: one passing through the three vertices of the triangle, one slightly smaller so it crosses each side of the triangle in two points, and one larger so it encloses the triangle; see Figure 2. To name the points, we let , , be the vertices of the triangle, , , three of the six crossings of the small circle with the sides, and , , three of the six crossings of the big circle with the lines that support the sides. As shown in the figure, we pick , on the line that passes through and , we pick , on the line that passes through and , and we pick , on the line that passes through and .
Figure 2. 9 points with 4 each on three straight lines and 3 each on the three blue concentric circles so that the configuration enjoys a 3-fold rotational symmetry. The additional dotted circles visualize Properties (i) and (ii) of the points.
We make sure that the radii of the circles are chosen such that
(i) lies outside the circle passing through , , which, by the 3-fold rotational symmetry, implies that lies outside the circle passing through , , , and lies outside the circle passing through , , ; see the dotted circular arcs in Figure 2;
(ii) lies outside the circle that passes through and touches the line of in , which, by the 3-fold rotational symmetry, implies that is outside the circle that passes through and touches the line of in , and is outside the circle that passes through and touches the line of in ; see the dotted circles in Figure 2.
Assuming each side of the equilateral triangle has length 1, we get Properties (i) and (ii) if we choose the radii such that is at distance from , and is at distance larger than 1 from .
In spite of the colinearities, the Delaunay triangulation the 9 points is well defined and indeed as shown in Figure 1. To verify we need to show that the circumcircle of every triangle in this triangulation is empty. But this is easy, and it suffices to check 5 of the 13 triangles. In fact, any sufficiently small perturbation of the 9 points has the same Delaunay triangulation combinatorially. To arrive at the final configuration, we move , , by a small angle in a clockwise order on their common circle. This completes the construction of .
We argue that the 15 additional pairs each have circle depth 1; see also Figure 3 for a slightly artistic rendering of these pairs as directed edges, and § 2.3 for the purpose of the directions. For each such pair, we need to verify that there is a circle through the two points that encloses only one of the remaining 7 points.
Figure 3. The edges that do not belong to the Delaunay triangulation of . We draw them as curved arcs for better visualization, and directed to support the extension to points per point of the nine.
: among the pencil of circles that touch the line of in choose the circle that passes through . This circle is well defined because after the small clockwise rotation, no longer lies on this line. Observe that is the only point inside this circle.
: similarly choose the circle that touches the line of in and passes through . is again the only point inside this circle.
: by construction, the circle that passes through , , encloses only ; see Property (i) and Figure 2. We can make the circle slightly smaller while still passing through and so that lies outside this circle.
: choose the circle that touches the line of in and passes through
. By Property (ii), is the only point inside this circle.
(5) : choose the circle that touches the line of in and of in . The only point inside this circle is .
The remaining 10 pairs are symmetric, so the same arguments apply.
Arbitrarily Many Points
Next we extend the upper bound from 9 to points, for any positive integer . We do this by substituting collinear points on a short line segment for each of the original 9 points. Each line segment is centered at the corresponding point, and its direction is chosen with care, as will be explained shortly. Furthermore, all line segments are sufficiently short so that picking one of the points on each, we would get the same configuration as for the original 9 points combinatorially.
It remains to choose the directions, which will be done using the directions of the 15 arcs displayed in Figure 3. Importantly, each of the 9 points is target of at most two directed arcs. Also note that for each arc there is a circle through its endpoints that encloses exactly one of the remaining seven points:
is target of two directed arcs, and the two corresponding circles—which are specified in (2) and (5)—touch each other in ;
is target of two directed arcs, and the two corresponding circles—which are specified in (1) and (4)—touch each other in ;
is target of only one directed arc, and the corresponding circle is specified in (3).
The remaining six points are symmetric so that the above observations about , , generalize to them accordingly.
For each of the original 9 points, we choose the line segment in the direction so it is tangent to the corresponding circles that pass through the point. For we have two corresponding circles, which touch in , so the desired tangent direction works for both, and the same holds for . By the 3-fold rotational symmetry, the directions of the line segments of , , are obtained by rotation through , and those of , , by rotation through .
Proof of Theorem 2.1. We argue that the described configuration of points implies . Consider two of the points, and , and let and be the two original points such that is one of the collinear points substituted for , and is one of the collinear points substituted for . If , then any sufficiently small circle that passes through and possibly encloses a point only if it is among the other points that are substituted for . We can therefore assume .
If and are connected by an edge in the Delaunay triangulation, then there is a circle that passes through and such that all points on the other seven line segments lie outside. The only points that are possibly inside the circle belong to the same line segments as and , of which there are at most .
Otherwise, there is a directed arc—say from to —and there is a circle that passes through and that encloses only one of the remaining seven original points, say . There is also a circle that passes through and and encloses the points substituted for and at most points substituted for . By the choice of the line segment at , none of the points on this line segment lie inside this circle.
In conclusion, we have . To get a bound also for integers not necessarily divisible by 9, we choose a subset of the smallest multiple of 9 that is not smaller than and get , which completes the proof of Theorem 2.1. □
Scouting for Improvements
We ask whether the 9-point configuration introduced in § 2 can be used as a basis to further improve the upper bound for , which is also an upper bound for . To narrow down the possibilities, we focus on the combinatorics of promising configurations and delay the more challenging task of finding geometric realizations until later.
Given a generic set of points in and a positive integer , the object of interest is the order- Voronoi tessellation, denoted . It is a decomposition of into convex regions, each associated with a subset of points such that the region consists of all for which these are the closest points of ; see e.g. [13]. Whenever two regions are separated by a single edge, then the two associated sets of points overlap in points. Let be the points and and associated to the two regions. The pencil of circles that pass through and have their centers on the bisector of and , and whenever the center is interior to the said edge, the circle strictly encloses the points in . We thus associate the edge with the pair , call the pair new in if there are no edges of the first Voronoi tessellations on its bisector, and call it single if it is new and there is no second edge in along its bisector. The new pairs are exactly the pairs at circle depth .
Letting be the number of new pairs in , and the total number of new pairs in the first Voronoi tessellations, we have
as proved in [17] for the more general setting of the plane depth for points in convex position in ; see also equation (10). There are two necessary conditions for this bound to be tight. (I) The number of unbounded regions in the first Voronoi cells is a minimum, and since each such region corresponds to a set of at most points that can be separated from the rest by a straight line, the tight lower bound in [14] applies. (II) Each bisector either contains no edge of the first Voronoi tessellations, or it carries a connected sequence of these edges. The authors believe that these two conditions are also sufficient for (4) to be tight, but this is besides the point.
We are looking for integers and such that the number of pairs defined by the points is exactly equal to the upper bound in (4): . This reduces to a quadratic equation, , and we ask for positive integers and that satisfy this equation; note that for starting from 9 we choose the smaller of the two solutions for . Table 1 lists the first eight integer solutions to this equation. The upper bound in [12] may
| 1 | 2 | 6 | 21 | 77 | 286 | 1066 | 3977 | |
| 4 | 9 | 28 | 99 | 364 | 1353 | 5044 | 18819 |
Table 1. The first eight integer solutions to the quadratic equation derived from (4) while assuming that the upper bound is tight.
be interpreted as a geometric realization of , and the 9-point construction in § 2 as a geometric realization of . Are there geometric realizations of or any of the later solutions? To shed light on this sequence, define as well as and observe that the integer solutions can be enumerated with the following recurrence relations:
for . Turning this into explicit formulas, we get
The ratio over gives the constant in the upper bound. We thus get a sequence of improvements of this constant, which in the limit is
which we recognize as the constant in the current best lower bound for and .
Construction in Space
Following the recipe for 28 points from Section 3, we further lower the constant in the upper bound for to . Specifically, we prove
Theorem 4.1. , for every positive integer .
In Section 4.1, we describe a set of 28 points in convex position such that all pairs have depth at most 5, and in Section 4.2, we replace each of the 28 points by carefully placed nearby points to prove the theorem.
Twenty-eight Points
The convex hull of is displayed in Figure 4, and the coordinates of the points are given in Table 2. One can check through a direct computation that each of the pairs has plane depth 5 or less. The set has a 3-fold rotational symmetry, with the space diagonal as the axis of rotation, and the origin as one of the points in . The numbers of pairs with depth are 78, 69, 66, 57, 54, 54, for , so their sum is , as required. Once we remove the origin from , the remaining 27 points split into 9 clusters of 3 each, and the middle points of the clusters form a 9-point set with each of 36 pairs having plane depth at most 1. Indeed, the 9- and 28-point constructions share a number of features that are deeper than the similar visual appearance.

Figure 4. The convex hull of viewed from along the space diagonal. Similar to the 9-point construction, we see a 3-fold rotational symmetry with the points radiating out from the central point at the origin, which lies on the axis of symmetry.
Table 2. The coordinates of the points in displayed in Figure 4. For easier reading, we arrange the points with the origin first, followed by 3 sets of 9 points each, which radiate out from the origin. The 3-fold rotational symmetry reveals itself by cyclically permuting the coordinates in the first column to obtain the points in the second and the third columns.
Arbitrarily Many Points
The generalization from 28 to arbitrarily many points resembles that in § 2.3. Again, we fix a positive integer and replace each point in with close points to get a configuration of points. Among the original 28 points, there are 54 pairs at plane depth exactly 5. Figure 5 illustrates these pairs by showing 18 of them as directed arcs between the points, whose coordinates are listed in Table 2, while the remaining 36 arcs can be obtained through 3-fold rotational symmetry. The directions of the arc are chosen so that the following three conditions are satisfied:
each point is target (end-point) of exactly two of the 54 arcs, except for point , which is not target of any of the arcs;
for each point in , there is a vector such that the line that passes through and is a support line of ;
for each directed arc from to , there is a unique plane that passes through , , and , and this plane separates the remaining 26 points into 5 points on one side and 21 points on the other side.
In other words, we require that the plane that passes through the points of a pair at depth 5 and the endpoint of the vector attached to the target of the corresponding directed arc witnesses the depth of the pair. We list the arcs shown in the left panel of Figure 5 together with the vectors assigned to their targets, while leaving the verification of the three claimed properties to the diligent reader:
We expand the construction of as follows. Fixing a positive integer, , we replace by points on a small circle with center in the plane , which supports . Every other point is replaced by points near and along the line that passes through and . To finally get the points in convex position, we move the point on this line onto a circle with large radius whose tangent at is the said line; see the right panel of Figure 5. Importantly, the radius of the circle centered at can be chosen arbitrarily small, the radii of the circles passing through the other points in can be chosen arbitrarily large, and the points can be chosen arbitrarily close to the points in they replace.
Proof of Theorem 4.1. Consider a pair, and , of the points, and let and be the corresponding points in . If , then there is a plane that passes through and that separates a subset of the points substituted for and all other points. The plane depth of is thus at most , so we can assume .
If the plane depth of is less than 5, then there is a plane passing through and that has at most $6m - 2$ points on one side: the points each substituted for the at most 4 original points on one side of the plane through and , plus points each substituted form and $E.
If the plane depth of is 5, assume the directed arc that represents the pair goes from to . Then there is a plane that passes through and and is arbitrarily close to that has at most points on one side: the points each substituted for the 5 original points on the side of the plane through and , plus points substituted for . Because the points substituted for lie on a circular arc, none of them lies on that side of the plane. Also note that is possible but is not because none of the directed arcs has as its target.
In conclusion, we have . To get a bound also for integers not necessarily divisible by 28, we choose a subset of the smallest multiple of 28 that is not smaller than and get , which completes the proof of Theorem 4.1.
Ugly Construction in the Plane
In this section, we sketch a set of 28 points in the plane, denoted , which proves and generalizes to prove . We call this set ugly because it does not enjoy the 3-fold rotational symmetry that helps in understanding and .
Twenty-eight Points
The integer coordinates of the 28 points in are listed in Table 3. It is tedious but not difficult to verify that every pair in this set has circle depth at most 5. Moreover, for every positive integer , we can substitute points for each point in such that each pair of the points has circle depth at most . The way this is done is similar to our approach in § 2.3 and § 4.2, so we will be brief.
Table 3. The coordinates of the points in . Since they are integers, we can unambiguously compute the number of points inside each circle passing through three of the points and this way check that each pair indeed has circle depth at most 5.
First we observe that 54 pairs in have circle depth 5, while all other pairs have circle depth less than 5. For each of the 54 pairs, we chose a directed arc from one point to the other in such a way that
each point is target of at most two directed arcs;
whenever a point is the common target of two arcs, say from to and from to , then there is a circle through and and another through and that touch each other at and both strictly enclose only 5 of the points in .
To construct the points, we replace by points near on the line that passes through and separates the two circles. It is also possible that a point is target of only one directed arc, in which case we pick the points near and on the line that passes through and is tangent to a circle of the corresponding pair that strictly encloses only 5 points of .
The argument that every pair in this set of points has circle depth at most is the same as the one used to prove Theorem 2.1, but see also the proof of Theorem 4.1. Finally, for each positive integer , not necessarily divisible by 28, we choose a subset of the smallest multiple of 28 that is not smaller than to get the
Main Theorem. , for every positive integer .
Since , the Main Theorem supersedes Theorem 2.1, and because it also supersedes Theorem 4.1.
Finding Oases in the Desert
While the Main Theorem supersedes the others, we would never have found and its extension to points in if we did not have the opportunity to take the intermediate step of constructing in . Indeed, the plane depth question in is more relaxed for two reasons, and we used each for another intermediate step along the way. To explain, we define
the two-sided circle depth of a pair in a finite set in as the minimum—over all circles passing through the two points—of the number of points strictly inside the circle or the number of points strictly outside the circle, whichever is smaller, and write for the minmax two-sided circle depth for points in general position in ;
the one-sided plane depth of a pair in a finite set in as the minimum—over all non-vertical planes passing through the two points—of the number of points strictly below the plane, and write for the minmax one-sided plane depth for points in general and convex position in .
Clearly and . After establishing as explained in § 4, we have interacted with AI tools to first find 28 points in that imply , then generalize to get , then find 28 points in that imply , and finally generalize to get . Only after this sequence of successes did we find and its extension of points and thus proved the Main Theorem.
Non-convex Position in Space
A natural extension of the depth questions studied in this paper is to points in that are in general but not necessarily convex position. Are there such sets for which the two-sided plane depth of every pair is strictly less than ? Using “depth” short for “two-sided plane depth” in this section, we denote the number of pairs at depth of a set by , and write for the number of pairs at depth at most . With this notation, we have iff .
The Depth of Pairs and Triples
For a triple of points of a generic set , there is a unique plane that passes through the three points, and all other points lie on one (open) side of the plane or the other. Letting and be the number of points on the two sides, we have , and assuming , we say the small side contains points and the large side contains points. Furthermore, we call the depth of the triple. For example, the triples at depth 0 span the triangles of . Note that the depth of the halving triples defined by remain undefined. This is on purpose as these triples play no role in our subsequent analysis.
We mention that the two oriented versions of the triple are also known as -facet and -facet, always counting the points on the positive side of the plane as defined by the orientation of the triple; see e.g. [22]. We use the depth terminology because it makes the connection to the depth of pairs more transparent. To count, for , we write for the number of triples at depth , and for the number of triples at depth at most . Following Ramos and Viaña [17], we observe that
a pair has depth at most iff it belongs to a triple at depth ;
every pair belongs to an even number of triples at any given depth, hence at least two if it belongs to any triple at that depth;1
every triple contains three pairs, and the depth of each of these pairs is at most the depth of the triple.
Hence, we get as an upper bound for the number of pairs at depth at most . If the points in are in general as well as convex position, then the number of triples at depth , with , depends only on and not on the positions of the points [7, 13]. Writing for this number, we thus get
for points in convex position, which the authors of this paper – given the findings here – now believe is tight, contrary to the conjectures by Ramos and Viaña [17]. We note that (10) is tight iff every pair at depth at most belongs to exactly two triples at depth ; compare with condition (II) in the footnote in Section 3. If the points are not in convex position, then may exceed , so we cannot conclude that (10) holds beyond points in convex position.
Upper bounds for have been a topic of investigation for decades, with the current best upper bound being from 2001 [18]. It follows that for , which guarantees pairs at depth . We will improve on this bound in Section 6.4, showing the existence of a pair at linear depth, however with a constant short of the bound known for in convex position. Nevertheless, we cannot rule out that the bound in (10) holds for all generic sets of points in , which would immediately generalize the depth bound for convex position to all generic sets in . Indeed, we show also for sets in possibly non-convex position in § 6.2, and we construct sets in convex position showing that this bound is tight in § 6.3.
Upper Bound
For the proof of , let be the extreme points in , and write for the non-extreme or inner points. For , we consider the set of points whose removal makes a vertex of the convex hull. Formally,
in which (12) is not difficult to prove and will be useful shortly. As an aside, we mention that there are always four extreme points that contain in their convex hull, by Carathéodory’s Theorem, so , and there are at least two such quadruples of points if , so whenever .
Lemma 6.1. The number of pairs at two-sided plane depth at most 1 in a set of points in general position is at most .
Proof. A pair is at depth 0 iff its endpoints span an edge of the convex hull, which implies that their number is . The pairs at depth 1 are those that appear as edges of the convex hull after one of the extreme points is removed. The number of pairs at depth exactly 1 is therefore
in which is the degree of in the edge graph of the convex hull of , is the number of inner points that become vertices of the convex hull upon the removal of , and is the over-count; that is: the sum—over all pairs at depth 1—of one less than the number of times the pair appears. We can therefore write the number of pairs at depth at most 1 as
in which is the number of times appears as a vertex of the convex hull after the removal of a single extreme point, and is the accumulated over-count for the pairs at depth 1 that connect to extreme points of . We get (16) from (15) by observing and as we ignore the over-count for pairs connecting two extreme points or two inner points.
The goal is now to show for all . Suppose appears as a vertex on the convex hull upon the removal of , and let be the set of neighbors of on the convex hull. Hence, is in the convex hull of , which by (12) implies . In other words, if , then every pair at depth 1 that connects to an extreme point appears times on the convex hull, so these pairs are over-counted times. Hence, and therefore , which completes the argument.
Lower Bound
We will see shortly that the upper bound in Lemma 6.1 is tight, and indeed there are sets in convex position that have this many pairs. One example are the nine points in Table 4, for which there are pairs at depth 0 or 1, and we leave the verification of this claim to the diligent reader. Unlike the lifting of the 9-point example in Section 2, there is a degree-3 vertex in its convex hull, which will be instrumental in the construction below.
| Degree | A | B | C |
| degree 5 | |||
| degree 6 | |||
| degree 3 |
Table 4. Nine points in with 3-fold symmetry. The convex hull is a combinatorial octahedron with three rather low triangular pyramids glued on three pairwise non-adjacent triangular faces. The degree sequence of the vertices in the edge graph of the convex hull is , and all pairs have depth at most 1.
Lemma 6.2. For every there is a set of points in general and convex position in with pairs at two-sided plane depth at most 1.
Proof. The example of points in Table 4 is the basis of this proof by induction. Denote this set and recall that it has the required number of 36 pairs at depth at most 1, namely 21 pairs that span edges of the convex hull, and an additional 15 pairs at depth 1. Importantly, the convex hull of has a degree-3 vertex, which is a property we maintain inductively for all sets.
Let be a degree-3 vertex and the neighbors of in the edge graph of , so is a triple at depth 1 of . We construct by carefully adding a new point, , close to , such that
all pairs at depth at most 1 in remain pairs at depth at most 1 in ;
belongs to at least 6 (new) pairs at depth at most 1 in .
We thus increase the number of pairs at depth at most 1 by at least 6 in each step, which implies that has at least such pairs, but by Lemma 6.1 there cannot be more such pairs, which implies that claimed number.
The remainder of this proof shows that a point can be added to such that Properties 1 and 2 are satisfied and, furthermore, has degree 3 in the edge graph of , so it can act as the vertex in the next iteration. Letting be the mentioned points in , and the third vertex of the second triangle incident to the edge in , we place such that it obeys the following conditions:
is extreme in , and are the neighbors of in the edge graph of ;
is sufficiently close to , so there are no three points in whose plane separates from ;
the plane spanned by has at least two points of on each side.
Observe that Condition (i) is equivalent to being on the small side of the triple of and on the large sides of the triples , , of . Also note that Condition (iii) is equivalent to lying on the large sides of the two triples that contain the edge of . This is feasible because implies that each edge of belongs to exactly two triples at depth 1. Next we argue that Conditions (i), (ii), (iii) imply Properties 1 and 2.
Property 1: since has degree 3, the only depth-1 triple of that has on its small side is , and since is sufficiently close to , is also the only depth-1 triple of that has on its small side. Hence, is the only depth-1 triple of whose depth increases upon adding . Every pair of that belongs to a depth-1 triple of belongs to at least two depth-1 triples of and therefore to at least one depth-1 triple of . Since a pair has depth at most 1 iff it belongs to a triple at depth 1, we conclude that all pairs that have depth at most 1 in have depth at most 1 in .
Property 2: to see that belongs to at least six pairs at depth at most 1 in , note that three of these pairs span the edges , , in . One more pair is , which is an edge of as is sufficiently close to . Finally, we rotate a plane about the edge , which it contains. Starting when the plane supports —so there are no points on its small side—it passes through the other points in sequence, first and last . Letting be the second and the second to the last, this identifies and as depth-1 triples of . We have because , and , by Condition (iii). Hence, and are the required two additional pairs at depth at most 1. □
Deep Pairs for Possibly Non-convex Sets
We finally prove the linear upper bound on the number of pairs at depth at most , which implies a linear lower bound on the minmax depth of the pairs. We will make use of the lower and upper bounds for the number of triples at depth at most proved in [2] for and [22] for , respectively:
Theorem 6.3. Let be a set of points in general but not necessarily convex position in . Then
for every . This implies that necessarily contains a pair at two-sided plane depth , in which
Proof. Consider a pair at depth or smaller, and note that it belongs to a positive even number of depth- triples for every with . Therefore, for every integer with , the number of triples with depth between and that contain the pair is at least . It follows that for and ,
in which we use both inequalities in (17) to get (21). Assuming , we choose which gives
The largest value of that satisfies is
as claimed.
We mention that a more careful choice of increases the constant to roughly 0.0981. We do not elaborate on this improvement, since we do not believe that these constants are close to being tight.
Discussion
The work reported in this paper suggests a number of specific questions about the minmax circle and plane depth of finite sets in two and three dimensions. Some of them probe the relationship between the two notions of depth.
The authors of this paper conjecture that the current lower bound constant, , is tight for as well as for . But this does not imply for every positive integer , and indeed the authors tend to believe that the two functions are different for some .
Suppose and are positive integers satisfying ; compare with (4) in Section 3. Is it true that in this case there are points in such that all pairs have plane depth at most ? Assuming such points exist, is it furthermore true that the points can be chosen in convex position? If found correct, this would imply that the constant of the current best lower bound, , is tight for . We verified this conjecture for all relevant pairs with .
It is interesting to see that one step in establishing our results was showing that the complex of triangles at certain depths (usually called -facets), can be a weak pseudomanifold without boundary studied e.g. in [4]. By definition, this is a connected abstract simplicial complex that is pure of dimension 2 in which every edge belongs to exactly two triangles. It is not necessarily a manifold, and two triangulated spheres glued at one or several shared vertices give an example of such a pseudomanifold that is not a manifold.
Letting be points in general and convex position in , the triangles at plane depth , for some , define a connected abstract simplicial complex that satisfies the conditions of such a pseudomanifold, except that an edge may belong to more than two triangles. Indeed, every edge at depth at most belongs to a positive even number of triangles at depth , and every edge of the convex hull is contained in such a triangle, so the complex is connected via the 1-skeleton of the convex hull. The question is whether this geometric construction can satisfy the remaining condition: that each edge belongs to exactly two triangles. Ramos and Viaña [17] conjectured implicitly that beyond the case it cannot. Indeed, their conjectured relation , with the right-hand side smaller than (10) by , excludes the possibility of a weak pseudomanifold for . However, the results in this paper disprove this conjecture as, e.g., the configurations of 9 and 28 points in Sections 2 and 4 furnish examples for and , where, additionally, all pairs are edges of the complex.
References
- [2]O. Aichholzer, J. García, D. Orden and P. Ramos. New results on lower bounds for the number of (≤k)-facets. European Journal of Combinatorics 30 (2009), 568–1574.
- [3]J. Akiyama, Y. Ishigami, M. Urabe and J. Urrutia. On circles containing the maximum number of points. Discrete Math. 151 (1996), 15–18.
- [4]B. Bagchi and B. Datta. A structure theorem for pseudomanifolds. Discrete Math. 168 (1998), 41–60.DOI
- [5]I. Bárány and D.G. Larman. A combinatorial property of points and ellipsoids. Discrete Comput. Geom. 5 (1990), 375–382.DOI
- [6]I. Bárány, J.H. Schmerl, S.J. Sidney and J. Urrutia. A combinatorial result about points and balls in Euclidean space. Discrete Comput. Geom. 4 (1989), 259–262.DOI
- [7]K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4 (1989), 387–421.
- [8]M. Claverol, C. Huelmer and A. Martinez-Moraian. On circles enclosing many points. Discrete Math. 344 (2021), article 112541.arxiv.org/abs/1907.06601
- [9]B. Delaunay. Sur la sphère vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskie i Estestvennykh Nauk 7 (1934), 793–800.
- [10]H. Edelsbrunner, N. Hasan, R. Seidel and X.J. Shen. Circles through two points that always enclose many points. Geometriae Dedicata 32 (1989), 1–12.DOI
- [11]R. Hayward. A note on the circle containment problem. Discrete Comput. Geom. 4 (1989), 263–264.DOI
- [12]R. Hayward, D. Rappaport and R. Wenger. Some extremal results on circles containing points. Discrete Comput. Geom. 4 (1989), 253–258.DOI
- [13]D.-T. Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31 (1982), 478–487.DOI
- [14]L. Lovasz, K. Vestergombi, U. Wagner and E. Welzl. Convex quadrilaterals and k-sets. Contemp. Math. 342 (2004), 139–148.
- [15]V. Neumann-Lara and J. Urrutia. A combinatorial result about points and circles on the plane. Discrete Math. 69 (1988), 173–178.
- [16]M.N. Prodromou. A combinatorial property of points and balls, a colored version. Discrete Comput. Geom. 38 (2007), 641–650.DOI
- [17]P. Ramos and R. Viaña. Depth of segments and circles through points enclosing many points: a note. Comput. Geom. 42 (2009), 338–341.arxiv.org/abs/0803.1088
- [18]M. Sharir, S. Smorodinsky and G. Tardos. An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26 (2001), 195–204.
- [19]S. Smorodinsky, M. Sulovský and U. Wagner. On center regions and balls containing many points. In “Proc. 14th Intl. Comput. Combin. Conf.”, Springer LNCS 5932 (2008), 363–373.DOI
- [20]T. Tuttle. Online Routing and Containment Problems. Ph.D. thesis, Computer Science Department, Carleton University, Ottawa, Ontario, 2026.
- [21]J. Urrutia. Open problems in computational geometry. In “Proc. 5th Latin American Sympos. Theoret. Informatics”, Springer LNCS 2286 (2002), 4–11.
- [22]E. Welzl. Entering and leaving j-facets. Discrete Comput. Geom. 25 (2001), 351–364.DOI



