# Accession Number:

## ADA415522

# Title:

## On the Number of Congruent Simplices in a Point Set

# Descriptive Note:

## Conference paper

# Corporate Author:

## DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 2001-06-03

# Pagination or Media Count:

## 9.0

# Abstract:

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.

# Descriptors:

# Subject Categories:

- Operations Research
- Computer Programming and Software