1 Introduction

1.1 Background

In 1946, Erdős published a paper titled On sets of distances of n point, introducing the problem of finding asymptotic bounds on the minimum number of distinct distances among sets of n points in the plane [7]. This simply stated problem proved to be surprisingly challenging and is now known as the Erdős distance problem. Indeed, the original question was only finally resolved by Guth and Katz in 2015 [15].

Over time, many variations of the problem were introduced: restricting the point sets, studying subsets with no repeated distances, and many other quantities. We study variations of a related problem, introduced by Erdős and Purdy [14]. What is A(n), the minimum number of distinct angles formed by n not-all-collinear points in the plane? Unlike in the distance setting, an extra restriction of non-collinearity is required to prevent the degenerate case of at most two angles. When this problem was proposed, the regular n-gon was conjectured to be optimal (yielding \(n-2\) angles), and a lower bound of \((n-2)/2\) angles was proven for point sets without three collinear points. Since then, the problem and all other analogues of distinct distance problems with angles have gone untouched. We study this problem of distinct angles in many of the settings originally considered for distinct distances, providing exact or asymptotic bounds, depending on the problem. We summarize our results below.

1.2 Summary of Results and Methods

Note that throughout, unlike Erdős, we do not count angles of 0 or \(\pi \) to avoid some degenerate behaviors. This is consistent with the current literature on related repeated angle questions (see, for example [21]).

1.2.1 Erdős Angle Problems

We begin with the most natural extension of the Erdős distance problems to angles: what is the least number of distinct angles determined by n not-all-collinear points in the plane? Given that the known low angle constructions contain obvious structures, such as many points on a line or on a circle, it is natural to also consider the problem over restricted point sets. Our main results in this section are summarized in the following.

  • We provide a construction of a polygon projected onto a line, yielding a point configuration with no four points on a circle admitting \(n-2\) distinct angles, the same as the conjectured optimal regular n-gon.

  • We also provide a point configuration in general position admitting less than \(cn^{{\log _2}7}\) for some constant c, the first nontrivial bound for this problem. The hypercube configuration relies on enumerating classes of triangles equivalent up to edge translation and then projecting onto a generic plane. While [11, 13] also use a projection onto a generic plane for the distance problem analogue, the properties of orthogonal projections are much more convenient for distances. Attempting to directly apply their results fails dramatically due to additional complexity added by angles.

In addition, for completeness, we provide a known upper bound on A(n) of \(n-2\) from the regular n-gon, conjectured by Erdős and Purdy to be the optimal configuration, and a lower bound of n/6 by partial progress towards the Weak Dirac Conjecture of Erdős and Dirac. We also consider similar problems on restricted point sets, as in the distance setting. Under a restriction forbidding three points on a line, we provide bounds on the restricted quantity \(A_{no3l }(n)\) (these were known by Erdős).

1.2.2 The Robustness of Efficient Point Configurations

Having identified efficient point configurations in the polygon and the projected polygon, we ask how resilient they are to perturbation. Erdős investigated a similar question for distances in [10]. We prove combinatorially the surprising result that the regular n-gon with k points perturbed defines O(nk)Footnote 1 angles, so long as all points remain on the circle, and we prove an analogous result for the projected polygon. Consequently, if any constant number of points in a regular polygon are moved to random positions on the circle, the construction still defines O(n) angles (an optimal number asymptotically), even though moving even one point off the circle experimentally gives a super-linear number of distinct angles. In that vein, we provide conjectures about the number of angles in several perturbed optimal configurations in which points may no longer lie exactly on a circle or line.

1.2.3 The Pinned Angle Problem

We subsequently examine the angle equivalent of another prominent Erdős distance problem. What is the smallest k such that every n point configuration has some point determining k distinct distances? This problem remains open in the distance setting for convex configurations of points, and is conjectured to be \(\left\lfloor n/2\right\rfloor \) by Erdős in [7]. An upper bound of \(\left\lfloor n/2\right\rfloor \) is obtained by considering the regular n-gon, and the current best lower bound of \((13/36 + 1/22701) n + O(1)\) is obtained by Nivasch et al. [20].

Denoting the analogous angular quantity allowing any configuration of points as \(\hat{A}(n)\) (with the pinned point as the apex of the angles), we bound it between n/6 and \(n-2\) using results about A(n). This in turn also provides an upper bound on \(\hat{A}_\Sigma (n)\), the sum of the number of distinct angles determined by each point.

1.2.4 Partite Sets

Given a partite set, the question of distances determined between the two sets has been studied by Elekes [6] in the unrestricted setting, but remains unsolved in general. We ask the analogous question in the angular setting: how many angles are defined by a k-partite set, where each point is in a distinct set? We provide low angle configurations in the unrestricted case, establish linear lower and upper bounds on partite sets without three collinear points, and completely solve the problem in a particular case.

1.2.5 Maximal Subsets of Points with Distinct Angles

One prominent variation of the Erdős distance problem asks: what is minimum maximal subset of n points such that no distance is repeated? None of the numerous variants in the distance setting have been fully resolved, although a number of upper and lower bounds have been proven by a variety of authors. For a complete picture of these problems in the distance setting see [1, 2, 12, 14, 18].

We ask the analogous question for angles. We upper bound this configuration in general, showing \(R(n)\le A(n)^{1/3}\). Then, we employ a probabilistic method similar to that in [2] to show a lower bound of \(\Omega (n^{1/5})\).

1.2.6 Higher Dimensions: Lenz’s Construction

Lenz’s construction consists of multiple unit circles in row orthogonal two-dimensional subspaces. We show that, just as it has been for repeated angle problems in higher dimensions and the unit distance problem, Lenz’s construction also provides a good upper bound of \(2\lceil 2n/d \rceil -2\) on \(A_d(n)\), the least number of distinct angles defined by n points in d dimensions (see [1, p. 499]). This construction demonstrates that, for a fixed number of points, increasing the dimension decreases the upper bound on the number of distinct angles dramatically. This behavior aligns with the behavior in the distance setting with the integer lattice. We also provide a higher dimensional upper bound for the maximal subset question.

Table 1 Summary of results
Full size table

We provide a tabular summary of our results in this section for convenience. Each parameter is described informally above, but we formally define each one in its respective section.

We note several other miscellaneous bounds over the course of the paper, but do not include them here because either we only provide an upper or lower bound or they do not fit nicely into the structure of the table. These include: variants of angle sum bounds in Sect. 4, partite set bounds in Sect. 5, and maximal subset bounds in non-general position in Sect. 6, to name a few.

2 Erdős Angle Problems

2.1 Unrestricted Point Sets

We begin by considering the most broad, non-trivial version of the distinct angles problem. This is the version of the problem originally posed by Erdős [14].

Definition 2.1

For a point set \({\mathcal {P}}\subset \mathbb {R}^2\), let \(A({\mathcal {P}})\) denote the number of distinct angles in \((0,\pi )\) determined by points in \({\mathcal {P}}\). Then, let

$$\begin{aligned} A(n) :=\min _{|{\mathcal {P}}|= n} A({\mathcal {P}}), \end{aligned}$$

where \({\mathcal {P}}\) is not all collinear.

We begin by showing \(A(n) = \Theta (n)\) with explicit upper and lower bounds. First, we give an upper bound using the regular polygon:

Lemma 2.2

\(A(n) \le n-2\).

Proof

Consider the point configuration given by the vertices of an n-sided regular polygon. Upon inscribing the polygon in a circle, notice that, for any vertex chosen as apex, the distinct angles with that apex are subtended by arcs of length \(\pi /n\), \(2\pi /n, \ldots , (n-2)\pi /n\). The magnitudes of the distinct angles in the polygon are then half of each of those arclengths. \(\square \)

