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.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE