betaFeedback

WorksMathematics

The Deepest Pairs of Points Are Not as Deep as Conjectured

Abstract

Given any finite set of points in R2\mathbb{R}^2, 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 R3\mathbb{R}^3. 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 XX of nn points in R2\mathbb{R}^{2}, each pair u,v∈Xu,v \in X 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 XX strictly inside the circle. Denoting this number π(u,v)\pi(u,v), we study the minimum depth we find in every generic set of nn points in the plane,

Π(n)=min⁡∣X∣=nmax⁡u,v∈Xπ(u,v).(1)\Pi(n) = \min_{|X|=n} \max_{u,v\in X} \pi(u,v). \tag*{(1)}

For non-generic point sets, the appropriate definition of the circle depth of a pair u,vu,v is the minimum—over all circles passing through uu 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 u∈Xu \in X to u′=(u,∥u∥2)u' = (u, \lVert u\rVert^{2}), we get a set X′X' of nn points on the unit paraboloid in R3\mathbb{R}^{3}, and the circle depth of u,vu,v is the minimum—over all non-vertical planes that pass through u′u' and v′v'—of the number of points in X′X' strictly below the plane. This motivates the following related but different concept. Given a generic set YY of nn points in R3\mathbb{R}^3, each pair a,b∈Ya,b \in Y 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 ψ(a,b)\psi(a,b), we study the minimum depth in every generic set of nn points in convex position in R3\mathbb{R}^3,

Ψ(n)=min⁡∣Y∣=nmax⁡a,b∈Yψ(a,b).(2)\Psi(n) = \min_{|Y|=n}\max_{a,b\in Y}\psi(a,b). \tag*{(2)}

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 R3\mathbb{R}^3 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 Ψ(n)≤Π(n)\Psi(n) \leq\Pi(n), 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 R2\mathbb{R}^2 than in R3\mathbb{R}^3: if Y=X′Y=X', then π(u,v)≥ψ(u′,v′)\pi(u,v) \geq\psi(u',v') 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 R2\mathbb{R}^2 than in R3\mathbb{R}^3: every finite set in R2\mathbb{R}^2 lifts to a set in convex position in R3\mathbb{R}^3, but not every set in convex position in R3\mathbb{R}^3 is the lifted image of a set in R2\mathbb{R}^2.

Prior work. The historically older of the two questions is about the circle depth. In 1988, Neumann-Lara and Urrutia [15] introduced Π(n)\Pi(n) and proved Π(n)≥⌈(n−2)/60⌉\Pi(n) \geq\lceil(n-2)/60\rceil by showing that the average circle depth, over all pairs u,v∈Xu,v \in X, is at least as much. It was clear that the constant 1/601/60 is not best possible, so they asked for improved bounds. A year later, Hayward [11] improved the lower bound to Π(n)≥⌈5(n−2)/84⌉\Pi(n) \geq\lceil5(n-2)/84\rceil, and Hayward, Rappaport and Wenger [12] proved Π(n)≤⌈n/4⌉+1\Pi(n) \leq\lceil n/4\rceil+ 1. In the same year, Edelsbrunner, Hasan, Seidel and Shen [10] further improved the lower bound to Π(n)≥(1/2−1/12)n+O(1)\Pi(n) \geq(1/2 - 1/\sqrt{12})n + O(1), which is the best known lower bound today. In 2002, Urrutia [21] put his trust into the upper bound by conjecturing that 1/41/4 is the correct constant.

In 2009, Ramos and Viaña [17] proved Ψ(n)≥(1/2−1/12)n+O(1)\Psi(n) \geq(1/2 - 1/\sqrt{12})n + O(1) using a result on counting jj-facets of finite sets of points in convex position in R3\mathbb{R}^3. Since Ψ(n)≤Π(n)\Psi(n) \leq\Pi(n), 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 jj is at most 3n−8j−63n-8j-6, which would imply Ψ(n)≥⌈n/4⌉−1\Psi(n) \geq\lceil n/4\rceil- 1.

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 Rd\mathbb{R}^d there are ⌊12(d+3)⌋\lfloor\frac{1}{2}(d+3)\rfloor points such that every (d−1)(d-1)-sphere that encloses these points also encloses a positive fraction of all points [6]. For example, in R3\mathbb{R}^{3} 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 45ed3\frac{4}{5}ed^{3} proved in [19], in which e=2.718…e=2.718\ldots 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 Π(n)≤3n14+O(1)\Pi(n) \le\frac{3n}{14} + O(1), which implies the same upper bound for Ψ(n)\Psi(n). We do this in two steps, first proving Π(n)≤2n9+O(1)\Pi(n) \le\frac{2n}{9} + O(1) using an initial set of just 9 points, and then expanding to 28 points, while noting that

12−112=0.211…<314=0.214…<29=0.222…<14=0.25.(3)\frac{1}{2}-\frac{1}{\sqrt{12}}=0.211\ldots<\frac{3}{14}=0.214\ldots<\frac{2}{9}=0.222\ldots<\frac{1}{4}=0.25. \tag*{(3)}

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 R2\mathbb{R}^{2}, which proves that 2n9+O(1)\frac{2n}{9}+O(1) 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 3n14+O(1)\frac{3n}{14}+O(1) 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 R3\mathbb{R}^{3} 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 9m9m and 28m28m 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, A1A_1 to A9A_9 in the left column, B1B_1 to B9B_9 in the middle columns (labels not shown), and C1C_1 to C9C_9 in the right column. Right panel: the planes passing through points AiA_i, BjB_j, Bj+v(Bj)B_j + v(B_j) and CkC_k, BjB_j, Bj+v(Bj)B_j + v(B_j) constructed for the two arcs with common target BjB_j, together with a sketch of the circular arc on which the points substituted for BjB_j 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. Π(n)≤2⌈n/9⌉−1\Pi(n) \le2\lceil n/9\rceil- 1, for every positive integer nn.

The main step in the argument is the establishment of nine points that imply Π(9)≤1\Pi(9) \le1. 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 Π(9m)≤2m−1\Pi(9m) \le2m-1 in § 2.3 while pointing out that for this generalization, it is not enough to have a set of nine points witnessing Π(9)≤1\Pi(9) \le1.

Counting Edges

Given a set of nine points in R2\mathbb{R}^{2}, denoted X9X_9, we have (92)=36\binom{9}{2} = 36 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 Del⁡(X9)\operatorname{Del}(X_9); see [9]. Let h1h_1 be the number of points that are vertices of the convex hull of X9X_9, and recall that Del⁡(X9)\operatorname{Del}(X_9) has 3⋅9−h1−33 \cdot9 - h_1 - 3 edges. We have h1≥3h_1 \ge3, 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 3⋅9−6=213 \cdot9 - 6 = 21 edges and 2⋅9−5=132 \cdot9 - 5 = 13 triangles, not counting the outside region.

Assuming h1=3h_1 = 3, we have 21 pairs or edges whose circle depth is 0, so we need the remaining 36−21=1536 - 21 = 15 pairs to have circle depth 1. To see whether this is possible, we ask for each point u∈X9u \in X_9 how many circles passing through two of the other points enclose uu but no additional points of X9X_9. Equivalently, we can remove uu from the Delaunay triangulation and ask how many new edges appear in Del⁡(X9∖{u})\operatorname{Del}(X_9 \setminus\{u\}). Assuming there are only 3 vertices on the convex hull after removing uu, Del⁡(X9∖{u})\operatorname{Del}(X_9 \setminus\{u\}) has 3 fewer edges than Del⁡(X9)\operatorname{Del}(X_9), so if the degree of uu is kk, then we see k−3k - 3 new edges. The sum of degrees of the vertices in Del⁡(X9)\operatorname{Del}(X_9) is twice the number of edges, which is 42. Each degree is at least 3, so in total we see at most 42−9⋅3=1542 - 9 \cdot3 = 15 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 X9⊆R2X_9 \subseteq\mathbb{R}^{2} 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 AA, BB, CC be the vertices of the triangle, A′A', B′B', C′C' three of the six crossings of the small circle with the sides, and A′′A'', B′′B'', C′′C'' three of the six crossings of the big circle with the lines that support the sides. As shown in the figure, we pick A′A', A′′A'' on the line that passes through AA and BB, we pick B′B', B′′B'' on the line that passes through BB and CC, and we pick C′C', C′′C'' on the line that passes through CC and AA.

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) A′A' lies outside the circle passing through A′′A'', B′B', C′′C'' which, by the 3-fold rotational symmetry, implies that B′B' lies outside the circle passing through B′′B'', C′C', A′′A'', and C′C' lies outside the circle passing through C′′C'', A′A', B′′B''; see the dotted circular arcs in Figure 2;

  • (ii) B′B' lies outside the circle that passes through CC and touches the line of A′A' in A′A', which, by the 3-fold rotational symmetry, implies that C′C' is outside the circle that passes through AA and touches the line of B′B' in B′B', and A′A' is outside the circle that passes through BB and touches the line of C′C' in C′C'; 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 A′A' is at distance 14\frac{1}{4} from AA, and A′′A'' is at distance larger than 1 from BB.

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 A′′A^{\prime\prime}, B′′B^{\prime\prime}, C′′C^{\prime\prime} by a small angle in a clockwise order on their common circle. This completes the construction of X9X_9.

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 X9X_9. We draw them as curved arcs for better visualization, and directed to support the extension to mm points per point of the nine.

  1. A′′A′A^{\prime\prime}A^{\prime}: among the pencil of circles that touch the line of A′A^{\prime} in A′A^{\prime} choose the circle that passes through A′′A^{\prime\prime}. This circle is well defined because after the small clockwise rotation, A′′A^{\prime\prime} no longer lies on this line. Observe that C′′C^{\prime\prime} is the only point inside this circle.

  1. A′′AA^{\prime\prime}A: similarly choose the circle that touches the line of A′A^{\prime} in AA and passes through A′′A^{\prime\prime}. C′′C^{\prime\prime} is again the only point inside this circle.

  1. C′A′′C^{\prime}A^{\prime\prime}: by construction, the circle that passes through A′′A^{\prime\prime}, C′C^{\prime}, B′′B^{\prime\prime} encloses only CC; see Property (i) and Figure 2. We can make the circle slightly smaller while still passing through A′′A^{\prime\prime} and C′C^{\prime} so that B′′B^{\prime\prime} lies outside this circle.

  1. CA′CA^{\prime}: choose the circle that touches the line of A′A^{\prime} in A′A^{\prime} and passes through

CC. By Property (ii), C′C' is the only point inside this circle.

(5) CACA: choose the circle that touches the line of A′A' in AA and of B′B' in CC. The only point inside this circle is C′C'.

The remaining 10 pairs are symmetric, so the same arguments apply.

Arbitrarily Many Points

Next we extend the upper bound from 9 to nn points, for any positive integer nn. We do this by substituting mm 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 mm 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:

  • AA is target of two directed arcs, and the two corresponding circles—which are specified in (2) and (5)—touch each other in AA;

  • A′A' is target of two directed arcs, and the two corresponding circles—which are specified in (1) and (4)—touch each other in A′A';

  • A′′A'' 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 AA, A′A', A′′A'' 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 AA we have two corresponding circles, which touch in AA, so the desired tangent direction works for both, and the same holds for A′A'. By the 3-fold rotational symmetry, the directions of the line segments of BB, B′B', B′′B'' are obtained by rotation through 120∘120^\circ, and those of CC, C′C', C′′C'' by rotation through 240∘240^\circ.

Proof of Theorem 2.1. We argue that the described configuration of 9m9m points implies Π(9m)≤2m−1\Pi(9m) \le2m - 1. Consider two of the 9m9m points, dd and ee, and let DD and EE be the two original points such that dd is one of the mm collinear points substituted for DD, and ee is one of the mm collinear points substituted for EE. If D=ED = E, then any sufficiently small circle that passes through dd and ee possibly encloses a point only if it is among the other m−2m - 2 points that are substituted for DD. We can therefore assume D≠ED \ne E.

  • If DD and EE are connected by an edge in the Delaunay triangulation, then there is a circle that passes through dd and ee 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 dd and ee, of which there are at most 2m−22m - 2.

  • Otherwise, there is a directed arc—say from DD to EE—and there is a circle that passes through DD and EE that encloses only one of the remaining seven original points, say FF. There is also a circle that passes through dd and ee and encloses the mm points substituted for FF and at most m−1m - 1 points substituted for DD. By the choice of the line segment at EE, none of the mm points on this line segment lie inside this circle.

