Counting Large Distances in Convex Polygons: A Computational Approach

Abstract

In a convex n-gon, let ${d}_{1} > {d}_{2} > \cdots$ denote the set of all distances between pairs of vertices, and let m _i be the number of pairs of vertices at distance d _i from one another. Erdős, Lovász, and Vesztergombi conjectured that $\sum\nolimits_{i\leq k}{m}_{i} \leq kn$. Using a new computational approach, we prove their conjecture when k ≤ 4 and n is large; we also make some progress for arbitrary k by proving that $\sum\nolimits_{i\leq k}{m}_{i} \leq (2k - 1)n$. Our main approach revolves around a few known facts about distances, together with a computer program that searches all distance configurations of two disjoint convex hull intervals up to some finite size. We thereby obtain other new bounds, such as m ₃ ≤ 3n∕2 for large n.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Given a set S of n points in the plane, let ${d}_{1} > {d}_{2} > \cdots$ be the set of all distances between pairs of points in S. It was shown by Hopf and Pannwitz in 1934 [5] that the distance d ₁ (the diameter of S) can occur at most n times, which is tight (e.g., for a regular polygon of odd order). In 1987, Vesztergombi [6] showed that the second-largest distance, d ₂, can occur at most $\frac{3} {2}n$ times; she subsequently [7] considered the version of the problem when the points are in convex position and showed that in this case the number of second-largest distances is at most $\frac{4} {3}n$. She also showed that both results are tight up to additive constants.

Let m _i denote the number of times that d _i occurs. It is known that ${m}_{k} \leq 2kn$ [6], and moreover that ${m}_{k} \leq kn$ for point sets in convex position [7], while the following open conjecture would imply ${m}_{k} \leq 2n$.

Conjecture 1.1 (Erdős, Moser [2, 7]). 

The number of unit distances generated by n points in convex position cannot exceed 2n.

A lower bound of 2n − 7 for this conjecture is known due to Edelsbrunner and Hajnal [3].

For the rest of the chapter, we consider only point sets in convex position. One natural question is to find how large ${m}_{\leq k} :=\sum\nolimits_{i\leq k}{m}_{i}$, i.e., the number of top-k distances, can be in terms of n. The conjectured value is

Conjecture 1.2 (Erdős, Lovász, Vesztergombi [4]). 

The number of top-k distances generated by n points in convex position is at most kn; i.e., ${m}_{\leq k} \leq kn$.

Odd regular polygons prove m _{≤ k}  = kn is possible. In [4], the bound ${m}_{\leq k} \leq 3kn$ is proven, and ${m}_{\leq 2} \leq 2n$ was shown in [7], verifying Conjecture 1.2 for k = 2.

In this chapter, we give improved upper bounds on m _k and ${m}_{\leq k}$ for convex point sets, and more generally bounds for sums of the form $\sum\nolimits_{t\in T}{m}_{t}$. Our first result is the following.

Theorem 3.

For any k ≥ 1, the number of top-k distances generated by n points in convex position is at most (2k − 1)n; i.e.,  ${m}_{\leq k} \leq (2k - 1)n$.

Thus, we close about half of the gap toward Conjecture 1.2.

Next, by combining several known conditions on distances for convex point sets, and by using a computer program to carry out an exhaustive search on a finite abstract version of the problem, we prove the following.

Theorem 4.

The distances generated by n points in convex position satisfy the following bounds, for large enough n:

• ${m}_{\leq 3} \leq 3n,{m}_{\leq 4} \leq 4n;$

• ${m}_{3} \leq \frac{3} {2}n,{m}_{4} \leq \frac{13} {8} n;$

• ${m}_{1} + {m}_{3} \leq 2n,{m}_{2} + {m}_{3} \leq \frac{9} {4}n.$

In particular, we verify Conjecture 1.2 for k ≤ 4 and n large. For m ₃ and ${m}_{2} + {m}_{3}$, the bound is as good as can be obtained by our abstract version of the problem, as witnessed by periodic patterns achieving ${m}_{3} = \frac{3} {2}n$ and ${m}_{2} + {m}_{3} = \frac{9} {4}n$, but we do not know if any convex polygon can realize these distances; we elaborate in Sect. 6.