Remark 2.3

When n is odd, we may alternatively use an \((n-1)\)-gon with an extra point in the center. Adding the center point to an even regular polygon does not increase the number of nonzero angles defined, and so, if \(n = 2m+1\), we achieve a slightly better bound: \(A(2m + 1) \le 2m-2\).

We now leverage progress on the Weak Dirac Conjecture to provide a lower bound on A(n). In 1961, based on a stronger conjecture of Dirac’s, Erdős conjectured in [9] the following.

Conjecture 2.4

(Weak Dirac Conjecture) Every set \(\mathcal {P}\) of n non-collinear points in the plane contains a point incident to at least \(\lceil n/2\rceil \) lines of \(\mathcal {L(P)}\), where \(\mathcal {L(P)}\) is the set of lines formed by points.

While the Weak Dirac Conjecture is open, significant progress has been made. Let \(\ell (n)\) be the largest proven lower bound for the Weak Dirac Conjecture, i.e., every set \(\mathcal {P}\) of n points not on a line in the plane contains a point incident to at least \(\ell (n)\) lines of \(\mathcal {L(P)}\). Then, we have the following.

Theorem 2.5

For \(n > 3\), \(A(n)\ge (\ell (n) - 1)/2\ge n/6\).

Proof

Fix a set \(\mathcal {P}\) of n non-collinear points in the plane. Let \(p \in \mathcal {P}\) be incident to at least \(\ell (n)\) lines of \(\mathcal {L(P)}\). Fix another point \(q\in \mathcal {P}\). Note that for any fixed nonzero angle \(\theta < \pi \), there are exactly two possible lines that r must lie on if \(\angle qpr=\theta \). Since p is incident to \(\ell (n) - 1\) lines without q, p is the apex of at least \((\ell (n) - 1)/2\) distinct angles. Therefore

$$\begin{aligned} A(n) \ge \frac{\ell (n) - 1}{2}.\end{aligned}$$

We have \(\ell (n) \ge \lceil n/3\rceil +1\) from [16]. As such, we have \(A(n) \ge n/6\), as desired. \(\square \)

Notably, this argument is known (see [1, Conj. 10 in 6.2]), but we include it for completeness.

2.2 No Three Collinear Points

Given that any collinear point set defines at most two angles, it is intuitively clear why restricting the number of collinear points might result in interesting behavior. We briefly consider such point sets in this section.

Definition 2.6

Let \(A_{no 3l}(n) = \min _{|{\mathcal {P}}|=n} A({\mathcal {P}})\), where \({\mathcal {P}}\) contains no collinear triples.

Note that the regular n-gon contains no collinear triples, and so as with A(n), we have an upper bound of \(A_{no 3l}(n)\le n-2\). The usual stipulation on this bound holds. See Remark 2.3. Our restrictions on the point sets allow for a stronger lower bound than in the unrestricted case. This bound was known by Erdős but is included for completeness.

Lemma 2.7

For \(n >3\), \(A_{no 3l}(n)\ge (n-2)/2\).

Proof

Fix a point \(p\in {\mathcal {P}}\). As no three points are on a line, p determines \(n-1\) distinct lines with each of the other points. The result follows by fixing another point q and repeating the argument for Theorem 2.5. \(\square \)

We can easily generalize this restriction to no k points on a line. However, the lower bound given by repeating this argument with \(k\ge 4\) points on a line is always weaker than that in Theorem 2.5. Moreover, in those cases the regular polygon remains an upper bound.

2.3 Restricting Cocircularity

Since the regular polygon construction requires many points on a circle, it is natural to wonder how the bounds change when we require that no four points lie on a circle. This setting is not specifically studied in the context of distances but merits special attention for angles given the seeming optimality of the regular n-gon. We provide the following definition.

Definition 2.8

Let \(A_{no4c }(n) = \min _{|{\mathcal {P}}|=n} A({\mathcal {P}})\), where \({\mathcal {P}}\) contains no co-circular quadruples.

We then have the following lemma.

Lemma 2.9

For \(n > 3\), \(A_{no4c }(n) \le n - 2\).

Proof

Consider the vertices of a regular n-gon. Fix a vertex p. Then, if n is even, there is a vertex q directly opposite p. In that case, let \(\ell \) be the line perpendicular to \(\overline{pq}\), containing p. If n is odd, there are instead two vertices of maximal distance from p. In that case, let \(\ell \) instead be the line containing those two vertices. Then, for each vertex r other than p in the regular n-gon, project r onto \(\ell \) at the intersection of \(\overline{pr}\) and \(\ell \). This is the stereographic projection of the points onto \(\ell \) via p. Let the \(n-1\) projected points on \(\ell \) and p define the projected polygon configuration, \(\mathcal {P}\). Note that \(\mathcal {P}\) contains no four cocircular points (Fig. 1).

Fig. 1
figure 1

Projecting regular polygons onto a line

Full size image

We can now count the number of angles in this configuration. Let \(\alpha = \pi /n\), the angle subtended by an arc between consecutive points in a regular n-gon. Note that the angles formed in the case of p being the apex of the angle are exactly the \(n-2\) angles of a regular n-gon, \(i\alpha = i\pi / n\) for \(1\le i\le n-2\).

Next, we count angles of the form \(\angle p q r\) where q and r lie on line \(\ell \). Suppose first that n is even. Then there will be a point \(r_0\) at the center of \(\ell \). Note that if \(\angle p q r\) is acute, then \(\angle p q r = \angle p q r_0\). The other two angles in \(\triangle p q r_0\) are \(i\alpha \) and \(\pi /2\) (for \(1 \le i \le (n-2)/2)\), so

$$\begin{aligned}\angle p q r = \frac{\pi }{2}-\frac{i\pi }{n} = \biggl (\frac{n}{2} - i\biggr )\alpha ,\end{aligned}$$

for \(1 \le i \le (n-2)/2\). Since n is even, these are integer multiples of \(\alpha \). Moreover, since \(1 \le n/2-i \le n-2\), angles of this form are already accounted for in the angles with apex p. Additionally, note that, except for the angle with apex at \(r_0\), which has value \(\pi /2\), accounted for by angles with apex p, all the other angles \(\angle p q r\) possible are the supplements of acute angles of the form \(\angle p q r\), apart from the angle of value \(\pi /n\). Thus, we achieve angles of

$$\begin{aligned}\pi -\frac{(n/2 - i)\quad \pi }{n} = \frac{\pi }{2} + \frac{\pi i}{n},\end{aligned}$$

where \(1 \le i\le (n-4)/2\). All these angles are also accounted for in the case of angles with p as the apex, so, when n is even, we have \(n-2\) distinct angles.

The case of n odd follows nearly identically, although of course there is no center-point on the line. A calculation like in the even case shows that each angle measure achieved with apex on the line is also achieved by an angle with vertex at p off the line, and hence we again have \(n-2\) distinct angles. \(\square \)

Remark 2.10

The projected polygon construction and the regular polygon both give \(n-2\) angles for n points. The former contains collinear points but no four points on a circle, while the latter contains the opposite. Additionally, there are infinitely many such “one point off the line” configurations yielding \(\le cn\) angles, for some c. Fix \(\alpha < \pi /(n-1)\). Fix some p and some line \(\ell \). Space the remaining \(n-1\) points on \(\ell \) such that \(\angle rps = \alpha \) for consecutive r and s on \(\ell \). This configuration forms at most 3n angles in general. We revisit this in Sect. 3.

Note that Theorem 2.5 provides a lower bound of n/6 distinct angles here as well.

2.4 General Position: No Three Points on a Line Nor Four on a Circle

