The number of distinct distances from a vertex of a convex polygon

Gabriel Nivasch, János Pach, Rom Pinchasi, Shira Zerbib

Abstract


Erdős conjectured in 1946 that every $n$-point set $P$ in convex position in the plane contains a point that determines at least $\lfloor n/2\rfloor$ distinct distances to the other points of $P$. The best known lower bound due to Dumitrescu (2006) is $13n/36 − O(1)$. In the present note, we slightly improve on this result to $(13/36 + \varepsilon)n − O(1)$ for $\varepsilon \approx 1/23000$. Our main ingredient is an improved bound on the maximum number of isosceles triangles determined by $P$.


Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v4i1a1

ISSN: 1920-180X