The proof of Theorem 4 uses a computer program to make certain types of automatic deductions, as well as the following lemma to eliminate long distances “near” the boundary.

Lemma 1.5.

For any k ≥ 1 and ℓ ≥ 0, there is a constant C(k,ℓ) such that the following holds: In a convex polygon, if there are ℓ or fewer vertices between some vertices a and b such that $\vert ab\vert \geq {d}_{k}$ , then the number of top-k distances satisfies ${m}_{\leq k} \leq n + C(k,\mathcal{l})$.

The detailed bound we obtain is of the form $C(k,\mathcal{l}) = O({k}^{2}{(k + \mathcal{l})}^{2})$. In an earlier version of this chapter,¹ we proved results like “${m}_{\leq 3} \leq 3n + O(1)$,” which are weaker for large n but better for small n, using the following alternative lemma.

Lemma 1.6.

For any k ≥ 1 and ℓ ≥ 0, there is a constant C′(k,ℓ) such that the following holds. In a convex polygon, at most C′(k,ℓ) diagonals ab have both (i) ℓ or fewer vertices between a and b and (ii) $\vert ab\vert \geq {d}_{k}$.

In the latter, $C^{\prime}(k,\mathcal{l}) = O(k{\mathcal{l}}^{2})$. We do not think either lemma is tight.

In Sect. 2, we describe levels, a key element in our approach. In Sect. 3, we collect geometric facts used by the algorithm. We prove Lemma 1.5 in Sect. 3.1. The proof of our main result, Theorem 4, consists of the algorithmic approach described in Sect. 4 together with our computational results stated in Sect. 5. We conclude with suggestions for future work.

2 Levels

We use the term diagonal to mean any line segment connecting two points of S, including sides of the convex hull of S. We will partition the diagonals into nlevels in the following way. Let $S =\{ {a}_{1},{a}_{2},\ldots,{a}_{n}\}$ be the vertex set of our convex polygon, ordered clockwise. Then leveli is the set of diagonals

$${L}_{i} :=\{ {a}_{j}{a}_{k}\mid j + k \equiv i\ \text{ mod}\ n\},$$

where the index i can be taken modulo n. Equivalently, consider an auxiliary regular n-gon ${b}_{1}{b}_{2}\ldots {b}_{n}$; then two diagonals ${a}_{i}{a}_{j}$ and ${a}_{k}{a}_{l}$ lie in the same level when the corresponding segments ${b}_{i}{b}_{j}$ and ${b}_{k}{b}_{l}$ are parallel. We illustrate this in Fig. 1a.

Fig. 1

(a) Three consecutive levels of diagonals in a convex decagon. (b) Proof of Fact 3.2

Levels are used in the following way to prove Theorem 3 (i.e., ${m}_{\leq k} \leq (2k - 1)n$).

Proof of Theorem 1.3.

In the next section, we prove Lemma 3.5: In any level, there are at most 2k − 1 diagonals of length ≥ d _k . Since there are at most n levels, we are done.$\square$

3 Geometric Facts

To begin this section, we collect four geometric facts from the literature [1, 4, 7], which will be used in our computer program. For completeness, we include the proofs. The first two facts were used in [4, 7].

Fact 3.1.

If abcd is a convex quadrangle, then $\vert ab\vert + \vert cd\vert < \vert ac\vert + \vert bd\vert$.

Proof.

Let p be the intersection point of the diagonals ac, bd. Then, by the triangle inequality,

$$\qquad \qquad \vert ab\vert + \vert cd\vert < \vert ap\vert + \vert bp\vert + \vert cp\vert + \vert dp\vert = \vert ac\vert + \vert bd\vert \,.\qquad \qquad \qquad \qquad \square $$

Fact 3.2.

If a, b, c, d are vertices of a convex polygon in clockwise order, then at least one of these four cases must occur:

•  | ax |  >  | ad | for all vertices x of the polygon between c and d, including c;

•  | bx |  >  | bc | for all vertices x of the polygon between c and d, including d;

•  | cx |  >  | bc | for all vertices x of the polygon between a and b, including a;

•  | dx |  >  | ad | for all vertices x of the polygon between a and b, including b.

Proof.