Now that we have illustrated constructions determining O(n) angles that forbid either three points on a line or four points points on a circle, we consider configurations that forbid both. Erdős and others have investigated this problem extensively in the distance setting. While the best known lower bound in the distance setting is trivially \(\Omega (n)\), the best known upper bound is \(n2^{O(\sqrt{\log n})}\) from [11]. In this section we provide a nontrivial upper bound on this quantity in the angle setting.

Definition 2.11

Let

$$\begin{aligned}{A_{gen }(n) :=\min _{|{\mathcal {P}}|=n} A({\mathcal {P}})},\end{aligned}$$

where \({\mathcal {P}}\) is in general position.

We use a construction inspired by the projective construction in [13, Thm. 1] to provide an upper bound. We take higher dimensional hypercubes and project their points down to a generic plane. Unlike with distances, we have very little control over the triangles in the projection. As such, we proceed by very careful combinatorics.

Let \(Q_d\) be the d-dimensional hypercube with vertices of the form \(p=(x_1,x_2,\dots ,x_d)\) and \(x_i=0\) or 1 for each i. For any 2-dimensional plane \(\Pi \) in \(\mathbb {R}^d\), let T be the orthogonal projection of the points in \(Q_d\) onto \(\Pi \). It is possible to choose \(\Pi \) satisfying the following conditions.

  1. 1.

    \(T(p_1)=T(p_2)\) if and only if \(p_1=p_2\), and

  2. 2.

    \(\mathcal {P}:=T(Q_d)\subset \Pi \) is in general position.

In addition, since orthogonal projections are self-adjoint and idempotent, we have

$$\begin{aligned} p_1 - p_2 = p_3 - p_4\quad \Longrightarrow \quad d(T(p_1), T(p_2)) = d(T(p_3), T(p_4)). \end{aligned}$$
(2.1)

Unfortunately, T does not preserve the distance between points in \(Q_d\). That is,

This means two congruent triangles in \(Q_d\) need not be congruent after projection. However, by (2.1) and SSS-congruence, two congruent triangles with equal difference vector edges remain congruent after projection. This inspires the following definition.

Definition 2.12

Given a triangle \(\Delta \) with vertices in \(Q_d\), define the equivalence class \([\Delta ]_{Q_d}\) as the set of all triangles congruent to \(\Delta \) whose vertices lie in \(Q_d\) and edges correspond to (individually) translated copies of the edges of \(\Delta \).

It suffices to characterize the equivalence classes of translated congruent triangles in \(Q_d\) to bound the number of angles in P. We do so in the following lemma.

Lemma 2.13

The number of equivalence classes of triangles in \(Q_d\) is

$$\begin{aligned}\frac{7^d -3^{d+1} + 2}{12}.\end{aligned}$$

Proof

We begin by counting the number of unordered triples of distinct binary k-tuples such that no coordinate of the triple is fixed for all three. By “fixed" we mean equal among all three k-tuples. Let \(a_k\) denote the number of such triples.

At each coordinate in the triple of k-tuples, the possible values for each of the triples are 0 or 1. Since no coordinate of the triples is fixed, each coordinate must either have exactly one 1 or one 0 among the three k-tuples. There are then \((3\,{\cdot }\,2)^k\) ways to choose whether there will be one 1 or one 0 and the choice of tuple for that singleton for each of the k coordinates. This imposes an ordering which we divide out at the end. Now, note that although it is impossible to repeat a k-tuple thrice since no coordinate is fixed, we overcount instances with a repeated k-tuple. A k-tuple can be chosen to repeat twice in \(2^k\) ways and the choice of repeated k-tuple forces the choice of the third k-tuple. Such triples can be ordered in 3 ways. After subtracting off such pairs, the remaining triples are all distinct and thus can be ordered in 3! ways. We have

$$\begin{aligned}a_k = \frac{6^{k} - 3 \cdot 2^k}{6}.\end{aligned}$$

Now we use \(a_k\) to count \(t_k\), the number of triangles in \(Q_d\) with exactly k unfixed coordinates. As there are ways to choose the unfixed coordinates, \(a_k\) ways to choose the values in those unfixed coordinates, and \(2^{d-k}\) ways to choose the values of the fixed coordinates, we get

Finally, we prove that all triangles in the same equivalence class have the same set of fixed coordinates. We also prove that the size of the equivalence class of triangles with a given number of fixed coordinates is constant.

First observe that, given a triangle in \(Q_d\), we may get an equivalent triangle by flipping any combination of its fixed coordinates (from 0 to 1 or vice versa), thereby translating each vertex of the triangle by the same amount. Moreover, if a coordinate is not fixed, then any translation to a equivalent triangle cannot be nonzero in that coordinate as it would then lead to some point having a coordinate that is both nonzero and not one. The only other way to achieve an equivalent triangle is to translate the edges individually (keeping the difference vectors corresponding to them identical, but altering their relative orientations). See Fig. 2. This can happen in at most one way. \(\square \)

Fig. 2
figure 2

Translation equivalent triangles from flipped coordinates

Full size image

Moreover, flipping each coordinate of each of the three points yields a congruent triangle composed of the same difference vectors (by flipping, we mean changing from 0 to 1 and vice versa). This follows from the observation that, if a coordinate in a difference vector is 0, the subtracted coordinates must be equal and remain equal under swapping each coordinate. If a coordinate is 1 or \(-1\), it will swap sign but still be the same vector. Thus, we have that the size of the equivalence class of each triangle with k unfixed coordinates in a \(Q_d\) is exactly \(2^{d-k + 1}\). Moreover, all triangles in the equivalence class have exactly k unfixed coordinates. Putting this all together, we have that the number of equivalence classes of triangles in \(Q_d\) is

The above follows from standard binomial formula identities. \(\square \)

Since triangles in the same equivalence class are congruent under the projection from \(Q_d\) to a specially chosen generic plane, Lemma 2.13 provides an upper bound of \(O(7^d)\) distinct angles on point configurations in general position with \(2^d\) points. To establish this result for n not a power of two, pick the least d such that \(n < 2^d\) and apply the upper bound to a subset of n vertices in \(Q_d\). This proves the following theorem.

Theorem 2.14

\(A_{gen }(n) = O(n^{\log _{2}7})\).

3 The Robustness of Efficient Point Configurations

Before we consider several variants of this problem, we discuss a very natural question: how far can point sets stray from our best constructions (regular polygons and projected polygons) while still being “near-optimal?” In the distance setting, a point set is called near-optimal if it admits \(O(n/\sqrt{\log n})\) angles, like the \(\sqrt{n} \times \sqrt{n}\) integer lattice. Erdős asked if such sets have lattice-like structure, containing \(\Omega (n^{1/2})\) points on a line. The question has gone unsolved even after replacing 1/2 by any \(\epsilon > 0\). For some partial results related to this problem, see [22,23,24], in which the authors bound the number of points on various algebraic curves in near-optimal point sets. Formally, we have the following definition.

Definition 3.1

Let \(\mathcal {P}_1\), \(\mathcal {P}_2\), \(\ldots \) \(\subset \mathbb {R}^2\) be a sequence of point configurations, \(|\mathcal {P}_n|=n\). Then \(\mathcal {P}_n\) is near-optimal if \(A(\mathcal {P}_n) = O(n)\).

For example, the sequence of point configurations of regular n-gons is near-optimal. Perhaps surprisingly, these configurations are reasonably robust to point perturbation. We begin by studying points on a circle in a way reminiscent of a regular n-gon.

Proposition 3.2

For a fixed \(k \ge 0\), let \(\mathcal {S}_n^k\) be the collection of n points on a circle with \(n-k\) points forming a regular \((n-k)\)-gon and the remaining k placed arbitrarily. Then

$$\begin{aligned}\max _{\mathcal {P} \in \mathcal {S}_n^k}A(\mathcal {P}) = \Theta (nk).\end{aligned}$$

