Points in General Position

Many Discrete Geometry problems study planar point sets in general position. Most commonly, this definition refers to point sets with no three collinear points and no four cocircular points (that is, no circle contains four points of the set). A few examples of such problems:

  • What is the minimum number of distinct distances that are spanned by a set of n  points in general position?
  • What is the minimum number of convex k  -gons determined by n  points in general position?
  • For even n  , what is the maximum number of distinct ways in which one can cut a set of n  points in general position by a line into two halves, each of cardinality n/2  ?
  • What is the maximum number of points that can be placed on an n \times n  grid so that no three points are collinear. What happens when we also forbid four cocircular points?
Randomly choosing n  points from the plane will lead to a set in general position, but this set is unlikely to have any interesting extremal structure. For example, we expect such a set to span many distinct distances, and it is not clear why such a set should span few convex k  -gons. Problems such as the ones above ask for point sets that are in general position while also having some kind of structure. I often find it useful to have examples of such point sets as part of my “Discrete Geometry toolkit”. I am familiar with two very different constructions of such sets. This post describes these two constructions. If you are familiar with additional constructions, do let me know!

Construction 1: Subsets of the integer lattice. Our first construction involves finding a large subset of an n \times n  section of the integer lattice that is in general position. The basic idea for this construction seems to originate from Erdős (for example, see this paper of Roth), although we will follow a later variant of Thiele.

For a prime p  , we consider the point set

{\cal P} = \left\{\left(t,t^2 \mod p\right)\ :\ 0\le t <p/4 \right\}.

Note that {\cal P}  is a set of \lfloor p/4\rfloor  points from a p\times p  section of the integer lattice. We will now show that {\cal P}  does not contain three collinear points or four cocircular points.

An example of the first construction, created by Gábor Damásdi.

Three points (x_1,y_1),(x_2,y_2),  and (x_3,y_3)  are collinear if and only if

\begin{vmatrix} 1 & x_1 & y_1 \\ 1 & x_2 & y_2 \\ 1 & x_3 & y_3 \end{vmatrix} = 0.

It is not difficult to check that for three points (t_1,t_1^2),(t_2,t_2^2),(t_3,t_3^2)  , we get

\begin{vmatrix} 1 & t_1 & t_1^2 \\ 1 & t_2 & t_2^2 \\ 1 & t_3 & t_3^2 \end{vmatrix} = (t_2-t_1)(t_3-t_2)(t_3-t_1).

For distinct integers t_1,t_2,t_3  , this determinant is clearly nonzero. When we also have that 0\le t_1,t_2,t_3 < p  , this determinant is also not a multiple of the prime p  . Thus,

\begin{vmatrix} 1 & t_1 & (t_1^2 \mod p) \\ 1 & t_2 & (t_2^2 \mod p) \\ 1 & t_3 & (t_3^2 \mod p) \end{vmatrix} \neq 0.

We conclude that no three points of {\cal P}  are collinear. We can use a similar argument for the case of cocircular points. Four points (x_1,y_1),(x_2,y_2),(x_3,y_3),  and (x_4,y_4)  are cocircular if and only if

\begin{vmatrix} 1 & x_1 & y_1 & x_1^2 +y_1^2\\ 1 & x_2 & y_2 & x_2^2 +y_2^2\\ 1 & x_3 & y_3 & x_3^2 +y_3^2\\ 1 & x_4 & y_4 & x_4^2 +y_4^2 \end{vmatrix} = 0.

(One can think of this test is as lifting the four points to the paraboloid defined by z=x^2+y^2  in {\mathbb R}^3  , and checking if the four lifted points are coplanar. It is known that the intersections of the paraboloid with planes are exactly the lifting of circles to the paraboloid.)

Taking the points (t_1,t_1^2),(t_2,t_2^2),(t_3,t_3^2),(t_4,t_4^2)  , we get