In conclusion, we have Π(9m)≤2m−1\Pi(9m) \le2m - 1. To get a bound also for integers nn not necessarily divisible by 9, we choose a subset of the smallest multiple of 9 that is not smaller than nn and get Π(n)≤2⌈n/9⌉−1\Pi(n) \le2\lceil n/9\rceil- 1, 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 Π(n)\Pi(n), which is also an upper bound for Ψ(n)\Psi(n). 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 XX of nn points in R2\mathbb{R}^{2} and a positive integer k<n2k < \frac{n}{2}, the object of interest is the order-kk Voronoi tessellation, denoted Vor⁡k(X)\operatorname{Vor}_{k}(X). It is a decomposition of R2\mathbb{R}^{2} into convex regions, each associated with a subset of kk points such that the region consists of all x∈R2x \in\mathbb{R}^{2} for which these are the kk closest points of XX; see e.g. [13]. Whenever two regions are separated by a single edge, then the two associated sets of kk points overlap in k−1k-1 points. Let AA be the k−1k-1 points and A∪{u}A \cup\{u\} and A∪{v}A \cup\{v\} associated to the two regions. The pencil of circles that pass through uu and vv have their centers on the bisector of uu and vv, and whenever the center is interior to the said edge, the circle strictly encloses the points in AA. We thus associate the edge with the pair {u,v}⊆X\{u,v\} \subseteq X, call the pair new in Vor⁡k(X)\operatorname{Vor}_{k}(X) if there are no edges of the first k−1k-1 Voronoi tessellations on its bisector, and call it single if it is new and there is no second edge in Vor⁡k(X)\operatorname{Vor}_{k}(X) along its bisector. The new pairs are exactly the pairs at circle depth k−1k-1.

Letting dj−1d_{j-1} be the number of new pairs in Vor⁡j(X)\operatorname{Vor}_{j}(X), and Dk−1D_{k-1} the total number of new pairs in the first kk Voronoi tessellations, we have

Dk−1=∑j=1kdj−1≤3kn−3k(k+1)(4)D_{k-1} = \sum_{j=1}^{k} d_{j-1} \le3kn - 3k(k+1) \tag*{(4)}

as proved in [17] for the more general setting of the plane depth for points in convex position in R3\mathbb{R}^{3}; see also equation (10). There are two necessary conditions for this bound to be tight. (I) The number of unbounded regions in the first kk Voronoi cells is a minimum, and since each such region corresponds to a set of at most kk 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 kk 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 nn and kk such that the number of pairs defined by the nn points is exactly equal to the upper bound in (4): (n2)=3kn−3k(k+1)\binom{n}{2} = 3kn - 3k(k+1). This reduces to a quadratic equation, n2−(1+6k)n+6(k2+k)=0n^{2} - (1+6k)n + 6(k^{2}+k) = 0, and we ask for positive integers kk and nn that satisfy this equation; note that for nn starting from 9 we choose the smaller of the two solutions for kk. Table 1 lists the first eight integer solutions to this equation. The upper bound in [12] may

kk126217728610663977
nn4928993641353504418819

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 (1,4)(1,4), and the 9-point construction in § 2 as a geometric realization of (2,9)(2,9). Are there geometric realizations of (6,28)(6,28) or any of the later solutions? To shed light on this sequence, define (k−1,n−1)=(2,4)(k_{-1},n_{-1}) = (2,4) as well as (k0,n0)=(1,3)(k_{0},n_{0}) = (1,3) and observe that the integer solutions can be enumerated with the following recurrence relations:

kt=4kt−1−kt−2−1;(5)k_t = 4k_{t-1} - k_{t-2} - 1; \tag*{(5)}
nt=4nt−1−nt−2−4,(6)n_t = 4n_{t-1} - n_{t-2} - 4, \tag*{(6)}

for t≥1t \ge1. Turning this into explicit formulas, we get

kt=112[(3−3)(2+3)t+(3+3)(2−3)t]+12;(7)k_t = \frac{1}{12}\left[(3-\sqrt{3})(2+\sqrt{3})^t + (3+\sqrt{3})(2-\sqrt{3})^t\right] + \frac{1}{2}; \tag*{(7)}
nt=12[(2+3)t+(2−3)t]+2.(8)n_t = \frac{1}{2}\left[(2+\sqrt{3})^t + (2-\sqrt{3})^t\right] + 2. \tag*{(8)}

The ratio ktk_t over ntn_t gives the constant in the upper bound. We thus get a sequence of improvements of this constant, which in the limit is

lim⁡t→∞ktnt=112(3−3)(2+3)t12(2+3)t=3−36=12−112=0.211…,(9)\lim_{t\to\infty}\frac{k_t}{n_t} = \frac{\frac{1}{12}(3-\sqrt{3})(2+\sqrt{3})^t}{\frac{1}{2}(2+\sqrt{3})^t} = \frac{3-\sqrt{3}}{6} = \frac{1}{2} - \frac{1}{\sqrt{12}} = 0.211\ldots, \tag*{(9)}

which we recognize as the constant in the current best lower bound for Π(n)\Pi(n) and Ψ(n)\Psi(n).

Construction in Space

Following the recipe for 28 points from Section 3, we further lower the constant in the upper bound for Ψ(n)\Psi(n) to 3/143/14. Specifically, we prove

Theorem 4.1. Ψ(n)≤6⌈n/28⌉−1\Psi(n) \le6\lceil n/28\rceil- 1, for every positive integer nn.

In Section 4.1, we describe a set Y28Y_{28} of 28 points in convex position such that all (282)=378\binom{28}{2} = 378 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 Y28Y_{28} 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 (282)=378\binom{28}{2} = 378 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 Y28Y_{28}. The numbers of pairs with depth jj are 78, 69, 66, 57, 54, 54, for j=0,1,2,3,4,5j = 0,1,2,3,4,5, so their sum is (282)=378\binom{28}{2} = 378, as required. Once we remove the origin from Y28Y_{28}, 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.

The convex hull of $Y_{28}$ viewed from along the space diagonal

Figure 4. The convex hull of Y28Y_{28} 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.