Proof

Fix a configuration \({\mathcal {P}} \in S_n^k\). Since points in \({\mathcal {P}}\) lie on a circle, all its angles are incident angles. Thus the number of distinct angles is bounded by the number of distinct arc lengths. We divide the set of arcs into three cases. Suppose an arc is the minor one formed between \(p,q \in {\mathcal {P}}\). We then have the following cases.

  1. 1.

    Both p, q are on the polygon. There are at most \(2(n - k)k\) distinct arc lengths of this form.

  2. 2.

    Neither of p, q are on the polygon. Then, they are among the k arbitrarily placed points. There are at most \(2\left( {\begin{array}{c}k\\ 2\end{array}}\right) = k^2-k\) distinct arc lengths of this form.

  3. 3.

    We have p is on the polygon and q is not. There are at most \(2(n-k) k=2nk-2k^2\) distinct arc lengths of this form.

Then, in total, \({\mathcal {P}}\) determines at most \(2nk - k^2 + n -2k - 2\) angles. Since \(k\le n\), this quantity is O(nk).

We show that this bound is tight. Choose the k points to be placed at multiples of \(2\pi \) between \(2\pi (n-k-1)/(n-k)\) and \(2\pi \) such that all arcs formed with the added point are iteratively not admitted among the points in the configuration. Then there are \(n-k-2\) arcs between the point at \(2\pi (n-k-1)/(n-k)\) and the other non-zero polygonal points, moving clockwise about the circle. Notably, they can be extended by 1 to k arcs. By the choice of these arcs, for any length rational arc chosen, all the extensions by 1 to k arcs are distinct. Thus, at least \((n-k-2) k=\Omega (nk)\) distinct angles are formed (as the ends of the arc can be used as the end points of an angle with 0 as the apex). \(\square \)

From this, it follows that such configurations are near-optimal for any k constant in n.

We now discuss a related, more challenging problem. Let \(\mathcal {T}_n^k\) be the collection of n point configurations having \(n-k\) points on a circle and no circle containing more. Denote by T(n) the maximum quantity \(k \le n/2\) satisfying

$$\begin{aligned}\min _{\mathcal {P} \in \mathcal {T}_n^k} A(\mathcal {P}) = \Theta (n).\end{aligned}$$

What can be said about the value of T(n)? We restrict k to \(n - k = \Omega (n)\) in order to avoid cases that reduce to configurations with a negligible number of points on a circle.

Consider a new point at the center of a regular n-gon. When n is even, the new point generates no new angles (see Remark 2.3). When n is odd, it generates exactly \(\lceil n/2\rceil \) additional angles. To see this, say \(n=2m+1\). One new angle of \(4m\pi /({2m+1})\) is from the angle whose apex is at the new point and the ends at the original n-gon. Another n more angles of \(i\pi /n-\pi /(2n)\) for \(1\le i\le n\) are from those with the new point as an end point; they are equivalent to the original arcs on the n-gon with half of the \(2\pi /n\) arc cut out.

Thus, \(T(n) \ge 1\). We conjecture this bound to be tight and this point in the center is the only way to achieve it.

Conjecture 3.3

\(T(n) = 1\).

The aforementioned optimal point configuration, the projected polygon, has \(n-1\) points be on a line. To what extent can we perturb this configuration while remaining near-optimal?

Proposition 3.4

For a fixed \(k \ge 0\), let \(\mathcal {L}_n^k\) be the collection of planar n-point configurations with \(n-k\) (including the off-line point) in the projected polygon construction from Lemma 2.9 and the remaining k placed on the line arbitrarily. Then

$$\begin{aligned}\max _{\mathcal {P} \in \mathcal {L}_n^k} A(\mathcal {P}) = \Theta (nk).\end{aligned}$$

Proof

We may divide the possible angles into four cases. Observe an angle \(\angle pqr\) in the following cases.

  • Say q is the point off the line, and p, r are both projected points. Then the number of such angles is bounded by the number of angles in the projected polygon construction \(n-k-2\).

  • Say q is the point off the line, and neither of p, r are projected points. Then the number of angles in this case is bounded by \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) = (k^2-k)/2\).

  • Say q is the point off the line, p is a projected point, and r is not (without loss of generality). Then the number of such angles is this bounded by \((n-k-1) k\).

  • Say q is on the line. Then all nontrivial \(\angle pqr\) have one leg along the line and the other at the point off the line. Thus, for each q on the line, there are at most two possible angles, and they are supplementary amongst themselves. Then the number of these angles is bounded by \(2(n-1)\).

Then in total we O(nk) distinct angles formed. Now we show this bound is tight. Choose the k points to be placed following the rightmost point on the line such that the angles they form with the point off the line as the center are all unique (we can do this iteratively by the infinitude of the real line). Then, by construction, there are at least

distinct angles in the configuration, counting only angles with apex the point off the line. \(\square \)

From this, it follows that such configurations are near-optimal for any k constant in n.

Now, we consider the quantity analogous to T(n). Let \(\mathcal {M}_n^k\) be the collection of all n point configurations having \(n-k\) points on a line and no lines containing more. Denote by M(n) the maximum k satisfying

$$\begin{aligned}\min _{\mathcal {P} \in \mathcal {M}_n^k} A(\mathcal {P}) = \Theta (n).\end{aligned}$$

What can be said about the value of M(n)? It is immediate that \(M(n) \ge 1\) by the projected polygon. In addition, from Remark 2.10, there are many other near-optimal configurations in \(\mathcal {M}_n^k\). Consider a new point that is the original point off the line reflected over the line. It generates O(n) additional angles. Thus, \(M(n) \ge 2\). We conjecture this bound to be tight and the only pair of points to achieve this are those symmetric about the line.

Conjecture 3.5

\(M(n) = 2\).

4 The Pinned Angle Problem

We now pivot to a variant originally considered in the context of distinct distance problems. Among n points in the plane, in the worst case, what is the maximum number of distinct angles with apex at some “pinned” point? For example, see [17, Cor. 6] for the original problem for distances.

Definition 4.1

For a point set \({\mathcal {P}}\) and a point p in it, let \(A_p({\mathcal {P}})\) denote the number of distinct angles in \((0,\pi )\) formed in \({\mathcal {P}}\) with p as the apex. Then, let

$$\begin{aligned}{\hat{A}(n)} :=\min _{|{\mathcal {P}}|=n} \max _{p \in P}A_p(\mathcal {P}),\end{aligned}$$

where \(\mathcal {P}\) is a not-all-collinear planar point set.

Theorem 4.2

We have \(\hat{A}(n) = \Theta (n)\).

Proof

Regular polygons give an upper bound of \(n-2\). Let \(\ell (n)\) be the current best lower bound on the Weak Dirac Conjecture (see Conjecture 2.4). Using the same logic as Theorem 2.5, this gives a lower bound of \((\ell (n) - 1)/2\). This is at least n/6, completing the proof. \(\square \)

This use of the Weak Dirac Conjecture is known (see [1, Conj. 10, Sect. 6.2]). A related classical question for distinct distances is determining the average number of distinct distances admitted by a pinned point. We present its analogy for angles here.

Definition 4.3

Let

$$\begin{aligned}\hat{A}_{\Sigma }(n) :=\min _{|{\mathcal {P}}|=n} \sum _{p \in P}A_p(\mathcal {P}),\end{aligned}$$

where \(\mathcal {P}\) is a not-all-collinear planar point set.

Theorem 4.4

We have \(\hat{A}_{\Sigma }(n) \le 3n-6\).

Proof