\begin{vmatrix} 1 & t_1 & t_1^2 & t_1^2 +t_1^4\\ 1 & t_2 & t_2^2 & t_2^2 +t_2^4\\ 1 & t_3 & t_3^2 & t_3^2 +t_3^4\\ 1 & t_4 & t_4^2 & t_4^2 +t_4^4 \end{vmatrix} = (t_1+t_2+t_3+t_4)\prod_{1\le j<k \le 4}(t_k-t_j).

Since 0\le t_1,t_2,t_3,t_4 < p/4  , we have that t_1+t_2+t_3+t_4  is not a multiple of p  . Assuming that the four integers are distinct, none of the elements of the product is a multiple of p  . Repeating the above argument, we get that no four points of {\cal P}  are cocircular.

Now that we know that the above construction is in general position, let us mention a few of its applications:

  • Erdős and Purdy asked for the size of the largest subset of the n\times n  integer lattice with no three points on a line and no four on a circle. The above construction provides the current best lower bound for this problem.
  • Erdős, Hickerson, and Pach asked whether there exists a planar set of n  points in general position that spans no parallelograms and still determines o(n^2)  distinct distances. Dumitrescu provided a positive answer to this question by using the above construction.
  • The Heilbronn triangle problem asks for the smallest \Delta(n)  such that every set of n  points in the unit square determine a triangle of area at most \Delta(n)  . Erdős used a variant of the above construction to produce one of the first non-trivial lower bounds for the problem.
Construction 2: Projection from a hypersphere. In our first construction, the point set has some structure since it is a subset of a p\times p  section of the integer lattice. The structure in our second construction also originates from a lattice, although in a very different way. This construction comes from a paper of Erdős, Füredi, Pach, and Ruzsa, and seems to be influenced by earlier ideas of Behrend.

For a positive integer d  , consider the section of the d  -dimensional integer lattice

{\cal L} = \left\{(x_1,\ldots,x_d)\in {\mathbb Z}^d :\ 0\le x_1,\ldots,x_d <2^d \right\}.

We claim that there exists a hypersphere around the origin that contains many points of {\cal L}  . First, note that |{\cal L}| = 2^{d^2}  . We also note that the distance between a point x\in {\cal L}  and the origin is \sqrt{x_1^2+\cdots+x_d^2}  . Every such distance is the square root of an integer between zero and d\cdot 2^{2d}  . That is, the points of {\cal L}  determine at most d\cdot 2^{2d}  distinct distances from the origin. By the pigeonhole principle, there exists a distance \delta  such that at least 2^{d^2}/(d\cdot 2^{2d})=2^{d(d-2)}/d  points are at distance \delta  from the origin. In other words, the hypersphere S_\delta  centered at the origin and of radius \delta  contains at least 2^{d(d-2)}/d  points of {\cal L}  . Let {\cal P}'  be a set of exactly n=2^{d(d-2)}/d  of these points. To recap, {\cal P}'  is a set of n  points with integer coordinates on the hypersphere S_\delta  .

Let h  be a generic two-dimensional plane in {\mathbb R}^d  (or, if you prefer, a random plane). Let {\cal P}  be the set of points that are projections of the points of {\cal P}'  on h  . It is not difficult to verify that, on a generic plane, no two points of {\cal P}'  are projected to the same point. Similarly, when projecting four points on a generic plane, we do not expect the projections to be cocircular. That is, we may assume that {\cal P}  consists of n  distinct points, no four which are cocircular.

It is not true that the projections of any three points on a generic plane are not collinear. If three points are collinear in {\mathbb R}^d  , then their projections on every plane would remain collinear. This is why we take the points of {\cal P}'  to be on the hypersphere S_\delta  : Since every line intersects the hypersphere in at most two points, no three points of {\cal P}'  are collinear.

Now that we constructed a set {\cal P}  of n  points in general position, it remains to see what structure {\cal P}  has. For this purpose, we return to the lattice {\cal L}  in {\mathbb R}^d  . It is not difficult to verify that the set of vectors determined by pairs of points of {\cal L}  is