Since the sum of the angles of quadrilateral abcd is 2π, at least one angle is nonacute. Without loss of generality, let $\angle cda \geq \frac{\pi } {2}$. Then for any vertex x of the polygon between c and d, we have that $\angle xda \geq \angle cda \geq \frac{\pi } {2}$, and, thus, | ax |  >  | ad | (see Fig. 1b).$\square$

The special case i = j of the following fact appears in [4].

Fact 3.3.

If a, b, c, d are vertices of a convex polygon listed in clockwise order, such that $\vert bc\vert \geq {d}_{i}$ and $\vert ad\vert \geq {d}_{j}$, where d _i and d _j are the ith- and jth-largest distances among vertices of the polygon, then either between a and b or between c and d there are no more than $i + j - 3$ other vertices of the polygon.

Proof.

Let’s denote without loss of generality $a = {a}_{1},b = {a}_{x},c = {a}_{y},d = {a}_{z}$. We will show $\min \{x - 1,z - y\} \leq i + j - 2$, which proves the lemma. We use induction on i + j see Fig. 2. The base case $i = j = 1$ amounts to saying that any two noncrossing d ₁’s must share a vertex, which follows by Fact 3.1.

For the inductive step, we apply Fact 3.2. Suppose that the first of the four cases happens, so $d^{\prime} := {a}_{z-1}$ satisfies | ad′ |  >  | ad | ; the other cases are similar. Consequently, $\vert ad^{\prime}\vert \geq {d}_{j-1}$. By induction, $\min \{x - 1,(z - 1) - y\} \leq i + (j - 1) - 3$, from which the desired result follows (Fig. 2).$\square$

Fig. 2

(a) Proof of Fact 3.3, base case i = 2, j = 1; (b) proof of Fact 3.3, inductive step

The following is a strengthening of a result of Altman, obtained by removing all nonessential conditions from the hypothesis of [1, Lemma 1] but using the same proof. (He considered only the case where $\vert {a}_{1}{a}_{m}\vert = {d}_{1}$.)

Fact 3.4.

Let ${a}_{1}\ldots {a}_{n}$ be a convex polygon. If $1 \leq i < j \leq k < \mathcal{l} < m$ and $\vert {a}_{1}{a}_{m}\vert \geq \max \{\vert {a}_{1}{a}_{k}\vert,\vert {a}_{j}{a}_{m}\vert \}$, then $\vert {a}_{i}{a}_{\mathcal{l}}\vert >\min \{ \vert {a}_{i}{a}_{k}\vert,\vert {a}_{j}{a}_{\mathcal{l}}\vert \}$.

Proof.

Suppose for the sake of contradiction that $\vert {a}_{i}{a}_{\mathcal{l}}\vert \leq \min \{\vert {a}_{i}{a}_{k}\vert,\vert {a}_{j}{a}_{\mathcal{l}}\vert \}$. Denote by x and y the points where ${a}_{1}{a}_{j}$ and ${a}_{m}{a}_{k}$ intersect ${a}_{i}{a}_{\mathcal{l}}$ (see Fig. 3a). Repeatedly using the fact that when s, s′ are two sides of a triangle, $\vert s\vert > \vert s^{\prime}\vert$ iff the angle opposite s is larger than the angle opposite s′, we have

$$\begin{array}{rcl} \angle {a}_{j}x{a}_{\mathcal{l}} + \angle {a}_{k}y{a}_{i}& & > \angle {a}_{j}{a}_{i}{a}_{\mathcal{l}} + \angle {a}_{k}{a}_{\mathcal{l}}{a}_{i} \geq \angle {a}_{i}{a}_{j}{a}_{\mathcal{l}} + \angle {a}_{\mathcal{l}}{a}_{k}{a}_{i} \\ & & > \angle {a}_{1}{a}_{j}{a}_{m} + \angle {a}_{1}{a}_{k}{a}_{m} \geq \angle {a}_{j}{a}_{1}{a}_{m} + \angle {a}_{k}{a}_{m}{a}_{1}\,.\end{array}$$

However, $\angle {a}_{j}x{a}_{\mathcal{l}} + \angle {a}_{k}y{a}_{i} = \angle {a}_{j}{a}_{1}{a}_{m} + \angle {a}_{k}{a}_{m}{a}_{1}$, which gives a contradiction.$\square$

