Minimum number of different distances defined by a finite number of points

Minimum number of different distances defined by a finite number of points Albujer, A. aand Segura Gomis, S. a aDepartamento de An´alisis Matem´atico, Universidad de Alicante, Campus de San Vicente del Raspeig, E-03080-Alicante, Spain Abstract We study the minimum number of different distances defined by a finite number of points in the following cases: a) we consider metrics different from the euclidean distance in the plane, b) we consider the euclidean distance but restricted to subsets of the plane of special interest, c) we consider other topological surfaces: the cylinder and the flat torus. All these results extend those obtained by Erd¨os and other mathematicians for the euclidean distance in the plane. Key words: distances, metrics, integer lattice, flat torus, cylinder 1. Introduction In 1946 [4] Erd¨os posed the following problem: let f(n) denote the minimum number of distinct distances that can occur among the n(n−1) 2dis- tances between ndistinct points in the plane; what can we know about f(n)? For small values of nit is easy to compute f(n) and many times the number f(n) is attained for different configurations. Let us see the first examples. ............... . . . . . . . . . . . . . ................... . . . . . . . . . . . . . . ................ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . .............. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............... . . . . . . . . . . . . . . . f(3) = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . ........ f(4) = 2 . . . . . . . .. . . . . . . .............. .............. . . . . . . . . . . . . .. . . . . . . . . . . . . . f(5) = 2 f(6) = 3 Erd¨os obtained asymptotic estimates for f(n). The first asymptotic estimate was cn1/2< f(n)< c n (ln n)1/2 Email addresses: [email protected] (Albujer, A.), [email protected] (Segura Gomis, S.). Erd¨os conjectured that f(n)> cn1−εfor each ε > 0 and offered 500$ for a proof or a disproof. Erd¨os conjecture is still open. The last improvement was made by Szemer´edi (1992) who proved that f(n)> cn4/5([2]). f(n) can be investigated in dimension Rd with d > 2. For d= 3 the best bounds are cn4/3log log n < f(n) ([5]) and f(n)< n3/2+o(1) ([3]). Recently Braß([1]) determined f(n) exactly in dimension d= 4. There are also bounds for general dimensions. The aim of this communication is to extend Erd¨os problem to other ambient spaces. a) First we consider metrics different from the euclidean distance in the plane. b) Then we consider also the euclidean distance but restricted to subsets of the plane of special interest (points of the integer lattice and points of rational coordinates). c) Finally we consider Erd¨os problem in other topological spaces. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry 2. Erd¨os problem considering arbitrary distances in the plane In the plane we can define many distances. Let us recall that a distance in the plane is a map d:R2×R2→R such that i) d(x, y)≥0, d(x, y) = 0 iff x=y ii) d(x, y) = d(y, x) iii) d(x, z)≤d(x, y) + d(y, z) An interesting way to define a metric in the plane is as follows. Let us define the gauge function g(K, x) of a closed, convex set Krelative to an origin 0 as g(K, x) = inf{λ:x∈λK, λ > 0} It is easy to prove that if Kis a proper convex body and 0 ∈intK, the function m(x, y) = g(K, x −y) almost defines a distance in the plane. The condition that is violated is the symmetry condition m(x, y) = m(y, x) that holds only if Kis centrally symmetric. So a closed, centrally symmetric, convex set K with 0 ∈intK defines a metric ([7]). All these metrics generate the euclidean topology. In the particular case that the set Kthat induce this metric is a square of the type h(p, 0),(0, p),(−p, 0),(0,−p)i, then we obtain the famous taxi-cab metric which is also known as the Manhattan metric. This metric is particularly relevant for our analysis. The taxi-cab metric can also be defined as dT((x1, y1),(x2, y2)) = |x2−x1|+|y2−y1| We are going first to estimate the minimum number of distinct distances with the taxi-cab metric. We begin showing in table 1 that the taxi-cab metric provides different values for f(n) than those values attained with the euclidean metric. f(n) Euclidean metric Taxi-cab metric 3 1 1 4 2 1 5 2 2 6 3 2 7 3 2 Table 1 Some values of f(n) with the taxi-cab metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . f(3) = f(4) = 1 f(5) = ... =f(9) = 3 Now we are going to estimate precisely f(n). Lemma 1 Considering the taxi-cab metric f(n)≤ ⌈√n⌉−1 PROOF. Let Lbe the lattice generated by the vectors (1,1) and (1,-1). Let pbe an integer number and let Kpbe the point set determined by Kp= L∩h(0,0),(p−1,−(p−1)),(2(p−1),0),(p−1, p− 1)i. Consider K⌈√n⌉. This set contains at least n points since ⌈√n⌉ · ⌈√n⌉ ≥ √n·√n=n, so we can always choose npoints in K⌈√n⌉. As the points in K⌈√n⌉determine ⌈√n⌉ − 1 different distances among them, f(n)≤ ⌈√n⌉−1  This estimate is not only an upper bound but a precise determination of the minimum number of distinct distances: Lemma 2 Considering the taxi-cab metric f(n)≥ ⌈√n⌉−1 PROOF. We are going to give a sketch of the proof: We consider the “metric circumferences”, which in our case are square-shaped, as the locus of the points that are at distance rfrom a point p∈R2: S(p, r) = {x∈R2:dT(p, x) = r} Now we are going to locate the maximum number of points who define at most mdistances among March 25-26, 2004 Seville (Spain) them. As we are always dealing with a finite number of points, there would be at least two points a,bsuch that the distance between them is the maximum possible. All the others points should be located in the intersection of m“metric circumferences” centered at aand m“metric circumferences” centered at b. If we do not want to increase the number of different distances, the radius of these “metric circumferences” are {id(a,b) m}m i=1. There are two possible situations: i) All the “metrics circumferences” intersect properly. In this case as they have the pseudodisc property (there are at most two proper intersections for each pair of pseudodiscs), then we obtain that the maximum number of possible points is given by (m+ 1)2and they are distributed in a translated of the square Km+1. From this configuration we obtain our lower bound. ii) There are some pairs of “metric circumferences” that do not intersect properly but are tangent. In this case they are tangent along a straight line segment. Considering the ends of this straight line segment and taking the “metric circumferences” centered at these ends we conclude that there are no more than (m+1)2possible locations. So we also reach the same lower estimate.  It is easy to see that the argument in the proof of lemma 2 holds for all metrics generated by the gauge function of a centrally symmetric, convex set; as the equality sign is attained in the case that the body which generates the metric is a square, we can conclude the following corollary: Corollary 3 Among all metrics generated by a closed, centrally symmetric, convex set K, the metrics that give the smallest values for f(n)are those in which the metric is generated by the gauge function corresponding to a square. For instance the taxi-cab metric or the maximum metric defined as d((x1, y1)(x2, y2)) = max{|x2−x1|,|y2−y1|} Corollary 3 does not hold for general metrics. For example, let us consider the so called post office metric d((x1, y1)(x2, y2)) = d2((x1, y1),(0,0)) +d2((0,0),(x2, y2)) where d2stands for the euclidean distance in the plane. In this case it is easy to see that we can arrange infinite points so that each pair of them is at distance one; so f(n) = 1 for all n. (0,0) 3. The minimum number of distinct distances problem with the euclidean distance in the integer lattice If we consider Erd¨os problem restricted to the integer lattice we obtained different values for f(n) as the following table shows: f(n) Plane Integer lattice 3 1 2 4 2 2 5 2 3 6 3 4 7 3 4 Table 2 Some values of f(n) in the integer lattice In general, we have the following upper bound: Lemma 4 In the integer lattice f(n)≤(⌈√n⌉−2)(⌈√n⌉+ 1) 2 PROOF. Let Lbe the integer lattice and let Pnbe the point set Pn=L∩ h(0,0),(0,⌈√n⌉ − 1),(⌈√n⌉ − 1,0),(⌈√n⌉ − 1,⌈√n⌉ − 1)i.Pncontains at least npoints.We can compute the number of distinct distances by considering only the distances between (0,0) and the the rest of the points below the diagonal of the square. Then we have at most 2 + 3 + ... + (⌈√n⌉ − 1) distinct distances, 20th European Workshop on Computational Geometry that is the sum of the terms of an arithmetic progression, so f(n)≥2 + 3 + ... + (⌈√n⌉ − 1) = ⌈√n⌉(⌈√n⌉−1) 2−1 = (⌈√n⌉−2)(⌈√n⌉+1) 2 (0,0)  The values of f(n) if we restrict to the integer lattice are the same that if we restrict to the points with rational coordinates because a finite number of points with rational coordinates are included in an integer lattice generated by the vectors (q, 0) ,(0, q) where qis the least common denominator of the coordinates of the points that we are considering. This estimate of f(n) can be applied to computers, because the computer screen can be represented as a finite number of points with rational coordinates. 4. Erd¨os problem for other topological spaces The first mathematicians to consider this problem in other topological spaces were Erd¨os, Hickerson and Pach ([6]) who studied the case of the sphere. We are going to consider two other particular topological surfaces: the cylinder and the flat torus. As we can see in table 3, for small values of nwe obtain the same values for f(n) in both topological surfaces, but this do not occur for greater values of n. f(n) Plane Cylinder Flat torus 3 1 1 1 4 2 1 1 5 2 2 2 6 3 2 2 Table 3 Some values of f(n) in different topological surfaces Now, we can give upper bounds for both topological surfaces. Lemma 5 In the flat torus f(n)≤(⌊⌈√n⌉/2 + 1⌋+ 2)(⌊⌈√n⌉/2 + 1⌋−1) 2 Lemma 6 In the cylinder f(n)≤(⌊⌈√n⌉/2 + 1⌋+ 2)(⌊⌈√n⌉/2 + 1⌋−1) 2 +(⌊⌈√n⌉/2 + 1⌋)(⌈√n⌉−⌊⌈√n⌉/2 + 1⌋) We omit the proofs because they are similar to the proof of lemma 3. We have to consider a particular lattice and intersect it with the topological surfaces, as the figure shows. Then, by some arithmetic computations, we obtain the bounds. Flat Torus Cylinder References [1] Braß, P.: On the maximum number of unit distances among npoints in dimension four, Intuitive geometry (Budapest, 1995), 277–290, Bolyai Soc. Math. Stud., 6, J´anos Bolyai Math. Soc., Budapest, 1997. [2] Chung, F. R. K., Szemerdi, E. and Trotter, W. T.: The number of different distances determined by a set of points in the Euclidean plane, Discrete Comp. Geometry 7(1992), 1–11. [3] Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M. and Welzl, E.:Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comp. Geometry 5(1990), 90–160. [4] Erd¨os, P.: On sets of distances of npoints, Amer. Math. Monthly 53 (1946), 248–250. [5] Erd¨os, P.:On sets of distances of npoints in Euclidean space, Magyar Tudom´anyos Akad´emia M´atematikai Kutat´o Int´ezet K¨ozlem´enyei 7(1960), 165–169. [6] Erd¨os, P. , Hickerson, D. and Pach J.: A problem of Leo Moser about repeated distances on the sphere, Amer. Math. Monthly 96 (1989), 569–575. [7] Guggenheimer, H. W.: Applicable geometry, Robert E. Krieger Publishing Co., Inc. , Huntington, New York, 1977.