O=(0,0,0)O=(0,0,0)
A1=(4 241,−3 042,−872)A_1=(4\,241,-3\,042,-872)B1=(−872,4 241,−3 042)B_1=(-872,4\,241,-3\,042)C1=(−3 042,−872,4 241)C_1=(-3\,042,-872,4\,241)
A2=(5 687,−2 921,−1 374)A_2=(5\,687,-2\,921,-1\,374)B2=(−1 374,5 687,−2 921)B_2=(-1\,374,5\,687,-2\,921)C2=(−2 921,−1 374,5 687)C_2=(-2\,921,-1\,374,5\,687)
A3=(6 590,−2 839,−1 805)A_3=(6\,590,-2\,839,-1\,805)B3=(−1 805,6 590,−2 839)B_3=(-1\,805,6\,590,-2\,839)C3=(−2 839,−1 805,6 590)C_3=(-2\,839,-1\,805,6\,590)
A4=(16 681,2 985,−191)A_4=(16\,681,2\,985,-191)B4=(−191,16 681,2 985)B_4=(-191,16\,681,2\,985)C4=(2 985,−191,16 681)C_4=(2\,985,-191,16\,681)
A5=(19 502,2 872,592)A_5=(19\,502,2\,872,592)B5=(592,19 502,2 872)B_5=(592,19\,502,2\,872)C5=(2 872,592,19 502)C_5=(2\,872,592,19\,502)
A6=(20 783,2 779,1 264)A_6=(20\,783,2\,779,1\,264)B6=(1 264,20 783,2 779)B_6=(1\,264,20\,783,2\,779)C6=(2 779,1 264,20 783)C_6=(2\,779,1\,264,20\,783)
A7=(23 541,2 568,2 863)A_7=(23\,541,2\,568,2\,863)B7=(2 863,23 541,2 568)B_7=(2\,863,23\,541,2\,568)C7=(2 568,2 863,23 541)C_7=(2\,568,2\,863,23\,541)
A8=(23 510,2 534,3 409)A_8=(23\,510,2\,534,3\,409)B8=(3 409,23 510,2 534)B_8=(3\,409,23\,510,2\,534)C8=(2 534,3 409,23 510)C_8=(2\,534,3\,409,23\,510)
A9=(23 552,2 546,3 233)A_9=(23\,552,2\,546,3\,233)B9=(3 233,23 552,2 546)B_9=(3\,233,23\,552,2\,546)C9=(2 546,3 233,23 552)C_9=(2\,546,3\,233,23\,552)

Table 2. The coordinates of the points in Y28Y_{28} 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 mm and replace each point in Y28Y_{28} with mm close points to get a configuration of 28m28m 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 OO, which is not target of any of the arcs;

  • for each point E≠OE \ne O in Y28Y_{28}, there is a vector v(E)v(E) such that the line that passes through EE and E+v(E)E+v(E) is a support line of conv⁡(Y28)\operatorname{conv}(Y_{28});

  • for each directed arc from DD to EE, there is a unique plane that passes through DD, EE, and E+v(E)E+v(E), 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:

A8,C8→B1,v(B1)=(8 375,−958 501,−107 703),A_8, C_8 \to B_1,\quad v(B_1) = (8\,375, -958\,501, -107\,703),

A8,C6→B2,v(B2)=(275 321,−823 737,−90 605),A_8, C_6 \to B_2,\quad v(B_2) = (275\,321, -823\,737, -90\,605),

A8,C4→B3,v(B3)=(274 475,−588 570,−55 459),A_8, C_4 \to B_3,\quad v(B_3) = (274\,475, -588\,570, -55\,459),

A2,C4→B4,v(B4)=(82 979,318 088,−19 970),A_2, C_4 \to B_4,\quad v(B_4) = (82\,979, 318\,088, -19\,970),

A2,C4→B5,v(B5)=(−309 232,−789 995,22 889),A_2, C_4 \to B_5,\quad v(B_5) = (-309\,232, -789\,995, 22\,889),

A1,C4→B6,v(B6)=(−479 201,−906 536,104 366),A_1, C_4 \to B_6,\quad v(B_6) = (-479\,201, -906\,536, 104\,366),

A1,C4→B7,v(B7)=(−733 809,−779 927,−12 265),A_1, C_4 \to B_7,\quad v(B_7) = (-733\,809, -779\,927, -12\,265),

0,C4→B8,v(B8)=(−931 316,257 767,251 042),0, C_4 \to B_8,\quad v(B_8) = (-931\,316, 257\,767, 251\,042),

A1,C4→B9,v(B9)=(−488 811,70 348,31 729).A_1, C_4 \to B_9,\quad v(B_9) = (-488\,811, 70\,348, 31\,729).

We expand the construction of Y28Y_{28} as follows. Fixing a positive integer, mm, we replace O∈Y28O \in Y_{28} by mm points on a small circle with center OO in the plane x1+x2+x3=0x_1 + x_2 + x_3 = 0, which supports conv⁡(Y28)\operatorname{conv}(Y_{28}). Every other point E∈Y28E \in Y_{28} is replaced by mm points near EE and along the line that passes through EE and E+v(E)E+v(E). To finally get the 28m28m points in convex position, we move the mm point on this line onto a circle with large radius whose tangent at EE is the said line; see the right panel of Figure 5. Importantly, the radius of the circle centered at OO can be chosen arbitrarily small, the radii of the circles passing through the other points in Y28Y_{28} can be chosen arbitrarily large, and the 28m28m points can be chosen arbitrarily close to the points in Y28Y_{28} they replace.

Proof of Theorem 4.1. Consider a pair, dd and ee, of the 28m28m points, and let DD and EE be the corresponding points in Y28Y_{28}. If D=ED = E, then there is a plane that passes through dd and ee that separates a subset of the points substituted for DD and all other points. The plane depth of d,ed,e is thus at most m−2m - 2, so we can assume D≠ED \ne E.

  • If the plane depth of D,ED,E is less than 5, then there is a plane passing through dd and ee that has at most $6m - 2$ points on one side: the mm points each substituted for the at most 4 original points on one side of the plane through DD and EE, plus m−1m - 1 points each substituted form DD and $E.

  • If the plane depth of D,ED,E is 5, assume the directed arc that represents the pair goes from DD to EE. Then there is a plane that passes through dd and ee and is arbitrarily close to e+v(E)e + v(E) that has at most 6m−16m - 1 points on one side: the mm points each substituted for the 5 original points on the side of the plane through DD and EE, plus m−1m - 1 points substituted for DD. Because the points substituted for EE lie on a circular arc, none of them lies on that side of the plane. Also note that D=OD = O is possible but E=OE = O is not because none of the directed arcs has OO as its target.

In conclusion, we have Ψ(28m)≤6m−1\Psi(28m) \le6m - 1. To get a bound also for integers nn not necessarily divisible by 28, we choose a subset of the smallest multiple of 28 that is not smaller than nn and get Ψ(n)≤6⌈n/28⌉−1\Psi(n) \le6\lceil n/28\rceil- 1, 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 X28X_{28}, which proves Π(28)≤6\Pi(28) \le6 and generalizes to prove Π(n)≤6n/28+O(1)\Pi(n) \le6n/28 + O(1). We call this set ugly because it does not enjoy the 3-fold rotational symmetry that helps in understanding X9X_9 and Y28Y_{28}.