3.1 Counting Lemmas

First, we complete the proof of Theorem 3, using Fact 3.3.

Lemma 3.5.

In any level, there are at most 2k − 1 diagonals of length ≥ d _k.

Proof.

Without loss of generality (by relabeling), we consider the level L ₀. The diagonals of this level are ${a}_{j}{a}_{-j}$, with indices modulo n, for 0 < j < n ∕ 2. Let m > 0 (resp., M) be the minimal (resp., maximal) j such that $\vert {a}_{j}{a}_{-j}\vert \geq {d}_{k}$. Then, by Fact 3.3, we see that $M - m - 1 \leq k + k - 3$. So the number of top-k diagonals in L ₀ is bounded by $\vert \{m,m + 1,\ldots,M\}\vert = M - m + 1 \leq 2k - 1$, which gives the corollary.$\square$

Next, we give the proof of Lemma 1.5, which is needed in order to argue that our computational approach is correct.

Proof.

We want to show that if | ab | ≥ d _k , and a and b are separated by at most ℓ vertices, then the number of top-k distances satisfies ${m}_{\leq k} \leq n + O({k}^{2}{(k + \mathcal{l})}^{2})$. Let S be the interval obtained from this [a, b] by extending onto 2k further points in both directions. By Fact 3.3, all edges of length ≥ d _k have at least one endpoint in S. Note $\vert S\vert = O(k + \mathcal{l}).$

Fig. 3

(a) Proof of Fact 3.4; (b) proof of Lemma 1.5

We will show an upper bound of $n + O({k}^{2}{(k + \mathcal{l})}^{2})$ on the number of edges sx of length ≥ d _k , with $s \in S,x \in V \setminus S$. This will complete the proof since the only other top-k distance edges must lie with both endpoints in S, and there are at most O(k + ℓ)² such edges.

The key observation is that in the bipartite graph between S and $V \setminus S$ consisting of these edges, all but a constant number of vertices in $V \setminus S$ have degree 1. Specifically, if sx, s′x are both edges in this graph, then the location of x is uniquely determined by s, s′, | sx | , and | s′x | ; it follows that $\sum\nolimits_{x}\left(\begin{array}{c} \mathrm{deg}(x)\\ 2 \end{array} \right)$ is at most $O({(k + \mathcal{l})}^{2}{k}^{2})$, and consequently $\sum\nolimits_{x:\deg (x)>1}\deg (x) = O({(k + \mathcal{l})}^{2}{k}^{2})$. We are then done by counting the endpoints of degree-1 vertices, of which there are at most n.$\square$

4 The Algorithm

The algorithm we use to prove Theorem 4 examines distances among finite configurations of points in the plane. Informally, we examine all possible configurations of a bounded size, where a configuration includes all occurrences of top-k distances in a few consecutive levels, and we try to establish that not too many top-k distances can occur per level, averaged over a small interval of levels. Thus, ultimately, the argument in our proof decomposes any global point set into local configurations of bounded size.

4.1 The Goal

Our computational goal will be to bound the number of long distances that can occur in a consecutive sequence of several levels. We begin by reproving (for large n) Vesztergombi’s result on counting the second-largest distances; it illustrates the type of computational result we need.

Proposition 4.1.

We have ${m}_{2} \leq \frac{4} {3}n$ for large enough n.

Proof.

We prove the theorem for $n \geq 3 \cdot C(16,2)$ with C as in Lemma 1.5. Let a special diagonal be a diagonal of length d ₂ or longer, whose endpoints are separated by at most 16 vertices. If there is any special diagonal, we are done by Lemma 1.5. So we may assume there are no special diagonals.

Using our computer program, we establish the following lemma.

Lemma 4.2.

In every point set S without special diagonals, for every level i, at least one of the following is true:

• at most $1 = \lfloor 1 \cdot \frac{4} {3}\rfloor$ diagonal in level i has length d ₂;

• at most $2 = \lfloor 2 \cdot \frac{4} {3}\rfloor$ diagonals in levels i and i + 1 have length d ₂;

• at most $4 = \lfloor 3 \cdot \frac{4} {3}\rfloor$ diagonals in levels $i,\ldots,i + 2$ have length d ₂;