\left\{(x_1,\ldots,x_d)\in {\mathbb Z}^d :\ -2^d\le x_1,\ldots,x_d <2^d \right\}.

That is, the number of distinct vectors determined by pairs of points of {\cal L}  is O\left(2^{d(d+1)}\right)  . Since {\cal P}' \subset {\cal L}  , the number of distinct vectors determined by pairs of points of {\cal P}'  is also O(2^{d(d+1)})  . Let p_1,p_2,p_3,p_4\in {\mathbb R}^d  satisfy p_1-p_2=p_3-p_4  , and let \pi(\cdot)  be a projection from {\mathbb R}^d  to a two-dimensional plane. Then \pi(p_1)-\pi(p_2)=\pi(p_3)-\pi(p_4)  . This implies that the number of distinct vectors determined by pairs of points of {\cal P}  is also O(2^{d(d+1)})  .

From the definition n=2^{d(d-2)}/d  we obtain \log n = d(d-2) - \log d  , which in turn implies 2^{d(d+1)} = O(n2^{\sqrt{\log n}})  . Thus, the number of distinct vectors determined by pairs of points of {\cal P}  is O\left(n2^{\sqrt{\log n}}\right)  . (If you are not used to such expressions, note that for every \varepsilon>0  we have n2^{\sqrt{\log n}} = O\left(n^{1+\varepsilon}\right)  .) This property shows that {\cal P}  has a strong structure. For example, it immediately implies that the number of distinct distances determined by {\cal P}  is O\left(n2^{\sqrt{\log n}}\right)  (and similarly for the number of distinct directions). That is, a set in general position can still determine a relatively small number of distinct distances.

Additive Energy of Real Point Sets

Over the years, more and more interactions between Discrete Geometry and Additive Combinatorics are being exposed. These include results such as the Green–Tao ordinary lines theorem and Solymosi’s sum-product bound. One reason for this connection is that both fields study the structure and symmetries of various objects (such as sets of points or subsets of additive groups). In this post I will discuss one of the simplest connections between the two fields — studying the additive energy of a set of points in a real space {\mathbb R}^d  . The main goal of the post is to present two open problems that involve the additive energy of such sets. I heard one of these problems from Nets Katz and the other from Ciprian Demeter. In future posts we might discuss more involved interactions between the two fields.

Ciprian Demeter and Nets Katz.

Continue reading

(More) Local Properties that imply Many Distinct Distances

Last year I wrote a post about a distinct distances problem that involves local properties of the point set. Specifically, let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set {\cal P} \subset {\mathbb R}^2  of n  points, such that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances. For more details and examples, see the original post.

A while ago I noticed another nice bound for this set of problems. Unfortunately the proof is very simple, which prevents it from being published in a “decent” journal. I’ve been trying to push it further, so far without success. Perhaps someone else would see how this idea can be extended.

As discussed in the previous post, Fox, Pach, and Suk proved that for every k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+6\right) = \Omega(n^{8/7-\varepsilon}).

A simple argument shows that for every k\ge 4  we have

\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2\right) = \Omega(n^2).

Our interest in this post lies in between these two bounds. That is, what happens between the values \binom{k}{2}-k+6  and \binom{k}{2}- k/2 +2  . I am only aware of one previous result in thie range: Erdős and Gyárfás showed that \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega(n^{4/3})  . We will now prove a stronger result.

Theorem 1. For every k\ge 8  that is divisible by four, we have

\phi\left(n,k,\binom{k}{2}- 3k/4 +3\right) = \Omega_k(n^{4/3}).

Continue reading

Distinct Distances for Sets with no Repeated Bisectors

