Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235435] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharir, M, On the number of congruent simplices in a point set, Proceedings of the Annual Symposium on Computational Geometry (2001), pp. 1-9
    (last updated on 2017/12/18)

    Abstract:
    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320