• at most $5 = \lfloor 4 \cdot \frac{4} {3}\rfloor$ diagonals in levels $i,\ldots,i + 3$ have length d ₂.

Now let’s see how this gives the desired result. Taking $i = 1$, the four cases above establish that for some $1 \leq {\gamma }_{1} \leq 4$, the number of d ₂’s in levels $1,\ldots,{\gamma }_{1}$ is at most $\frac{4} {3}{\gamma }_{1}$. Applying the same logic to $i = {\gamma }_{1} + 1$, we get that there is some $1 \leq {\gamma }_{2} \leq 4$ such that the number of d ₂’s in levels ${\gamma }_{1} + 1,\ldots,{\gamma }_{1} + {\gamma }_{2}$ is at most $\frac{4} {3}{\gamma }_{2}$.

We continue to further define γ _i ’s in the same way until $\sum\nolimits_{i=1}^{x}{\gamma }_{i} \equiv \sum\nolimits_{i=1}^{y}{\gamma }_{i} ({\rm mod} n)$ for some x < y. Summing a contiguous subset of these bounds, the number of d ₂’s in levels from $1 +\sum\nolimits_{i=1}^{x}{\gamma }_{i}$ to $\sum\nolimits_{i=1}^{y}{\gamma }_{i}$ is at most $\frac{4} {3}$ per level on average. But this sum counts each of the n levels an equal number of times, so the number of d ₂’s overall is at most $\frac{4} {3}n$.$\square$

The computer program’s goal is thus to prove a general version of Lemma 4.2: Given a target ratio α and target distances (a subset of $\{{d}_{1},{d}_{2},\ldots,{d}_{k}\}$), find a constant m so that every level i admits 1 ≤ m′ ≤ m such that $\leq m^{\prime} \cdot \alpha$ target lengths occur in levels $i,\ldots,i + m^{\prime}$. The program searches for a point set with > α target diagonals in level 1, > 2α in level 2, etc. If the search terminates, the above proof shows the number of target distances is ≤ αn. The hypothesis that no special diagonals exist is used only indirectly by the program, explained below.

Our algorithm works with configurations consisting of two disjoint intervals of points, and an assignment of a distance from $\{{d}_{1},{d}_{2},\ldots,{d}_{k},\, ``< {d}_{k}\}$ to each diagonal spanning the two intervals. We thereby obtain analogues of Lemma 4.2 by checking all possible configurations up to some finite size. For this to work, Fact 3.2 is crucial since it implies that all of the top-k distances in ℓ consecutive levels have all of their endpoints in two intervals of bounded size. We use an incremental branch-and-bound search: It exhaustively searches all possibilities, but in an efficient way where large sections of the search space can be eliminated at once. Each individual step of the algorithm corresponds to an application of one of the Facts 3.1–3.4. The lack of special diagonals allows us to focus on disjoint interval pairs. The Java implementation is available at http://sourceforge.net/projects/convexdistances/.

4.2 Configurations

In more detail, our algorithm maintains a set of configurations. Each configuration has two disjoint intervals of points from S; then for each diagonal generated by one point from each interval, the configuration stores a set of possible values for the distance between those two points. Arbitrarily name one interval the top and denote its points as {t _i } _i , with t _{i + 1} following t _i in clockwise order, and name the other interval the bottom with points $\{{b{}_{i}\}}_{i}$, and b _{i − 1} following b _i in clockwise order. Then we denote the set of possible distances between t _i and b _j as D[i, j]; in each configuration D[i, j] is a subset of $\{1,2,\ldots,k,\infty \}$, where x ∈ D[i, j] means that d _x is a possible value for the distance $\vert {t}_{i}{b}_{j}\vert$, while ∞ ∈ D[i, j] means that it is possible for $\vert {t}_{i}{b}_{j}\vert$ to be shorter than d _k . (So typical steps in our program use special cases to reason with “${d}_{\infty }$” distances correctly.) Reiterating, a configuration consists of a top interval of indices, a bottom interval of indices, and for each top-bottom pair a subset of $\{1,2,\ldots,k,\infty \}$.