This post is about a distinct distances problem which I think is quite interesting. As we shall see, solving this problem would also lead to significant progress in characterizing point sets with a small number of distinct distances. Recall that a perpendicular bisector of two points p,q\in {\mathbb R}^2  is the line that consists of the points a  satisfying |pa|=|qa|  (where |pa|  is the distance between a  and p  ). For brevity, we will simply refer to these as bisectors.


We say that a set {\cal P}  of n  points in {\mathbb R}^2  has no repeated bisectors if for every four distinct points a,b,c,d\in {\cal P}  the bisector of a  and b  is not identical to the bisector of c  and d  (that is, the configuration in the above figure is forbidden).

Conjecture. Let {\cal P}  be a set of n  points in {\mathbb R}^2  with no repeated bisectors. Then for any \varepsilon>0  the points of {\cal P}  determine \Omega(n^{2-\varepsilon})  distinct distances, .

Update July 2017: The conjecture is false, as pointed out by Cosmin Pohoata. A known construction is a counterexample, and I should be ashamed for not observing this on my own. Erdős, Füredi, Pach, and Ruzsa constructed a set of n  points in {\mathbb R}^2  with O(n^{1+\varepsilon})  distinct distances for any \varepsilon >0  and no four points on a common circle. Having a repeated bisector requires having four points on a circle, so there are no repeated bisectors. Oh well…

For some initial intuition, consider the point sets that determine a small number of distinct distances. I am only aware of two types of configurations that yield O(n)  distinct distances: the vertices of a regular n  -gon and lattices.


We can also play a bit with these examples. For example, by taking two regular n  -gons whose vertices are on two concentric circles, or by taking n  evenly spaced points on a line (that is, an n\times 1  lattice). All of these examples have a significantly large amount of repeated bisectors.

So far I only managed to find a set with no repeated bisectors and O(\frac{n^2}{\sqrt{\lg n}})  distinct distances. From the other direction, I can only show that every such set determines \Omega(n)  distinct distances. This is unfortunate, since a stronger bound for this problem would lead to a breakthrough in characterizing planar point sets that determine a small number of distinct distances. Below I describe how this can be done, and also how to obtain simple lower and upper bounds for this problem.

Continue reading

Local Properties that imply Many Distinct Distances

Jacob Fox, Janos Pach, and Andrew Suk just placed this paper on arXiv. The paper seems very nice, but unfortunately for Ben Lund, Frank de Zeeuw, and myself, it contains a result that is almost identical to one that we had but did not yet publish. Instead of sulking alone in the dark, in this post I describe the problem and our result.

Jacob Fox, Janos Pach, and Andrew Suk.

Let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set of n  points {\cal P} \subset {\mathbb R}^2  with the property that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances.

For example, the value of \phi(n,3,3)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any isosceles triangles (including degenerate triangles with three collinear vertices). Since no isosceles triangles are allowed, every point determines n-1  distinct distances with the other points of the set, and we thus have \phi(n,3,3) = \Omega(n)  . Erdős observed the following upper bound for \phi(n,3,3)  . Behrend proved that there exists a set A  of positive integers a_1<a_2<\cdots<a_n  , such that no three elements of A  determine an arithmetic progression and that a_n < n2^{O(\sqrt{\log n})}  . Therefore, the point set {\cal P}_1 = \{(a_1,0), (a_2,0),\ldots, (a_n,0)\}  does not span any isosceles triangles. Since {\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}  and D({\cal P}_2)< n2^{O(\sqrt{\log n})}  , we have \phi(n,3,3) < n2^{O(\sqrt{\log n})}  .

In the same paper, Erdős derived the more general bound

\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n).

As Fox, Pach, and Suk point out, a result by Sarkozy and Selkow implies the slightly stronger (with \varepsilon  depending on k  )

\phi\left(n,k,\binom{k}{2}-k+4+\log k\right) = \Omega(n^{1+\varepsilon}).

We are now ready to state our result. The result of Fox, Pach, and Suk is identical up to the +5  being replaced with +6  . While there are some similarities between the two proofs, they do not seem to be identical.

