Similar simplices in a d-dimensional point set | Zendy

Pankaj K. Agarwal | Zendy; Roel Apfelbaum | Zendy; George Purdy | Zendy; Micha Sharir | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Similar simplices in a d-dimensional point set

Author(s) -

Pankaj K. Agarwal,

Roel Apfelbaum,

George Purdy,

Micha Sharir

Publication year - 2007

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/1247069.1247112

Subject(s) - simplex , bounding overwatch , combinatorics , set (abstract data type) , mathematics , point (geometry) , geometry , computer science , artificial intelligence , programming language

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).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research