Abstract - The following problem of Erdös is probably the best known and simplest problem to explain in combinatorial geometry. Find the maximum number of times the same distance can occur among n points in the plane. For n ≥ 4, it is not possible that all (n,2) point pairs determine the same distance, so it is a natural and non trivial problem to find the maximum number of point pairs that determine the same distance ∂. By scaling, we can assume without loss of generality that ∂ = 1. We assume here, as always in combinatorial geometry, that the points are distinct. We represent the the maximum number of occurrences of the distance ∂ by u(n).

Index Terms – Asymptotic Bounds, Unit distance graph.

INTRODUCTION

The original problem statement as stated in abstract deals with finding the asymptotic bounds for the function u(n). The problem was studied by various mathematicians in the past. The original upper bound for the function u(n) was put by Erdos himself, which was of O(n3/2)[1]. However, this upper bound was reduced in many steps by many mathematicians to give make the function more precise. This bound was reduced to O(n4/3) [2],[3]. The most recent development is due to Schade. He found out the actual number of u(n) for small values of n(n≤14).

OBJECTIVE

The main objective is to find the exact values that Schade has been able to obtain and if possible extend the search for beyond n=14 by using computational methods.