On the Number of Congruent Simplices in a Point Set
DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
We derive improved bounds on the number of k-dimensional simplices spanned by a set of n points in Rsup d that are congruent to a given k-simplex, for k or d - 1. Let fsup dsub Kn be the maximum number of k-simplices spanned by a set of n points in Rsup d that are congruent to a given k-simplex. We prove that fsup 3sub 2 n On sup 53 times 2 sup Oalpha sup 2n, fsup 4sub 2n On sup 2 epsilon, fsup 5sub 2 n theta n sup 73, and fsup 4sub 3n On sup 94 plus epsilon. We also derive a recurrence to bound fsup dsub k n for arbitrary values of k and d, and use it to derive the bound fsup dsub kn Onsup d2 for d or 7 and k or d - 2. Following Erdos and Purdy, we conjecture that this bound holds for larger values of d as well, and for k or d - 2.
- Operations Research
- Computer Programming and Software