Theorem 1. For every even k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+5\right) = \Omega(n^{8/7-\varepsilon}).

Continue reading

Point Sets with Few Distinct Distances

Ben Lund and I were sitting in a small Korean restaurant and discussing an old conjecture of Erdős. Erdős suggested that if a set of n  points in {\mathbb R}^2  spans O(n/\sqrt{\log n})  distinct distances, then the vertices of this set must span either a square or an equilateral triangle. Presumably, this conjecture was made because the two best-known examples of sets with O(n/\sqrt{\log n})  distinct distances are n\times n  subsets of the integer lattice and of the triangular lattice. (By the triangular lattice, I mean the vertices of a tiling of the plane with equilateral triangles.)

intGrid grid3
A subset of the integer lattice and a subset of the triangular lattice.

A subset of the integer lattice spans many squares and no equilateral triangles, while a subset of the triangular lattice spans many equilateral triangles and no squares. We can create various similar configurations by taking one of these two configurations and then applying rotations, uniform scaling, and taking subsets. Such configurations still contain squares or equilateral triangles. Ben and I were wondering whether we can find additional configurations, which are not “related” to the integer lattice or to the triangular lattice. Surprisingly, we managed to find a large family of other configurations. Moreover, many of these configurations do not span any squares or triangles, disproving Erdős’ conjecture. We then discovered that these configurations were already known, and appeared in a paper by Moree and Osburn. I guess that this is another case of lack of communication between different mathematical communities…

Continue reading

Distinct Distances: Open Problems and Current Bounds

If you have been following this blog for a while, you might have noticed that I have been slowly surveying the various open problems that are related to distinct distances, and the best known bounds for them. I think that my survey is now in a decent shape, so I uploaded it on arXiv.

For this occasion, I wish to mention an open problem concerning surfaces in {\mathbb R}^3  . It is far from being one of the main problems of this subfield. However, since currently no non-trivial bounds are known for it, it seems like a good problem for a student or for someone who wishes to start working on distinct distances problems.

Recall that in bipartite distinct distances problems we have two sets of points {\cal P}_1  and {\cal P}_2  , and are interested only in distinct distances that are spanned by pairs of {\cal P}_1\times{\cal P}_2  (i.e., distances between points from different sets). For simplicity, in this post we assume that both sets are of cardinality n  . One example of such a result, by Pach and de Zeeuw, is that if each of the two point sets is on a planar curve that contains no lines or circles, then the number of distinct distances between {\cal P}_1  and {\cal P}_2  is \Omega\left(n^{4/3}\right).

In {\mathbb R}^d  , the similar (yet non-bipartite) case where one point set is placed a curve was studied by Charalambides and by Raz, Sharir, and Solymosi. However, nothing non-trivial is known for point sets on two-dimensional surfaces. That is, consider, in {\mathbb R}^3  , the minimum number of distinct distances between a set {\cal P}_1  of n  points on a two-dimensional surface S_1  , and a set {\cal P}_2  of n  points on a two-dimensional surface S_2  .

Before we properly formulate any questions for this scenario, let us first consider some examples. First, consider the case where S_1  and S_2  are non-parallel planes in {\mathbb R}^3  . In this case there exist two orthogonal lines \ell_1,\ell_2  such that \ell_1 \subset S_1  , \ell_2 \subset S_2  , and \ell_1 \cap \ell_2  is a point on S_1 \cap S_2  . We can place the two sets of points on \ell_1,\ell_2  such that the number of distinct distances between the two sets is \Theta(n)  (e.g., see Section 3 of the survey). The same bound can be obtained between two spheres and between a sphere and a plane (in both cases by placing the points on two parallel circles).

A slightly better bound can be obtained in the case where S_1  and S_2  are parallel planes. In this case we can place a \sqrt{n}\times\sqrt{n} subset of the integer lattice on each of the planes. For example, we may assume that the planes are defined by z=0  and z=1  , and that the points of the two sets are

