Math @ Duke

Publications [#235435] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, On the number of congruent simplices in a point set,
Proceedings of the Annual Symposium on Computational Geometry
(2001),
pp. 19
(last updated on 2018/10/23)
Abstract: We derive improved bounds on the number of kdimensional simplices spanned by a set of n points in Rd that are congruent to a given ksimplex, for k ≤ d  1. Let fk(d)(n) be the maximum number of ksimplices spanned by a set of n points in Rd that are congruent to a given ksimplex. 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