The projected polygon construction from Lemma 2.9 has one point off the line as the apex of \(n-2\) distinct angles. All the points on the line, apart from the endpoints, are the apex of exactly two non-degenerate angles. These contribute another \(2n-4\) to the sum. Hence, \(\hat{A}_{\Sigma }(n) \le 3n-6\). \(\square \)

We also have the following for \(\hat{A}'_{\Sigma }(n)\), this quantity forbidding three collinear points.

Theorem 4.5

We have \({\hat{A}'_{\Sigma }(n)}= \Theta (n^2)\).

Proof

Since no three points are on a line, we can repeatedly remove points and apply the bound from Theorem 2.5. This gives

$$\begin{aligned}\sum _{i = c}^n \frac{i}{6} = \Omega (n^2).\end{aligned}$$

To get the upper bound, use the fact that every point of a regular n-gon is the apex of exactly \(n-2\) distinct angles. \(\square \)

5 Partite Sets

Another well-known variant of the distinct distances problem is that of distances between points in partite sets. See [6], for example. We introduce a similar problem for angles. We make heavy use of the best lower bound of the Weak Dirac Conjecture on n points, \(\ell (n)\), in this section. As a reminder, from [16], we have \(\ell (n)\ge \lceil n/3\rceil \).

Definition 5.1

Given bipartite \(\mathcal {P},{\mathcal {Q}}\subset \mathbb {R}^2\), denote by \(A(\mathcal {P}, \mathcal {Q})\) the number of distinct angles in \((0,\pi )\) whose apex lies in a different set than its two end points. Where \(\mathcal {P} \cup \mathcal {Q}\) is not all collinear, let

$$\begin{aligned} A(m,n) :=\min _{\begin{array}{c} |{\mathcal {P}}|=m\\ |{\mathcal {Q}}|=n \end{array}}A(\mathcal {P}, \mathcal {Q}). \end{aligned}$$

For simplicity, assume \(m \le n\). We begin by providing upper bounds on both unrestricted and restricted point sets.

Lemma 5.2

We have \(A(m,n) \le m\).

Proof

We utilize the projected polygon construction from Lemma 2.9. Assign the point off the line, q, to be in \(\mathcal {Q}\) and the m leftmost points on the line in \(\mathcal {P}\). Notably, the points in \(\mathcal {P}\) are all within the left half of the line. Now, the angles of the form \(\angle p_1qp_2\), the angles with apex q, form the angles \(i\pi /(n+m)\) for \(1\le i\le m-1\). Let r be the rightmost point on the line. From Lemma 2.9, we have two cases for the the angles of the form \(\angle qp_ir\). If \(n+m\) is even, they form the angles

$$\begin{aligned}\frac{\pi }{2} - \frac{j\pi }{n+m}\end{aligned}$$

for \((n-m)/2\le j\le (n+m-2)/2\) (or, for \(n = m\), we have all such angles for \(j\ge 1\) and an angle of \(\pi /2\) for \(p_i\) the orthogonal projection of q onto the line). In the case \(n+m\) odd, the angles \(\angle qp_ir\) are

$$\begin{aligned}\frac{\pi }{2} - \biggl ( \frac{j\pi }{n+m} - \frac{\pi }{2(n+m)}\biggr )\end{aligned}$$

for \((n-m + 1)/2\le j\le (n+m-1)/2\). Namely, these angles are computed by completing the angles of the right triangle containing q, \(p_i\), and the orthogonal projection of q. Substituting the ranges of the angles for both, we find that the only angles in the configuration are \(l\pi /(n+m)\) for \(1\le l\le m\), implying the result. \(\square \)

Note that this result implies that no unrestricted lower bound in terms of \(n + m\) can exist.

Next, we provide an upper bound on the case of no three collinear points in \(\mathcal {P}\) or \(\mathcal {Q}\) (the union may have three collinear points).

Lemma 5.3

We have \(A_{no3l }(m,n) \le n - 2\).

Proof

Let \(\mathcal {P}\) form a subset of vertices of a regular n-gon of size m and \(\mathcal {Q}\) the vertices of a regular n-gon, both inscribed in the same circle. The bipartite angles formed in this configuration are all incident angles subtended by arcs of the size subtending angles in a regular n-gon. Thus, the distinct angles formed in this configuration are a subset of the angles of a regular n-gon, implying the result from Lemma 2.2. \(\square \)

Now, we provide a lower bound in the restricted case of no three collinear points within sets \(\mathcal {P}\) or \(\mathcal {Q}\).

Lemma 5.4

We have \(A_{no3l }(m,n)\ge \lfloor (n-1)/2\rfloor \).

Proof

Fix a point \(p\in {\mathcal {P}}\) to be an apex and a \(q\in {\mathcal {Q}}\) to be a non-apex point. By the argument in Lemma 2.7, since no three points are collinear, at most two of each of the remaining \(n-1\) points in \({\mathcal {Q}}\) can form the same angle with \(\overline{pq}\) with apex p. However, one other point in the \({\mathcal {Q}}\) can be collinear to p and q, not contributing any angle, yielding

$$\begin{aligned} \lceil (n-2)/ 2 \rceil = \lfloor (n-1)/2 \rfloor . \square \end{aligned}$$

Corollary 5.5

We have \(A_{no3l }(m,n) \ge \lfloor ((m+n)/2-1)/2\rfloor \).

This allows us to completely solve this problem in the case of \(m = 1\).

Lemma 5.6

We have \(A_{no3l }(1, n) = \lfloor (n-1)/2 \rfloor \).

Proof

Let \(\mathcal {Q}\) be the vertices of a regular n-gon. Inscribe these vertices in a circle. Let the singular point p in the other set be the center of the circle. Then the number of angles of the form \(\angle q_1pq_2\) for \(q_1,q_2\in {\mathcal {Q}}\) is \(n/2-1\) for n even and \((n-1)/2\) for n odd by counting subtending arclengths. This yields \(A(1,n)\ge \lfloor (n-1)/2\rfloor \). Combining with Lemma 5.4, we achieve the desired result. \(\square \)

We now consider k-partite sets.

Definition 5.7

Let \(n = \sum _{i=1}^{k} r_i\). Let \(A(r_1,r_2, \dots , r_k)\) denote the minimum number of distinct angles determined by point sets in \(\mathbb {R}^2\) of respective sizes \(r_1, \dots , r_k\) with each of the following stipulations:

  • each angle is formed by three points in distinct sets,

  • \(r_1 \ge r_2 \ge \ldots \ge r_k\) and \(k \ge 3\), and

  • not all points are collinear.

We begin with upper bounds on unrestricted and restricted point sets.

Lemma 5.8

We have \(A(r_1, r_2, \ldots , r_k) \le 2(n - r_1 -1)\).

Proof

Let \(S=n-r_1\). We follow a similar proof to Lemma 5.2. Let the n points be in an n point projected regular polygon configuration. Let the point off the line, p, be in the \(r_1\) set. Let the leftmost \(r_k\) points be in the \(r_k\) set, the next leftmost in the \(r_{k-1}\) set, and so on, with the remaining rightmost points on the line in the \(r_1\) set. Note that all angles must include p. The angles \(i\pi /n\) for \(1\le i\le S-1\) are exactly those formed by angles with p as the apex. We assume without loss of generality that S is at most n/2 as, from Lemma 2.9, there are \(n-2\) total angles in the configuration. From the proof of Lemma 5.2, the angles with apex p and the acute angles with apex some point in an \(r_i\) set for \(i>1\) overlap completely, yielding \(S-1\) angles (note that the rightmost apex has no endpoint for an angle opening to the right, thus the minus one). Moreover, since we may assume \(S \le n/2\), all of \(S-1\) supplemental angles are obtuse. Thus, they do not overlap at all, yielding the desired bound of \(2S-2\) angles. \(\square \)

As before, we are unable to provide a lower bound only in terms of n, as, from the above, there are configurations with large \(r_1\) which exhibit very few distinct angles.

We next provide an upper bound on \(A(r_1, r_2, \ldots , r_k)\) in the restricted case of no three points on a line in each set (and, in this case, globally).

Lemma 5.9

We have \(A_{no3l }(r_1,r_2, \ldots , r_k) \le n-\max (2, r_k + 1)\).

Proof

Place the n points as the vertices of a regular n-gon. Assign the first \(r_1\) to the first partite set, the next \(r_2\) to the second, and so on, continuing clockwise about the circle circumscribing the polygon. Then, since all points are on a circle, the angles in the configuration each correspond exactly to the arc subtending them. But, by construction, the arcs subtending angles may contain at most \(n-\max (3,r_k+2)\) points. As such, the distinct angles in this configuration are exactly \(i\pi /n\) for \(1 \le i\le n - \max (2, r_k + 1)\). This implies the desired bound. \(\square \)

When we forbid three points on a line globally, we have a stronger bound than Lemma 5.4 for \(r_{k-1}\) and \(r_k\) small.

Lemma 5.10

\(A_{no3l }(r_1,r_2,\dots ,r_k)\ge \lceil (n-r_{k-1}- r_k)/2\rceil \).

Proof

Fix a point in the \(r_k\)-set and a point in \(r_{k-1}\)-set. Now, since there are no three collinear points, the points in the other sets make each angle with these points at most twice. Thus, \(A_{no3l }(r_1,r_2,\dots ,r_k)\ge \lceil ({n-r_{k-1}-r_k})/2\rceil \). \(\square \)

6 Maximal Subsets of Points with Distinct Angles

6.1 Definitions and Upper Bounds

Another variant of the Erdős distinct distance problem is the following: given n points in a plane, how many points must we remove so that the remaining points determine no repeated distances? This problem has been studied extensively in the context of distances, with varying restrictions on the points set [2, 12, 15, 18]. We study an analogous problem for angles, proving the first nontrivial lower and upper bounds.

Definition 6.1

For a point set \({\mathcal {P}}\), let \(R(\mathcal {P})\) be the maximum size of \(\mathcal {Q}\subseteq \mathcal {P}\) such that \({\mathcal {Q}}\) determines no repeated angle. Then, let

$$\begin{aligned}R(n) :=\min _{|\mathcal {P}| = n} R({\mathcal {P}}),\end{aligned}$$

where the minimum is taken over non-collinear point sets \(\mathcal P\) of n points.

In general, configurations with a low number of angles provide a reasonable upper bound for R(n).

Lemma 6.2

Let \(\mathcal {P} \subseteq \mathbb {R}^2\) be a planar point configuration of n points with no three collinear points. Then

$$\begin{aligned}R(\mathcal {P}) \le (2A(\mathcal {P}))^{1/3}.\end{aligned}$$

Proof

Fix \(\mathcal {P} \subseteq \mathbb {R}^2\), a planar point configuration of n points with no three collinear points. Then, the subsets of the point configuration determine at most \(A(\mathcal {P})\) distinct angles. Moreover, as there are no three collinear points in \(\mathcal {P}\), any subset S of \(\mathcal {P}\) admits not necessarily distinct angles. Thus, if a subset S has no repeated angles, it must be that

This implies \(|S| \le (2A(\mathcal {P}))^{1/3}\). \(\square \)

Using Lemma 2.2 and Theorem 2.14 we get the following bounds.

Corollary 6.3

We have

$$\begin{aligned}R(n), R_{no3l }(n)= O(n^{1/3}),\qquad R_{no4c }(n), R_{gen }(n)= O\bigl (n^{({\log _2}{7})/3}\bigr ).\end{aligned}$$

Remark 6.4

Notably, Lemma 6.2 does not provide an especially strong bound for \(R_{no4c }(n)\), since it does not apply to the construction from Lemma 2.9.

6.2 A Probabilistic Lower Bound on Maximal Distinct Angle Subsets in General Position

Now we provide a lower bound on \(R_{gen }(n)\). The proof is in many ways reminiscent of Charalambides’s proof of this for distances (see [2, Proposition 2.1]). To proceed, we define and bound several quantities.

Definition 6.5

For a point set \(\mathcal {P}\), let

$$\begin{aligned} Q_3(\mathcal {P})&:=\{ (p,q,r) \in \mathcal {P}^3:p,q,r distinct ,\ \angle pqr=\angle qrp\},\\ Q_4(\mathcal {P})&:=\{ (p,q,r,s) \in \mathcal {P}^4:p,q,r,s distinct ,\ \angle pqr= \angle pqs, \\&\qquad \quad \left. \angle pqr = \angle rsp, \angle pqr= \angle qrs, or \angle pqs = \angle qrs \right\} ,\\ Q_5(\mathcal {P})&:=\{ (p,q,r,s,t) \in \mathcal {P}^5:p,q,r,s,t distinct ,\ \angle pqr=\angle sqt, \\&\qquad \quad \left. \angle pqr= \angle qst, \angle pqr = \angle rst\right\} ,\\ Q_6(\mathcal {P})&:=\{(p,q,r,s,t,u):p,q,r,s,t,u distinct, \ \angle pqr = \angle stu \}. \end{aligned}$$

Remark 6.6

\(Q_3(\mathcal {P})\) is the collection of pairs of equal angles overlapping at all three points. It is also the collection of isosceles triangles, over counting up to a factor of 3. \(Q_4(\mathcal {P})\) is the collection of pairs of equal angles overlapping at two points. The first case is when the angles share an apex and one endpoint. The second case is when they share both endpoints. The third case is when their apex vertices are endpoints for the other angle (and since that gives two points overlapping, the other two endpoints do not overlap). The fourth and final case is when the endpoints of one angle are the apex and an endpoint of the other. See Fig. 3. \(Q_5(\mathcal {P})\) is the collection of pairs of equal angles overlapping at one point. The first case is when the angles share an apex. The second case is when the apex of one angle is an endpoint of the other. The third case is when an endpoint of one angle is also an endpoint of the other. See Fig. 4. \(Q_6(\mathcal {P})\) is the collection of pairs of equal angles without overlaps. These cases are all encompassing as, for each number of repeated points, it involves some matching of angle endpoints/apexes to angle endpoints/apexes. These cases are an exhaustive list of such matchings.

Fig. 3
figure 3

Four point repeated angle configurations

Full size image
Fig. 4
figure 4

Five point repeated angle configurations

Full size image

For that which follows, we assume the point configuration is in general position in the plane. That is, no three points in the configuration are on a line, and no four are on a circle. The argument fails without restricting to sets with no four points on a circle, as remarked afterward.

Definition 6.7

For each \(3 \le i \le 6\), let

$$\begin{aligned}q_i(n) :=\max _{|\mathcal {P}|=n} |Q_i(\mathcal {P})|,\end{aligned}$$

where \(\mathcal {P}\) is a planar point set in general position.

Lemma 6.8

We have \(q_3(n) = O(n^{7/3}).\)

Pach and Sharir show the number of isosceles triangles in the plane is \(O(n^{7/3})\) [21]. We count such triangles twice in \(Q_3(n)\) if the triple forms an isosceles triangle and thrice if it forms an equilateral triangle. This makes no difference asymptotically.

Lemma 6.9

We have \(q_4(n) = O(n^3)\).

Proof

Let \(\mathcal {P}\) be n points in general position. We show that there are at most \(cn^3\) quadruples in each case of \(Q_4(\mathcal {P})\), for some constant c, implying the desired bound. In each of the cases below, we use the same naming convention as in Definition 6.5. Our case numbering also correspond to those in Fig. 3. Fix p, q, and r, which may be done in less than \(n^3\) ways.

Case 1::

We count the number of ways to choose s such that \(\angle pqs = \alpha = \angle pqr\). Since \(\alpha \) is determined by p, q, and r, then s must be on a ray from q forming angle \(\alpha \) with \(\overline{qp}\). There are at most two such rays, with one being \(\overrightarrow{qr}\). Since the points are in general position, s cannot be on \(\overrightarrow{qr}\). On the other ray, there are at most one such point s. So, there are at most \(n^3\) quadruples in this case.

Case 2::

Let C be the circle determined by the three points and \(C'\) be its reflection across the segment \(\overleftrightarrow {pr}\). Let \(\ell \) be the perpendicular bisector of segment \(\overleftrightarrow {pr}\). We show that any point s forming \(\angle psr = \alpha \) has to lie on the outer perimeter of the figure \(C \cup C'\). First, assume point s lies in the same half space as q with respect to the line \(\overleftrightarrow {pr}\) and the same half space as r with respect to \(\ell \). Let \(s'\) be the point projected onto C projected from s along \(\overleftrightarrow {ps}.\) By comparing the triangles \(\triangle psr\) and \(\triangle ps'r\), we have that \(\angle ps'r = \angle psr\) iff \(\angle prs = \angle prs'\). Therefore, it must be that \(s = s'\). The previous argument can be performed when s is on the other side of \(\ell \), by projecting along \(\overleftrightarrow {rs}\) instead. However, in either of these cases, \(s \in C\), which violates the restriction of no four points on a circle. That is, the second diagram in Case 2 of Fig. 3 is impossible given our restrictions. This argument can be repeated when s is on the other side of \(\overleftrightarrow {pr}\), but instead on circle \(C'\). Since there are already two points on this circle, there is most one choice for s in this case. Hence, there are at most \(n^3\) quadruples in this case.

Case 3::

We choose s such that \(\angle qrs = \alpha \). Since \(\alpha \) is determined by p, q, and r, s must be on a ray from r forming angle \(\alpha \) with \(\overline{qr}\). There are at most two such rays. Each such ray contains at most two point, yielding at most two options for s. So, there are at most \(2n^3\) quadruples in this case.

Case 4::

This case is extremely similar to Cases 1 and 3. We choose s such that \(\angle sqr=\alpha =\angle pqr\). As before, there are at most two lines which intersect \(\overline{qr}\) at q at an angle of \(\alpha \). Each line contains at most one additional point in \(\mathcal {P}\), yielding an upper bound of \(2n^3\) quadruplets in this case.

Since each four cases can occur in at most \(cn^3\) ways, for \(c = 2\), then \(q_4(n) = O(n^3)\), as desired. \(\square \)

Remark 6.10

If four points on a circle is allowed, then we instead get \(q_4(n) = \Theta (n^4)\), crippling the proof. This can be achieved with a regular n-gon. Fix two of its vertices as the overlapping endpoints. They partition the vertices of the polygon into major and minor arcs, with the major one having least \((n-2)/2\) vertices. Then, any choice of two vertices from the major arc will yield a configuration as in Case 2. Thus there are \(\Omega (n^4)\) such configurations in this case. As such, forbidding four points on a circle is necessary.

Lemma 6.11

We have \(q_5(n) = O(n^4)\).

Proof

Let \({\mathcal {P}}\) be n points in general position. As in Lemma 6.9, we show that each case of \(Q_5({\mathcal {P}})\) occurs at most \(cn^4\) times, for constant c, implying the desired bound.

Case 1::

Fix p, q, r,  and s, done in less than \(n^4\) ways. As in Lemma 6.9, there are at most two choices for t, yielding at most \(2n^4\) options for this case.

Case 2::

This follows exactly as Case 1, yielding a bound of at most \(2n^4\) options for this case.

Case 3::

This follows exactly as Cases 1 and 2, yielding a bound of at most \(2n^4\) options for this case.

The above casework implies the result. \(\square \)

Lemma 6.12

We have \(q_6(n) = O(n^5)\).

Proof

Fix n points in general configuration and from it points p, q, r, s, and t, in less than \(n^5\) ways. There are then exactly two ways to choose u so that \(\angle pqr = \angle stu\). Then u must lie on one of two lines containing t. Since there are no three collinear points, there are at most two choices of u. The result follows. \(\square \)

Theorem 6.13

We have \(R_{gen }(n) = \Omega (n^{1/5})\).

Proof

Let \({\mathcal {P}} \subset \mathbb {R}^2\) be a point set of size n and let \({\mathcal {Q}} \subset {\mathcal {P}}\) be a set in which each element of \({\mathcal {Q}}\) is chosen independently and uniformly from \(\mathcal {P}\) with probability p. The probability p will be specified below.

Each occurrence of some configuration from \(\bigcup _{i=3}^6 Q_i\) in \({\mathcal {Q}}\) generates a repeated angle. Let \({\mathcal {Q}}' \subset {\mathcal {Q}}\) be the points remaining after one point from each configuration is removed. Indeed, \({\mathcal {Q}}'\) is free of repeated angles and \(|{\mathcal {Q}}'| \le R_{gen }({\mathcal {P}})\). Taking expectations we obtain

$$\begin{aligned}\mathbb {E}[|{\mathcal {Q}}'|] \ge \mathbb {E}[|{\mathcal {Q}}|] - \sum _{i=3}^6 \mathbb {E}[|Q_i|] = pn - \sum _{i=3}^6 p^i q_i(n).\end{aligned}$$

Using Lemmas 6.8–6.12, there exist some constant \(c > 1\) such that for all \(n > N\) for some N, we get

$$\begin{aligned}\mathbb {E}[|{\mathcal {Q}}'|]\ge np-c (p^3 n^{7/3} - p^4 n^3 - p^5 n^4 - p^6 n^5).\end{aligned}$$

Setting \(p = c^{-1}n^{-4/5}\), for \(n > N\) we have

$$\begin{aligned}\mathbb {E}[|{\mathcal {Q}}'|]\ge c^{-1}n^{1/5} - c^{-2}n^{-1/15} - c^{-3}n^{-1/5} - c^{-4} - c^{-5}n^{1/5}= \Omega (n^{1/5}).\end{aligned}$$

By the first moment method, there exists a subset of size \(\Omega (n^{1/5})\) without repeated angles. \(\square \)

7 Higher Dimensions: Lenz’s Construction

In general, the minimum number of distinct angles among n points in \(\mathbb {R}^d\) should decrease as lower dimensional spaces can be embedded in higher dimensional ones. In this section, we provide a construction that demonstrates that this is indeed the case.

Definition 7.1

Let \(A_d(n)\) be the minimum number of distinct angles on three points determined by n non-collinear points in d-dimensional space.

In dimension d for \(d \ge 4\), Lenz gives a construction for a low upper bound on \(A_d(2n)\), as described in [8].

Construct a unit regular n-gon centered at the origin in the \(x_1 x_2\)-plane and another unit regular n-gon centered at the origin in the \(x_3x_4\)-plane. This is Lenz’s construction. Now, we upper bound the number of distinct angles in this configuration. From Lemma 2.2, there are \(n-2\) distinct angles between points in the same n-gon. There are then two other cases to consider. We may assume without loss of generality the points lie in four dimensions, as the extra dimensions make no difference in the computation. Let the three points be

  1. 1.

    \(x = (\cos \theta , \sin \theta , 0, 0),\)

  2. 2.

    \(y = (\cos \psi , \sin \psi , 0, 0)\),

  3. 3.

    \(z = (0,0, \sin \phi , \cos \phi )\),

where \(\theta , \psi , \phi \in \{2\pi i/n : 0 \le i \le n-1\}\) and \(\theta \ne \psi \).

Case 1::

The endpoints are in the same polygon In this case, z is the apex of the angle. By trigonometric identities, we have \(\langle x-z,y-z\rangle =1 + \cos (\theta - \psi )\), and \(\Vert x-z\Vert =\Vert y-z\Vert = \sqrt{2}\). We compute \(\alpha = \angle xzy\) using

$$\begin{aligned}\alpha =\arccos \frac{\langle x-z, y - z\rangle }{\Vert x-z\Vert \cdot \Vert y-z\Vert }=\arccos {\frac{1+\cos (\theta - \psi )}{2}}.\end{aligned}$$

We know \(\theta - \psi = 2\pi k/n\) for nonzero \(-n+1\le k\le n-1\). Since cosine is an even and periodic with \(2\pi \), the image of \(\cos (\theta - \psi )\) are exactly \(\cos (2\pi k/n)\) for \(1 \le k \le \lceil (n-1)/2\rceil \). Because arccosine is injective on \([-1,1]\), it yields exactly \(\lceil (n-1)/2\rceil \) values of \(\alpha \).

Case 2::

The endpoints are in different polygons In this case, we may assume x is the apex of the angle. By trigonometric identities, we have \(\langle y-x, z - x\rangle =1-\cos (\theta - \psi )\), and \(\Vert y-x\Vert =\sqrt{2}\sqrt{1-\cos (\theta -\psi )}\). We compute \(\alpha = \angle yxz\) using

$$\begin{aligned}\alpha =\arccos \frac{\langle y-x,z-x\rangle }{\Vert y-x\Vert \cdot \Vert z-x\Vert }=\arccos \frac{\sqrt{1 - \cos (\theta - \psi )}}{2}.\end{aligned}$$

Now, since in both cases arccosine is injective on the domain, these \(\alpha \) are duplicate angles if and only if

$$\begin{aligned}&1 + \cos (\theta - \psi ) = \sqrt{1 - \cos (\theta - \psi )}\\&\quad \iff \cos (\theta - \psi )(\cos (\theta - \psi ) + 3) = 0\\&\quad \iff \cos (\theta - \psi )=0. \end{aligned}$$

Since we are only considering \(\theta -\psi =2\pi k/n\) for \(1\le k\le \lceil (n-1)/2\rceil \), this occurs only for \(k = n/4\). Hence, we overcount between these two cases exactly once if and only if \(4\,{\vert }\,n\).

As a result of these computations, we have the following lemma.

Lemma 7.2

The number of distinct angles in Lenz’s construction with 2n points is at most \(2n - 4\) if \(4\,{\vert }\,n\) and at most \(2n - 3\) otherwise.

We can extend Lenz’s construction to get even better bounds on the minimum number of distinct angles in higher dimensions. In dimension \(d\ge 6\), we may now have three unit regular n-gons in disjoint pairs of coordinates. Crucially, adding the third n-gon adds at most one angle, formed by points on three different polygons. As the distance between points is \(\sqrt{2}\), three points always yield an equilateral triangle and an angle of \(\pi /3\).

If the dimension allows, you may then add even more n-gons in disjoint coordinates. After the third, the additional ones do not add any additional distinct angles. Since subsets of the vertices of n-gons have a subset of the angles, you can make point sets of any size using Lenz-like constructions.

Theorem 7.3

Fix \(d \ge 2\). For \(n > d+1\), we have that

figure a

For \(3 \le n \le d+1\), we have

$$\begin{aligned} A_d(n) = 1. \end{aligned}$$
(6.4)

Proof

The lower bound of 2 for (6.1), (6.2), follows from the fact that the d-dimensional simplex has exactly \(d+1\) vertices and it is the largest point configuration in d-dimensional space with all points equidistant. As such, in each of these cases, there are at least two distances between the points and thus more than one distinct angle.

Now note that \(\lceil {n}/{\lfloor d/2\rfloor }\rceil \ge 3\) if \(n>d+1\). (6.2) and then follow from Lemma 7.2 and the above discussion of generalized Lenz’s constructions. In fact, in special cases for \(d \ge 6\) we get a slightly lower bound. For \(n/\lfloor d/2\rfloor \) a multiple of 3 or 4, we may reduce the bound by 1 (and 2 if a multiple of 12).

For (6.2) we also may reduce the bound by 1 if \(\lceil n/2\rceil \) is a multiple of 4. For (6.1), for \(d = 2\) or 3, this follows from Lemma 2.7 by using a regular n-gon. For (6.4), note that for \(n = d+1\), we can arrange the points to form the vertices of a d-dimensional regular simplex, yielding all points equidistant from one another. This means all angles are \(\pi /3\) as they are the angle of an equilateral triangle. We can take any subset of the vertices of such a simplex to get the same result. \(\square \)

Crucially, this construction implies that no uniform lower bound greater than 4 for a fixed n and varying d can exist. From this, we can also give an upper bound on the higher dimensional version of the quantity R(n) from Definition 6.1.

Definition 7.4

Let \(R_d(\mathcal {P})\) be the maximum size of any \(\mathcal {Q}\subseteq \mathcal {P} \subseteq \mathbb {R}^d\) such that \({\mathcal {Q}}\) defines no angle twice. Over the set of all n non-collinear points, define

$$\begin{aligned}R_d(n) = \min _{|\mathcal {P}| = n} R_d({\mathcal {P}}).\end{aligned}$$

We again make use of a variation of Lenz’s construction to provide an upper bound.

Proposition 7.5

We have

$$\begin{aligned}R_d(n) \le \biggl (2\biggl \lceil \frac{n}{\lfloor d/2 \rfloor } \biggr \rceil - 4\biggr )^{\!1/3}.\end{aligned}$$

Proof

We use the variation of Lenz’s construction from Lemma 7.2. Distribute the points as evenly as possible amongst the largest possible regular polygons in disjoint pairs of dimensions as normal. Note that there cannot be points on three different circles as they form an equilateral triangle. Also note that there cannot be two points on one circle and one on another as that forms an isosceles triangle. As such, we may apply Lemma 6.2 to the largest polygon to achieve our desired bound. \(\square \)

Remark 7.6

For , there is a two distance set of that many points (see [19, Lemma 3.1]). Thus, in such sets all but two points must be removed, yielding \(R_d(n) =2\) for .

8 Future Work

Future research may take distinct angles problems in a number of new directions:

  • We have shown that \(n/6\le A(n)\le n-2\). Further, we have identified two non-collinear point configurations which define exactly \(n-2\) angles, the regular n-gon and its projection onto the line. Whether these are in fact the optimal configurations is open (though they are conjectured to be so), and even if they are, there may be others which also define \(n-2\) angles. Note that we have observed that, excluding angles of 0 and \(\pi \), one may add a point to the center of an even sided regular polygon without adding any angles. See Remark 2.3. This does not contradict Erdős’s initial conjecture in [14], as he included 0 angles.

  • Prove Conjecture 3.3 and 3.5 regarding optimal point configurations.

  • One may similarly improve our bounds on \(A_{no 3\ell (n)}\), \(A_{no4c }\), and \(A_{gen }\). In general position, an optimal construction has yet to be conjectured.

  • The question of distinct angles in higher dimensional space has yet to be explored deeply, and one may generalize any of our bounded quantities to the general setting. Further research may also investigate higher analogues of angles like three-dimensional solid angles.

  • We bounded \(R_{gen }(n)\), the size of the largest distinct-angle subset of an n point configuration. Alternatively, by viewing the point configuration as a complete graph on n vertices, we may define \(R_{gen }(n)\) as the number of vertices in the largest complete distinct-angle sub-graph. Instead of removing vertices, one might ask about removing edges until all angles left are distinct.