We assume that ${t}_{i}{b}_{j}$ is in level number j − i (modulo n), which is without loss of generality. To gain some intuition and exhibit the notation, it is helpful to look at a couple of examples. Our examples will be drawn from actual point sets and therefore each D[i, j] will be just a singleton, in contrast to the larger sets D[i, j] typically occurring in the algorithm. The first example, shown in Fig. 4, is a regular polygon of odd order. The second example, shown in Fig. 5, exhibits the extremal construction of Vesztergombi for second distances [7].

Fig. 4

Left: an odd regular polygon, with a top and bottom interval. Right: the corresponding values of D, where entry x in column i, row j indicates D[i, j] = { x}. One level is illustrated on the left and circled on the right

Fig. 5

Left: an illustration of Vesztergombi’s construction with ${m}_{2} = \frac{4} {3}n - O(1)$. Some diagonals of lengths d ₁ and d ₂ are shown (solid and dotted, respectively). Right: the corresponding configuration; again, entry x in column i, row j indicates D[i, j] = { x}

4.3 Methodology

Here is an example of a typical step in the algorithm, shown in Fig. 6. Suppose some configuration includes points ${t}_{1},{t}_{2},{b}_{2},{b}_{1}$, suppose that $D[1,1] = D[2,2] =\{ 2\}$, $D[1,2] =\{ 2,3,\infty \}$ and that $D[2,1] =\{ 1,2,3,\infty \}$. Then, using Fact 3.1, we know that $\vert {t}_{1}{b}_{2}\vert + \vert {t}_{2}{b}_{1}\vert > \vert {t}_{1}{b}_{1}\vert + \vert {t}_{2}{b}_{2}\vert$. As the right-hand side equals 2d ₂ and the maximum possible length of ${t}_{1}{b}_{2}$ is d ₂, we can deduce that $\vert {t}_{2}{b}_{1}\vert > {d}_{2}$ and so we may update the configuration via $D[2,1] :=\{ x \in D[2,1]\mid x < 2\} =\{ 1\}$.

Fig. 6

A typical step of the algorithm, using Fact 3.1

The program uses Facts 3.1–3.4 in ways analogous to the above example. Whenever one of the facts is applicable, we use it to reduce the size of one set D in the configuration. We use Fact 3.4 only when ${a}_{1},{a}_{i},{a}_{j}$ lie in the top interval and ${a}_{k},{a}_{l},{a}_{n}$ lie in the bottom, or vice versa.

Our algorithm also makes use of another easy observation. In any instance S, it cannot be true that both ${d}_{1} + {d}_{3} > {d}_{2} + {d}_{2}$ and ${d}_{1} + {d}_{3} < {d}_{2} + {d}_{2}$. Hence, using Fact 3.1, a quadruple t, t′, b′, b (in that cyclic order) with $\vert tb\vert = \vert t^{\prime}b^{\prime}\vert = {d}_{2},\vert tb^{\prime}\vert = {d}_{1},\vert t^{\prime}b\vert = {d}_{3}$ cannot co-exist with another quadruple $\hat{t},\hat{t}^{\prime},\hat{b}^{\prime},\hat{b}$ with $\vert \hat{t}\hat{b}\vert = {d}_{1},\vert \hat{t}^{\prime}\hat{b}^{\prime}\vert = {d}_{3},\vert \hat{t}\hat{b}^{\prime}\vert = \vert \hat{t}^{\prime}\hat{b}\vert = {d}_{2}$. More generally, given a configuration, we can deduce from any i, j, i′, j′ with each $D[i,j],D[i,j^{\prime}],D[i^{\prime},j],D[i^{\prime},j^{\prime}]$ singletons other than {∞} that an inequality of the form ${d}_{w} + {d}_{x} > {d}_{y} + {d}_{z}$ is true; in testing a configuration for validity, our program will reject any configuration where a contradiction arises from the set of all such pairwise inequalities. This is done by testing the associated digraph of $\left(\begin{array}{c} k + 1\\ 2 \end{array} \right)$ pairs for acyclicity. (We also include arcs of the form ${d}_{x} + {d}_{y} > {d}_{x} + {d}_{z}$ whenever y < z.)