Twenty-eight Points

The integer coordinates of the 28 points in X28X_{28} 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 mm, we can substitute mm points for each point in X28X_{28} such that each pair of the 28m28m points has circle depth at most 6m−16m-1. The way this is done is similar to our approach in § 2.3 and § 4.2, so we will be brief.

(−43541078421308, 73755248213092)(-43541078421308,\ 73755248213092)(−5968358377008, 23899163415198)(-5968358377008,\ 23899163415198)
(−5968475847095, 23898762358671)(-5968475847095,\ 23898762358671)(−5968096105183, 23900058846718)(-5968096105183,\ 23900058846718)
(−65455933408249, 3234461616877)(-65455933408249,\ 3234461616877)(−65455275321073, 3234009382199)(-65455275321073,\ 3234009382199)
(−65455134472388, 3233912600158)(-65455134472388,\ 3233912600158)(−5688953286781, 24862766121693)(-5688953286781,\ 24862766121693)
(−5689281680236, 24861599126288)(-5689281680236,\ 24861599126288)(−5689543505350, 24860668702641)(-5689543505350,\ 24860668702641)
(126911682523964, −136385416994996)(126911682523964,\ -136385416994996)(126911706262116, −136385445365977)(126911706262116,\ -136385445365977)
(126911817559414, −136385578384303)(126911817559414,\ -136385578384303)(123542157536189, −132394276422612)(123542157536189,\ -132394276422612)
(123540861150661, −132392749470942)(123540861150661,\ -132392749470942)(123542030042455, −132394126253617)(123542030042455,\ -132394126253617)
(−29741226526550, −14067115485000)(-29741226526550,\ -14067115485000)(−29741309229663, −14065846231360)(-29741309229663,\ -14065846231360)
(−29741210829441, −14067356335637)(-29741210829441,\ -14067356335637)(−29534668687474, −16333863678967)(-29534668687474,\ -16333863678967)
(−29534887171270, −16332037303774)(-29534887171270,\ -16332037303774)(−29534610561068, −16334349567602)(-29534610561068,\ -16334349567602)
(−59168471584685, 140738966607051)(-59168471584685,\ 140738966607051)(−59168144055706, 140737946295714)(-59168144055706,\ 140737946295714)
(−59168661005917, 140739556636561)(-59168661005917,\ 140739556636561)(−11356070835532, 32692337730257)(-11356070835532,\ 32692337730257)
(−11355893082812, 32692115314032)(-11355893082812,\ 32692115314032)(−11356540064489, 32692924859856)(-11356540064489,\ 32692924859856)

Table 3. The coordinates of the points in X28X_{28}. 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 X28X_{28} 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 A∈X28A \in X_{28} is the common target of two arcs, say from BB to AA and from CC to AA, then there is a circle through AA and BB and another through AA and CC that touch each other at AA and both strictly enclose only 5 of the points in X28X_{28}.

To construct the 28m28m points, we replace uu by mm points near uu on the line that passes through uu and separates the two circles. It is also possible that a point u∈X28u \in X_{28} is target of only one directed arc, in which case we pick the mm points near uu and on the line that passes through uu and is tangent to a circle of the corresponding pair that strictly encloses only 5 points of X28X_{28}.

The argument that every pair in this set of 28m28m points has circle depth at most 6m−16m-1 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 nn, not necessarily divisible by 28, we choose a subset of the smallest multiple of 28 that is not smaller than nn to get the

Main Theorem. Π(n)≤6⌈n/28⌉−1\Pi(n) \le6\lceil n/28\rceil- 1, for every positive integer nn.

Since 3/14≤2/93/14 \le2/9, the Main Theorem supersedes Theorem 2.1, and because Ψ(n)≤Π(n)\Psi(n) \le\Pi(n) it also supersedes Theorem 4.1.

Finding Oases in the Desert

While the Main Theorem supersedes the others, we would never have found X28X_{28} and its extension to 28m28m points in R2\mathbb{R}^{2} if we did not have the opportunity to take the intermediate step of constructing Y28Y_{28} in R3\mathbb{R}^{3}. Indeed, the plane depth question in R3\mathbb{R}^{3} 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 R2\mathbb{R}^{2} 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 Φ2(n)\Phi_{2}(n) for the minmax two-sided circle depth for nn points in general position in R2\mathbb{R}^{2};

  • the one-sided plane depth of a pair in a finite set in R3\mathbb{R}^{3} as the minimum—over all non-vertical planes passing through the two points—of the number of points strictly below the plane, and write Φ3(n)\Phi_{3}(n) for the minmax one-sided plane depth for nn points in general and convex position in R3\mathbb{R}^{3}.

Clearly Ψ(n)≤Φ2(n)≤Π(n)\Psi(n) \le\Phi_{2}(n) \le\Pi(n) and Ψ(n)≤Φ3(n)≤Π(n)\Psi(n) \le\Phi_{3}(n) \le\Pi(n). After establishing Ψ(n)≤3n/14+O(1)\Psi(n) \le3n/14 + O(1) as explained in § 4, we have interacted with AI tools to first find 28 points in R3\mathbb{R}^{3} that imply Φ3(28)≤5\Phi_{3}(28) \le5, then generalize to get Φ3(28m)≤6m−1\Phi_{3}(28m) \le6m - 1, then find 28 points in R2\mathbb{R}^{2} that imply Φ2(28)≤5\Phi_{2}(28) \le5, and finally generalize to get Φ2(28m)≤6m−1\Phi_{2}(28m) \le6m - 1. Only after this sequence of successes did we find X28X_{28} and its extension of 28m28m 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 nn points in R3\mathbb{R}^{3} 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 Ψ(n)\Psi(n)? Using “depth” short for “two-sided plane depth” in this section, we denote the number of pairs at depth ii of a set Y⊆R3Y \subseteq\mathbb{R}^{3} by di(Y)d_i(Y), and write Dj(Y)=∑i=0jdi(Y)D_j(Y) = \sum_{i=0}^{j} d_i(Y) for the number of pairs at depth at most jj. With this notation, we have dj+1(Y)>0d_{j+1}(Y) > 0 iff Dj(Y)<(n2)D_j(Y) < \binom{n}{2}.

