Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
We define the bisector energy E(P) of a set P in R-2 to be the number of quadruples (a, b, c, d) is an element of P-4 such that a, b determine the same perpendicular bisector as c, d. Equivalently, E(P) is the number of isosceles trapezoids determined by P. We prove that for any epsilon > 0, if an n-point set P has no M(n) points on a line or circle, then we have E(P) = O(M(n)(2/5) n(12/5+epsilon) + M(n)n(2)). We derive the lower bound E(P) = Omega(M(n)n(2)), matching our upper bound when M(n) is large. We use our upper bound on E(P) to obtain two rather different results: (i) If P determines O(n/root log n) distinct distances, then for any 0 < alpha
Volkan Cevher, Kimon Antonakopoulos, Thomas Michaelsen Pethick, Wanyun Xie, Fabian Ricardo Latorre Gomez