In some situations none of these facts is applicable; say, for example, if each D[i, j] is equal to {1, 2, ∞}, we cannot conclude any further information. In this case, we use an approach that is similar to recursion or branch-and-bound in this situation, which works as follows. Find some i, j with | D[i, j] |  > 1, and let X denote D[i, j]. We then replace this configuration with two new configurations: Each of the new ones is almost identical to the original, except that in one we take $D[i,j] {=\min }_{x\in X}x$ and in the other we take $D[i,j] = X{\setminus \{\min }_{x\in X}x\}$. In a little more detail, while we are examining the levels from 1 to L, we only perform branching on diagonals in levels 1 to L, (i.e., only when $1 \leq j - i \leq L$) and any other nonsingleton D[i, j] does not entail branching. This was faster in practice than branching on every D[i, j].

4.4 Initializing and Growing Configurations

Recall that our theorems are all of the following form, for a set T of positive integers and some real α:

$$\sum\limits_{t\in T}{m}_{t} \leq \alpha n + O(1). $$

(♠)

We call a target distance any distance d _t with t ∈ T. We use k to represent the largest number in T.

We begin this detailed section by explaining why it suffices to examine configurations of bounded size to bound the number of target distances in L consecutive levels. The key tool is Fact 3.3. Namely, suppose ${t}_{0}{b}_{1}$ is any diagonal in level 1 with length $\vert {t}_{0}{b}_{1}\vert \geq {d}_{k}$, and consider any top-k distance diagonal e in levels $1,\ldots,L$. If e crosses ${t}_{0}{b}_{1}$, then t ₀ (resp., b ₁) is within L steps along the boundary from an endpoint of e (resp., the other endpoint of e). If e and ${t}_{0}{b}_{1}$ don’t cross, one endpoint of e is at most 2k steps from t ₀ or b ₁ by Fact 3.3, and the other endpoint of e is at most 2k + L points away from the other of t ₀ or b ₁. Summarizing, in either case, e has one endpoint in the interval I _t consisting of vertices at most 2k + L steps from t ₀, and e’s other endpoint lies in the interval I _b consisting of vertices at most 2k + L steps from b ₁; and this holds for all top-k distance diagonals e in levels $1,\ldots,L$.

Our program makes valid deductions whenever these intervals are disjoint, which is false only when t ₀ and b ₁ are within 2(2k + L) steps of one another on the boundary. Set $\mathcal{l} = 2(2k + L)$ and define a special diagonal to be one with length ≥ d _k and at most ℓ vertices between its endpoints. Recall that $\vert {t}_{0}{b}_{1}\vert \geq {d}_{k}$, so the program’s deductions are valid unless there was a special diagonal. This explains the choice of $16 = 2(2 \cdot 2 + 4)$ in Proposition 4.1 and justifies our general approach.

In the rest of this section, we explain some of the implementation details. The program begins working with a configuration consisting of a single diagonal t ₀ b ₁ of length ≥ d _k , and we assume without loss of generality that there are no diagonals ${t}_{i}{b}_{i+1}$ such that i < 0 and $\vert {t}_{i}{b}_{i+1}\vert \geq {d}_{k}$. Thus, the top and bottom intervals begins as the singleton sets $\{{t}_{0}\},\{{b}_{1}\}$.

We will now enlarge these configurations. Reviewing our proof strategy, the program must enumerate all possible configurations such that level 1 has more than α diagonals of a target length, and levels 1 and 2 together have more than 2α, etc., with the hope being that once the number of levels is high enough, we find that no such configurations exist, since this would give a result like Lemma 4.2.

Note that, by our choice of t ₀ and b ₁, which normalize our indices, in any convex point set, all level-1 diagonals of the target distances are of the form ${t}_{i}{b}_{i+1}$ for i > 1, and by Fact 3.3, they also satisfy i ≤ 2k − 2. So crucially, their possible positions are confined to an interval of bounded size. We now determine which of these diagonals have target lengths by exhaustive guessing, a term that simply means trying all possibilities. In detail, first, exhaustively guess the smallest i > 0 for which ${t}_{i}{b}_{i+1}$ is a target distance, then the second-smallest, etc. When the top and bottom intervals are enlarged, each new D[i, j] is set to $\{1,\ldots,k,\infty \}$ by default, meaning that no assumptions are made on the distance. When i is guessed as a minimal new level-1 diagonal for which ${t}_{i}{b}_{i+1}$ is a target distance, rather than the defaults, we set $D[i,i + 1] = T$ and $D[i^{\prime},i^{\prime} + 1] :=\{ 1,\ldots,k,\infty \}\setminus T$ for all new i′ < i.