The Depth of Pairs and Triples

For a triple of points of a generic set Y⊆R3Y \subseteq\mathbb{R}^{3}, 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 n0n_{0} and n1n_{1} be the number of points on the two sides, we have n0+n1+3=nn_{0}+n_{1}+3=n, and assuming n0<n1n_{0}<n_{1}, we say the small side contains n0n_{0} points and the large side contains n1n_{1} points. Furthermore, we call n0n_{0} the depth of the triple. For example, the triples at depth 0 span the triangles of conv⁡(Y)\operatorname{conv}(Y). Note that the depth of the halving triples defined by n0=n1n_{0}=n_{1} 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 n0n_{0}-facet and n1n_{1}-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 i<(n−3)/2i<(n-3)/2, we write ei(Y)e_i(Y) for the number of triples at depth ii, and Ej(Y)=∑i=0jei(Y)E_j(Y)=\sum_{i=0}^{j}e_i(Y) for the number of triples at depth at most jj. Following Ramos and Viaña [17], we observe that

  • a pair has depth at most jj iff it belongs to a triple at depth jj;

  • 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 Dj(Y)≤32ej(Y)D_j(Y) \le\frac{3}{2}e_j(Y) as an upper bound for the number of pairs at depth at most jj. If the nn points in YY are in general as well as convex position, then the number of triples at depth jj, with 2j≤n−42j \le n-4, depends only on n=∣Y∣n=|Y| and not on the positions of the points [7, 13]. Writing econv⁡(j,n)=2(j+1)[n−(j+2)]e^{\operatorname{conv}}(j,n)=2(j+1)[n-(j+2)] for this number, we thus get

Dj(Y)≤3(j+1)[n−(j+2)](10)D_j(Y) \le3(j+1)[n-(j+2)] \tag*{(10)}

for nn 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 jj belongs to exactly two triples at depth jj; compare with condition (II) in the footnote in Section 3. If the points are not in convex position, then ej(Y)e_j(Y) may exceed econv⁡(j,n)e^{\operatorname{conv}}(j,n), so we cannot conclude that (10) holds beyond points in convex position.

Upper bounds for ej(Y)e_j(Y) have been a topic of investigation for decades, with the current best upper bound being O(n3/2)O(n^{3/2}) from 2001 [18]. It follows that Dj(Y)=O(n2)D_j(Y)=O(n^2) for j=O(n2/3)j=O(n^{2/3}), which guarantees pairs at depth j=O(n2/3)j=O(n^{2/3}). 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 YY in convex position. Nevertheless, we cannot rule out that the bound in (10) holds for all generic sets of nn points in R3\mathbb{R}^3, which would immediately generalize the depth bound for convex position to all generic sets in R3\mathbb{R}^3. Indeed, we show D1(Y)≤6n−18D_1(Y) \le6n - 18 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 D1(Y)≤6n−18D_1(Y) \le6n - 18, let BB be the extreme points in YY, and write A=Y∖BA = Y \setminus B for the non-extreme or inner points. For a∈Aa \in A, we consider the set of points bb whose removal makes aa a vertex of the convex hull. Formally,

Ra={b∈Y∣a is a vertex of conv⁡(Y∖{b})}(11)R_a = \{b \in Y \mid a \text{ is a vertex of } \operatorname{conv}(Y \setminus\{b\})\} \tag*{(11)}
=⋂{Q⊆Y∖{a}∣a∈conv⁡(Q)},(12)= \bigcap\{Q \subseteq Y \setminus\{a\} \mid a \in\operatorname{conv}(Q)\}, \tag*{(12)}

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 aa in their convex hull, by Carathéodory’s Theorem, so ∣Ra∣≤4|R_a| \le4, and there are at least two such quadruples of points if n≥6n \ge6, so ∣Ra∣≤3|R_a| \le3 whenever n≥6n \ge6.

Lemma 6.1. The number of pairs at two-sided plane depth at most 1 in a set YY of nn points in general position R3\mathbb{R}^3 is at most 6n−186n - 18.

Proof. A pair is at depth 0 iff its endpoints span an edge of the convex hull, which implies that their number is 3∣B∣−63|B| - 6. 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

d1=D1−D0=∑b∈B[deg⁡(b)+3new⁡(b)−3]−C,(13)d_1 = D_1 - D_0 = \sum_{b \in B} [\deg(b) + 3\operatorname{new}(b) - 3] - C, \tag*{(13)}

in which deg⁡(b)\deg(b) is the degree of bb in the edge graph of the convex hull of YY, new⁡(b)\operatorname{new}(b) is the number of inner points that become vertices of the convex hull upon the removal of bb, and CC 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

D1=3∣B∣−6+∑b∈B[deg⁡(b)+3new⁡(b)−3]−C(14)D_1 = 3|B| - 6 + \sum_{b \in B} [\deg(b) + 3\operatorname{new}(b) - 3] - C \tag*{(14)}
=6∣B∣−18+∑b∈B3new⁡(b)−C(15)= 6|B| - 18 + \sum_{b \in B} 3\operatorname{new}(b) - C \tag*{(15)}
≤6∣B∣−18+∑a∈A[3r(a)−Ca],(16)\le6|B| - 18 + \sum_{a \in A} [3r(a) - C_a], \tag*{(16)}

in which r(a)=∣Ra∣r(a) = |R_a| is the number of times aa appears as a vertex of the convex hull after the removal of a single extreme point, and CaC_a is the accumulated over-count for the pairs at depth 1 that connect aa to extreme points of YY. We get (16) from (15) by observing ∑bnew⁡(b)=∑ar(a)\sum_b \operatorname{new}(b)=\sum_a r(a) and ∑aCa≤C\sum_a C_a\le C as we ignore the over-count for pairs connecting two extreme points or two inner points.

The goal is now to show 3r(a)−Ca≤63r(a)-C_a\le6 for all a∈Aa\in A. Suppose a∈Aa\in A appears as a vertex on the convex hull upon the removal of b∈Bb\in B, and let Nb(a)N_b(a) be the set of neighbors of aa on the convex hull. Hence, aa is in the convex hull of Nb(a)∪{b}N_b(a)\cup\{b\}, which by (12) implies Rb⊆Nb(a)∪{b}R_b\subseteq N_b(a)\cup\{b\}. In other words, if r=r(a)≥2r=r(a)\ge2, then every pair at depth 1 that connects aa to an extreme point appears r−1r-1 times on the convex hull, so these pairs are over-counted r−2r-2 times. Hence, Ca≥r(r−2)C_a\ge r(r-2) and therefore 3r−Ca≤5r−r2≤63r-C_a\le5r-r^2\le6, 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 6⋅9−18=366\cdot9-18=36 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.

