Math @ Duke

Publications [#235446] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, The number of congruent simplices in a point set,
Discrete & Computational Geometry, vol. 28 no. 2
(2002),
pp. 123150, ISSN 01795376 [doi]
(last updated on 2018/03/22)
Abstract: For 1 ≤ k ≤ d 1, let fk(d) (n) be the maximum possible number of ksimplices spanned by a set of n points in ℝd that are congruent to a given ksimplex. We prove that f2(3) = O(n5/3 2O(α2(n))), f2(4)(n) = O(n2+ε), for any ε > 0, f2(5)(n) = Θ(n7/3), and f3(4) (n) = O(n20/9+ε), for any ε > 0. 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 any ε > 0, for d ≤ 7 and k ≤ d  2. Following Erdos 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