{\cal P}_1 \cup {\cal P}_2 = \left\{ (x,y,z) | 1 \le x,y \le \sqrt{n} \quad \text{ and } \quad 1 \le z \le 2 \right\}.

A variant of Erdős’ analysis of the planar lattice (e.g., see Section 2 of the survey) implies that the number of distinct distances between the two sets is O(n/\sqrt{\log n})  .

Unlike the planar case, it is not immediately clear whether the above examples are tight. For example, the n^{1/3}\times n^{1/3} \times n^{1/3}  integer lattice determines only O\left(n^{2/3}\right)  distinct distances. This leads to the following conjecture.

Conjecture. Given a set {\cal P}_1  of n  points on a two-dimensional surface S_1  , and a set {\cal P}_2  of n  points on a two-dimensional surface S_2  , both in {\mathbb R}^3  , the number of distinct distances between the two sets is \Omega(n/\sqrt{\log n})  (or at least \Omega(n^{1-\varepsilon})  ?).

Assuming that the conjecture is true, we have the following natural question.

Problem. Characterize which pairs of surfaces S_1,S_2  can yield O(n)  distinct distances. Moreover, provide a lower bound for the minimum number of distinct distances for the case of any other pair of surfaces.

This problem formulation is motivated by aforementioned result of Pach and de Zeeuw for the case of points on two planar curves, where the only “exceptional” cases are when the two curves contain parallel lines or concentric circles, and then the number of distinct distances can be \Theta(n)  . For any other pair of curves, the number of distinct distances is \Omega(n^{4/3})  .

The limitations of the Elekes-Sharir framework

In a previous series of posts, we discussed the Elekes-Sharir(-Guth-Katz) framework. By using this framework, Guth and Katz derived the bound D(n)=\Omega(n/\log n)  for the Erdős distinct distances problem (where D({\cal P})  denotes the number of distinct distances that are determined by pairs of points from \cal P  , and D(n) = \min_{|{\cal P}|=n}D({\cal P})  ). The best known upper bound is D(n)=O(n/\sqrt{\log n})  , which leaves a gap of \Theta(\sqrt{\log n})  . The common belief is that D(n)=\Theta(n/\sqrt{\log n})  , and thus, that there should exist a way to strengthen the analysis of the lower bound.

In this post we briefly discuss the existence of point sets that determine \Theta(n/\sqrt{\log n})  distinct distances, for which the Elekes-Sharir framework can only yield a bound of \Omega(n/\log n)  . Such configurations imply that to improve the Guth-Katz lower bound while by relying on the Elekes-Sharir framework, one either has to make a drastic change in the framework, or to separately handle the family of “problematic” point configurations. This observation is one of the results in a recent paper by Javier Cilleruelo, Micha Sharir, and myself. Embarrassingly, I did not notice that a similar result was added to the third version of Guth and Katz’s paper. The aforementioned paper still contains other interesting results.

Javier Cilleruelo and Micha Sharir.

Let us first recall the lower bound construction of Erdős. This construction relies on the following theorem from number theory.

Continue reading

Few distinct distances implies no heavy lines or circles

This post is about another new distinct distances result, which was just uploaded to arXiv. It is a paper by Zahl, de Zeeuw, and myself.

Joshua Zahl and Frank de Zeeuw.

Let us start by asking what are currently the main challenges in studying distinct distances (you’re welcome to share your thoughts about this in the comments). It seems to me that most people consider the main challenge to be the d  -dimensional variant of the distinct distances problem (see the second half of this post for more details). I would like to suggest that another main problem is characterizing the point sets that determine a small number of distinct distances.

I already wrote about the characterization problem in this post, and I will now repeat a few sentences from there. So far, all the known point sets that determine a sublinear number of distinct distances are \sqrt{n}\times\sqrt{n}  lattices, possibly with some minor changes. For example, any \sqrt{n}\times\sqrt{n}  subset of the integer lattice determines O(n/\sqrt{\log n})  distinct distances, and so does a \sqrt{n}\times\sqrt{n}  subset of the following triangular lattice:

