On the number of congruent simplices in a point set

Published

Journal Article

We derive improved bounds on the number of k-dimensional simplices spanned by a set of n points in Rd that are congruent to a given k-simplex, for k ≤ d - 1. Let fk(d)(n) be the maximum number of k-simplices spanned by a set of n points in Rd that are congruent to a given k-simplex. We prove that f2(3)(n) = O(n5/3 · 2O(α(2)(n))), f2(4) (n) = O(n2+ε), f2(5) (n) = Θ(n7/3), and f3(4) (n) = O(n9/4+ε). We also derive a recurrence to bound fk(d)(n) for arbitrary values of k and d, and use it to derive the bound fk(d) (n) = O(nd/2+ε for d ≤ 7 and k ≤ d - 2. Following Erdös and Purdy, we conjecture that this bound holds for larger values of d as well, and for k ≤ d - 2.

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • January 1, 2001

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 1 - 9

Citation Source

  • Scopus