On the Number of Congruent Simplices in a Point Set

Abstract

We derive improved bounds on the number of k-dimensional simplices spanned by a set of n points in R(sup d) that are congruent to a given k-simplex, for k < or = d - 1. Let f(sup d)(sub K)(n) be the maximum number of k-simplices spanned by a set of n points in R(sup d) that are congruent to a given k-simplex. We prove that f(sup 3)(sub 2) (n) = O(n sup 5/3) times 2 sup O(alpha (sup 2)(n)), f(sup 4)(sub 2)(n) = O(n (sup 2) + epsilon), f(sup 5)(sub 2) (n)) = theta (n (sup 7/3), and f(sup 4)(sub 3)(n) = O(n (sup 9/4) plus epsilon). We also derive a recurrence to bound f(sup d)(sub k) (n) for arbitrary values of k and d, and use it to derive the bound f(sup d)(sub k(n) = O(n(sup d/2)) for d < or = 7 and k < or = d - 2. Following Erdo's and Purdy, we conjecture that this bound holds for larger values of d as well, and for k < or = d - 2.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 03, 2001
Accession Number
ADA415522

Entities

People

  • Micha Sharir
  • Pankaj Agarwal

Organizations

  • Duke University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Construction
  • Electronic Mail
  • Four Dimensional
  • Geometry
  • Graph Theory
  • Hard Copy
  • Inequalities
  • Intellectual Property
  • Military Research
  • New York
  • Three Dimensional
  • Triangles
  • Universities

Readers

  • Analytical Mechanics
  • Graph Algorithms and Convex Optimization.