\displaystyle \left\{a\cdot (1,0) + b\cdot (1/2, \sqrt{3}/2) \ \mid \mbox{ for any } a,b\in{\mathbb Z} \right\}.

intgrid grid3

Over 25 years ago Erdős asked whether every point set that determines O(n/\sqrt{\log n})  distinct distances “has lattice structure”. However, even after so many years and Guth and Katz’s breakthrough, we still hardly know anything about this problem. A proof by Szemerédi (unpublished and originally described in a 1975 paper by Erdős) implies that for every n  -point set \cal P  , there exists a line \ell  that contains \Omega(\sqrt{\log n})  points of \cal P  . It had been conjectured by Erdős that this bound can be improved to \Omega(n^{1/2})  , though no improvement had been discovered in the decades that passed. It is an interesting challenge to prove even the case of \Omega(n^{\varepsilon})  points on a line.

In the new paper, we study the “complementary” problem of proving that there must not be a line with too many points on it.

Theorem 1. (S’, Zahl, and de Zeeuw) Let \cal P  be a set of n  points that determine o(n)  distinct distances. Then no line contains \Omega(n^{7/8})  points of \cal P  .

Continue reading

Distinct distances from three points

This post is about the recent paper of Sharir and Solymosi concerning distinct distances from three points.


Let {\cal P}_1  and {\cal P}_2  be two sets of points in the plane, and let D({\cal P}_1,{\cal P}_2)  denote the number of distinct distances that are determined by a point of {\cal P}_1  and a point of {\cal P}_2  . The case where the points of each set are on a distinct line was considered in this paper by Sharir, Solymosi, and myself, and a generalization to the case where the points are on two general constant-degree curves was recently derived by Pach and de Zeeuw. Instead of restricting the point sets to curves, we now consider the case where {\cal P}_1  contains only a constant number of points (and |{\cal P}_2|=n  ).

If {\cal P}_1  contains a single point p  , then by putting the points of {\cal P}_2  on a common circle around p  , we obtain D({\cal P}_1,{\cal P}_2) = 1  .


Next, consider the case where {\cal P}_1  contains two points p,q  . Let D=\{d_1,d_2,\ldots\}  be the set of distinct distances between points of {\cal P}_1  and points of {\cal P}_2  . Consider the |D|  circles that are centered around p  and have a radius from D  , and the |D|  circles that are centered around q  that have a radius from D  . Since D  consists of all the distances between {\cal P}_1  and {\cal P}_2  , every point of {\cal P}_1  must be contained in an intersection of two circles. Let r  be the distance between p  and q  and let D=\{d_1,d_2,\ldots\}  be a set of \sqrt{n}  distinct distances, all larger than r  and smaller than 2r  . In this case, the two sets of circles intersect in exactly 2n  points. We can arbitrarily choose n  of these intersection points to be the points {\cal P}_2  . This implies that when |{\cal P}_1|=2  it is possible to have D({\cal P}_1,{\cal P}_2) = O(\sqrt{n})  .


To see that this bound is tight, assume for contradition that D({\cal P}_1,{\cal P}_2) = o(\sqrt{n})  and notice that there are o(n)  intersection points between the two sets of circles, which makes it impossible for the n  points of {\cal P}_2  to be intersection points. A nice corollary of this is that for every set \cal P  of n  points in the plane, there exists at most one point p\in{\cal P}  such that p  determines o(\sqrt{n})  distinct distinct distances with the points of {\cal P}\setminus\{p\}  .

The case where {\cal P}_1  contains three points p_1,p_2,p_3  is the first non-trivial case. As before, we can equivalently consider three families of circles, each centered around a different p_i  , and find an upper bound for the number of points that are contained in three circles.

Continue reading