DegreeABC
degree 5A1=(−3,−3,−2)A_1=(-3,-3,-2)B1=(−2,−3,−3)B_1=(-2,-3,-3)C1=(−3,−2,−3)C_1=(-3,-2,-3)
degree 6A2=(−3,0,3)A_2=(-3,0,3)B2=(3,−3,0)B_2=(3,-3,0)C2=(0,3,−3)C_2=(0,3,-3)
degree 3A3=(−2,−1,2)A_3=(-2,-1,2)B3=(2,−2,−1)B_3=(2,-2,-1)C3=(−1,2,−2)C_3=(-1,2,-2)

Table 4. Nine points in R3\mathbb{R}^3 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 (6,6,6,5,5,5,3,3,3)(6,6,6,5,5,5,3,3,3), and all pairs have depth at most 1.

Lemma 6.2. For every n≥9n\ge9 there is a set of nn points in general and convex position in R3\mathbb{R}^3 with 6n−186n-18 pairs at two-sided plane depth at most 1.

Proof. The example of n=9n=9 points in Table 4 is the basis of this proof by induction. Denote this set Y9Y_9 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 Y9Y_9 has a degree-3 vertex, which is a property we maintain inductively for all sets.

Let vv be a degree-3 vertex and a,b,ca,b,c the neighbors of vv in the edge graph of conv⁡(Yn)\operatorname{conv}(Y_n), so abcabc is a triple at depth 1 of YnY_n. We construct Yn+1Y_{n+1} by carefully adding a new point, ww, close to vv, such that

  1. all pairs at depth at most 1 in YnY_n remain pairs at depth at most 1 in Yn+1Y_{n+1};

  2. ww belongs to at least 6 (new) pairs at depth at most 1 in Yn+1Y_{n+1}.

We thus increase the number of pairs at depth at most 1 by at least 6 in each step, which implies that Yn+1Y_{n+1} has at least 6(n+1)−186(n+1)-18 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 ww can be added to YnY_n such that Properties 1 and 2 are satisfied and, furthermore, ww has degree 3 in the edge graph of conv⁡(Yn+1)\operatorname{conv}(Y_{n+1}), so it can act as the vertex vv in the next iteration. Letting v,a,b,cv,a,b,c be the mentioned points in YnY_n, and x∈Ynx\in Y_n the third vertex of the second triangle incident to the edge bcbc in conv⁡(Yn)\operatorname{conv}(Y_n), we place ww such that it obeys the following conditions:

  1. ww is extreme in Yn+1=Yn∪{w}Y_{n+1}=Y_n\cup\{w\}, and v,b,cv,b,c are the neighbors of ww in the edge graph of conv⁡(Yn+1)\operatorname{conv}(Y_{n+1});

  2. ww is sufficiently close to vv, so there are no three points in Yn∖{v}Y_n\setminus\{v\} whose plane separates ww from vv;

  3. the plane spanned by w,v,aw,v,a has at least two points of YnY_n on each side.

Observe that Condition (i) is equivalent to ww being on the small side of the triple vbcvbc of YnY_n and on the large sides of the triples vacvac, vabvab, bcxbcx of YnY_n. Also note that Condition (iii) is equivalent to ww lying on the large sides of the two triples that contain the edge vava of conv⁡(Yn)\operatorname{conv}(Y_n). This is feasible because n≥6n\ge6 implies that each edge of conv⁡(Yn)\operatorname{conv}(Y_n) belongs to exactly two triples at depth 1. Next we argue that Conditions (i), (ii), (iii) imply Properties 1 and 2.

Property 1: since vv has degree 3, the only depth-1 triple of YnY_n that has vv on its small side is abcabc, and since ww is sufficiently close to vv, abcabc is also the only depth-1 triple of YnY_n that has ww on its small side. Hence, abcabc is the only depth-1 triple of YnY_n whose depth increases upon adding ww. Every pair of YnY_n that belongs to a depth-1 triple of YnY_n belongs to at least two depth-1 triples of YnY_n and therefore to at least one depth-1 triple of Yn+1Y_{n+1}. 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 YnY_n have depth at most 1 in Yn+1Y_{n+1}.

Property 2: to see that ww belongs to at least six pairs at depth at most 1 in Yn+1Y_{n+1}, note that three of these pairs span the edges wvwv, wbwb, wcwc in conv⁡(Yn+1)\operatorname{conv}(Y_{n+1}). One more pair is wawa, which is an edge of conv⁡(Yn+1∖{v})\operatorname{conv}(Y_{n+1}\setminus\{v\}) as ww is sufficiently close to vv. Finally, we rotate a plane about the edge wvwv, which it contains. Starting when the plane supports conv⁡(Yn+1)\operatorname{conv}(Y_{n+1})—so there are no points on its small side—it passes through the other n−1n-1 points in sequence, first bb and last cc. Letting b′b' be the second and c′c' the second to the last, this identifies wvb′wvb' and wvc′wvc' as depth-1 triples of Yn+1Y_{n+1}. We have b′≠c′b'\ne c' because n+1≥6n+1\ge6, and b′≠ab'\ne a, c′≠ac'\ne a by Condition (iii). Hence, wb′wb' and wc′wc' 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 jj, 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 jj proved in [2] for j<⌊n/4⌋j < \lfloor n/4 \rfloor and [22] for j≤n2−2j \le\frac{n}{2} - 2, respectively:

4(j+33)≤Ej(Y)≤2(j+22)n−4(j+33).(17)4\binom{j+3}{3} \le E_j(Y) \le2\binom{j+2}{2}n - 4\binom{j+3}{3}. \tag*{(17)}

Theorem 6.3. Let YY be a set of nn points in general but not necessarily convex position in R3\mathbb{R}^3. Then

Dj(Y)≤3[(2j+1)n−(3j2+6j+2)],(18)D_j(Y) \le3[(2j+1)n - (3j^2 + 6j + 2)], \tag*{(18)}

for every j≤n4−1j \le\frac{n}{4} - 1. This implies that YY necessarily contains a pair at two-sided plane depth 2−26n+O(1)\frac{2-\sqrt{2}}{6}n + O(1), in which 2−26=0.0976…\frac{2-\sqrt{2}}{6} = 0.0976\ldots

