Similar simplices in a d-dimensional point set
Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, Micha Sharir · 2007
We consider the problem of bounding the maximum possible number fk,d(n) of k-simplices that are spanned by a set of n pointsin Rd and are similar to a given simplex. We first show that f2,3(n) = O(n13/6), and then tacklethe general case, and show that fd-2, d(n) = O(nd-8/5) and fd-1,d(n) = O*(nd-72/55), for any d.Our technique extends to derive bounds for other valuesof k and d, and we illustrate this by showing that f2,5(n)=O(n8/3).