After each new diagonal is added, we reapply Facts 3.1–3.4 in order to make additional deductions and eliminate any impossible configuration; and we split any nonsingleton sets D in the first level, as described earlier.

After this exhaustive guessing, we have collected all possible configurations. We keep only those for which level 1 has more than α diagonals of the target lengths. If any exist, we grow them in all possible ways to 2-level configurations, using exhaustive guessing like that explained above, except that we expand “to the left” before expanding “to the right” (for level 1, only rightward expansion was needed due to our choice of t ₀ and b ₁). Again, we prune those that have no more than 2α target distance in the first two levels.

We repeat the process described in the previous paragraph over and over, increasing the number of levels by 1 each time. If the program terminates eventually, it implies a result of the form like Lemma 4.2 and consequently that (♠) holds for this choice of T and α. We give a high-level review of the algorithm in Fig. 7.

Fig. 7

Sketch of the algorithm

5 Results: Proof of Theorem 4

Each row in Table 1 corresponds to an execution of our program that terminated. In other words, each execution establishes that an analogue of Lemma 4.2 holds, and we consequently deduce Theorem 4 using reasoning as in the proof of Proposition 4.1. Each line proves

$$\sum\limits_{t\in T}{m}_{t} \leq \alpha n\text{ for}\ n > C(k,2(2k + L))/(\alpha - 1), $$

(♣)

where k is the largest element of T, and C is the constant from Lemma 1.5. Note that the first two lines of Table 1 correspond to results that were already known. The running times are from a computer with a 2-GHz processor. The program was written in Java and is available on SourceForge.² For T = { 1, 2, 3, 4, 5} or T = { 5}, the program ran out of memory before obtaining any reasonable result.

Table 1 The terminating executions of our program, each one proving (♣) for that α and T. Tight means convex point sets are known with $\sum\nolimits_{t\in T}{m}_{t} = \alpha n - O(1)$, and abstractly tight means some periodic configuration has $\sum\nolimits_{t\in T}{m}_{t} = \alpha n$, but we could not realize it convexly in the plane

Fig. 8

Two unrealized periodic configurations with ${m}_{3} = \frac{3} {2}n$. Rows and columns are two intervals of vertices, and entry i (resp., ∞) means distance d _i (resp.,  < d ₃)

Fig. 9

An unrealized periodic configurations with ${m}_{2} + {m}_{3} = \frac{9} {4}n$

6 Abstract Tightness

Our computer program can also generate tight examples. In Fig. 8, we show two periodic configurations with ${m}_{3} = \frac{3} {2}n$ with periods of six and eight levels, respectively. (No other example has period lower than 14.) We were not able to embed these examples as convex point sets in the plane, and at the same time we did not disprove that they were embeddable. Based on our attempts, it seems like there is no simple periodic embedding respecting the natural symmetries of the distance configurations. A disproof of realizability could be used in the program to get stronger results. For ${m}_{2} + {m}_{3} = \frac{9} {4}n$, we also have an abstractly tight periodic example that we could not realize (Fig. 9).

7 Future Directions

Our program is essentially a depth-first search; each configuration examined by the program has a unique “parent” configuration from which it was grown. Thus, it would be possible to rewrite the program so as to use a smaller amount of memory and thereby possibly obtain results with smaller α or larger k; and a distributed implementation should also be straightforward.

It would be good to come up with constructions exhibiting better lower bounds. For example, no construction is known where m ₃ ∕ n is asymptotically greater than 4/3.

Our approach constitutes an abstract generalization of the original problem of bounding sums of the m _i ’s in convex point sets. Vesztergombi [7] considered an abstraction as well, using only a subset of the facts we applied here. Can Conjecture 1.1 of Erdős and Moser be violated in either of these abstractions?

Finally, can the functions C, C′ in Lemmas 1.5 and 1.6 be improved?