Proof. Consider a pair at depth jj or smaller, and note that it belongs to a positive even number of depth-kk triples for every kk with j≤k≤n2−2j \le k \le\frac{n}{2} - 2. Therefore, for every integer ℓ\ell with j≤ℓ≤n2−2j \le\ell\le\frac{n}{2} - 2, the number of triples with depth between jj and ℓ\ell that contain the pair is at least 2(ℓ+1−j)2(\ell+1-j). It follows that for 0≤j≤ℓ≤n2−20 \le j \le\ell\le\frac{n}{2} - 2 and j≤n4−1j \le\frac{n}{4} - 1,

2(ℓ+1−j)Dj(Y)≤3∑k=jℓek(Y)(19)2(\ell+1-j)D_j(Y) \le3\sum_{k=j}^{\ell}e_k(Y) \tag*{(19)}
=3[Eℓ(Y)−Ej−1(Y)](20)= 3[E_\ell(Y)-E_{j-1}(Y)] \tag*{(20)}
≤3[2(ℓ+22)n−4(ℓ+33)−4(j+23)],(21)\le3\left[2\binom{\ell+2}{2}n-4\binom{\ell+3}{3}-4\binom{j+2}{3}\right], \tag*{(21)}

in which we use both inequalities in (17) to get (21). Assuming 2j≤n2−22j \le\frac{n}{2} - 2, we choose ℓ=2j\ell=2j which gives

Dj(Y)≤32(j+1)[2(2j+22)n−4(2j+33)−4(j+23)](22)D_j(Y) \le\frac{3}{2(j+1)}\left[2\binom{2j+2}{2}n-4\binom{2j+3}{3}-4\binom{j+2}{3}\right] \tag*{(22)}
=3[(2j+1)n−(3j2+6j+2)].(23)=3[(2j+1)n-(3j^2+6j+2)]. \tag*{(23)}

The largest value of jj that satisfies 3[(2j+1)n−(3j2+6j+2)]<(n2)3[(2j+1)n-(3j^2+6j+2)] < \binom{n}{2} is

⌊2n−6−2n2−10n+126⌋−1=2−26n+O(1),(24)\left\lfloor\frac{2n-6-\sqrt{2n^2-10n+12}}{6}\right\rfloor-1=\frac{2-\sqrt{2}}{6}n+O(1), \tag*{(24)}

as claimed.

We mention that a more careful choice of ℓ≈2.15j\ell\approx2.15j 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, 12−112\frac{1}{2}-\frac{1}{\sqrt{12}}, is tight for Ψ(n)\Psi(n) as well as for Π(n)\Pi(n). But this does not imply Ψ(n)=Π(n)\Psi(n)=\Pi(n) for every positive integer nn, and indeed the authors tend to believe that the two functions are different for some nn.

  • Suppose kk and nn are positive integers satisfying (n2)≤3kn−3k(k+1)\binom{n}{2}\leq3kn-3k(k+1); compare with (4) in Section 3. Is it true that in this case there are nn points in R3\mathbb{R}^{3} such that all (n2)\binom{n}{2} pairs have plane depth at most k−1k-1? Assuming such nn points exist, is it furthermore true that the nn points can be chosen in convex position? If found correct, this would imply that the constant of the current best lower bound, 12−112\frac{1}{2}-\frac{1}{\sqrt{12}}, is tight for Ψ(n)\Psi(n). We verified this conjecture for all relevant pairs (n,k)(n,k) with n≤28n\leq28.

It is interesting to see that one step in establishing our results was showing that the complex of triangles at certain depths j>0j>0 (usually called jj-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 YY be nn points in general and convex position in R3\mathbb{R}^{3}, the triangles at plane depth jj, for some j<(n−3)/2j<(n-3)/2, 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 jj belongs to a positive even number of triangles at depth jj, 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 j=0j=0 it cannot. Indeed, their conjectured relation Dj(Y)≤3(j+1)n−22j+3D_j(Y)\leq3(j+1)n-2^{2j+3}, with the right-hand side smaller than (10) by j2+jj^2+j, excludes the possibility of a weak pseudomanifold for j>0j>0. 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 j=1j=1 and j=5j=5, where, additionally, all pairs are edges of the complex.

References

  1. [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.
  2. [3]J. Akiyama, Y. Ishigami, M. Urabe and J. Urrutia. On circles containing the maximum number of points. Discrete Math. 151 (1996), 15–18.
  3. [4]B. Bagchi and B. Datta. A structure theorem for pseudomanifolds. Discrete Math. 168 (1998), 41–60.DOI
  4. [5]I. Bárány and D.G. Larman. A combinatorial property of points and ellipsoids. Discrete Comput. Geom. 5 (1990), 375–382.DOI
  5. [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
  6. [7]K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4 (1989), 387–421.
  7. [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
  8. [9]B. Delaunay. Sur la sphère vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskie i Estestvennykh Nauk 7 (1934), 793–800.
  9. [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
  10. [11]R. Hayward. A note on the circle containment problem. Discrete Comput. Geom. 4 (1989), 263–264.DOI
  11. [12]R. Hayward, D. Rappaport and R. Wenger. Some extremal results on circles containing points. Discrete Comput. Geom. 4 (1989), 253–258.DOI
  12. [13]D.-T. Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31 (1982), 478–487.DOI
  13. [14]L. Lovasz, K. Vestergombi, U. Wagner and E. Welzl. Convex quadrilaterals and k-sets. Contemp. Math. 342 (2004), 139–148.
  14. [15]V. Neumann-Lara and J. Urrutia. A combinatorial result about points and circles on the plane. Discrete Math. 69 (1988), 173–178.
  15. [16]M.N. Prodromou. A combinatorial property of points and balls, a colored version. Discrete Comput. Geom. 38 (2007), 641–650.DOI
  16. [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
  17. [18]M. Sharir, S. Smorodinsky and G. Tardos. An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26 (2001), 195–204.
  18. [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
  19. [20]T. Tuttle. Online Routing and Containment Problems. Ph.D. thesis, Computer Science Department, Carleton University, Ottawa, Ontario, 2026.
  20. [21]J. Urrutia. Open problems in computational geometry. In “Proc. 5th Latin American Sympos. Theoret. Informatics”, Springer LNCS 2286 (2002), 4–11.
  21. [22]E. Welzl. Entering and leaving j-facets. Discrete Comput. Geom. 25 (2001), 351–364.DOI

Paper details

vlnc:W_2pszy3f6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents