Erdo&huml;s distance problem for convex metrics

This dissertation was inspired by the Erdo&huml;s Distance Problem, which asks: What is the minimum number of distinct distances determined by n distinct points in the plane? Erdős posed this question in 1946 and conjectured that f(n) = minE =n |{lcub}||x - y||2 : x, y ∈ E{rcub}| = O( n1-epsilon) and showed in [17] that this bound is attained by the nx n lattice. The best lower bound to date is O( n19/22), due to Katz and Tardos [20]. In this work we ask how the Erdo&huml;s distance problem changes when distance is defined by different convex metrics. More formally, given a convex metric K, we hope to find good upper and lower bounds on f K(n) = minE =n |{lcub}||x - y||K : x, y ∈ E{rcub}|.; In terms of the lower bound, we obtained the following result for all homogeneous, translation-invariant convex metrics. Its proof follows the general structure of Erdo&huml;'s original proof in [17], with modifications to account for certain difficult cases.; Theorem 1. For every convex asymmetric metric K and any set P of n points in the plane, there are O( n ) distinct distances determined by them. In fact, fKn≥ n+212-1 2 .; This bound is asymptotically tight for symmetric metrics K that are convex, but not strictly convex, i.e. fK( n) ≈ n1/2. However, for strictly convex metrics we aimed to mimic Szekely's method from [50] where he showed that in the Euclidean case f(n) = O( n4/5). While we were not able to extend his argument to work for all strictly convex metrics, we did extend it to a class of metrics which includes the Lp metric.; Theorem 2. Given a set E of n points in the plane, one of them determines ≳ n4/5 distinct distances from the others if our metric K is strictly convex, has only finitely many axes of symmetry, and all pairs of non-linear bisectors intersect in at most co points, for some constant co.; In fact, the argument follows rather nicely, with a few notable obstacles. Foremost, Szekely's argument relies heavily on the fact that the bisector of two points in the Euclidean metric is a line. Bisectors in arbitrary metrics may behave in many different ways and this is what prevents us from extending Theorem 2 to all strictly convex metrics. In the case of the L p metric we are able to resolve the issue of how often bisectors intersect by using a theorem from algebraic geometry, see [24, ch. 1].