On the number of congruent simplices in a point

ABSTRACT

We derive improved bounds on the number of k-dimensional simplices spa nned by a set of n points in $\reals^d$ that are congruent to a given $k$-simplex, for $k\le d-1$. Let $f_k^{(d)} (n)$ be the maximum number of $k$-simplices spanned by a set of $n$ points in $\reals^d$ that are congruent to a given $k$-simplex. We prove that $f_2^{(3)}(n) = O(n^{5/3}\cdot 2^{O(\alpha^2(n))})$, $f_2^{(4)} (n) = O(n^{2+\eps})$, $f_2^{(5)} (n) = \Theta(n^{7/3})$, and $f_3^{(4)} (n) = O(n^{9/4+\eps})$. We also derive a recurrence to bound $f_k^{(d)} (n)$ for arbitrary values of $k$ and $d$, and use it to derive the bound $f_k^{(d)} (n) = O(n^{d/2})$ for $d \le 7$ and $k \le d-2$. Following Erd{\H o}s and Purdy, we conjecture that this bound holds for larger values of $d$ as well, and for $k\le d-2$.

REFERENCES

• 1: Pankaj K. Agarwal , Jirí Matousek , Otfried Schwarzkopf, Computing Many Faces in Arrangements of Lines and Segments, SIAM Journal on Computing, v.27 n.2, p.491-505, April 1998 [doi>10.1137/S009753979426616X]
• 2: T. Akutsu, H. Tamaki and T. Tokuyama, Distribution of distances and triangles in a point set and algorithms for computing the largest common point set, Discrete Comput. Geom. 20 (1998), 307-331.
• 3: Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
• 4: Laurence Boxer, Point set pattern matching in 3-D, Pattern Recognition Letters, v.17 n.12, p.1293-1297, Oct. 25, 1996 [doi>10.1016/0167-8655(96)00086-4]
• 5: Peter Brass, Exact Point Pattern Matching and the Number of Congruent Triangles in a Three-Dimensional Pointset, Proceedings of the 8th Annual European Symposium on Algorithms, p.112-119, September 05-08, 2000
• 6: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 7: P. Erdos, On a set of distances of n points, Amer. Math. Monthly, 53 (1946), 248-250.
• 8: P. Erdös , D. Hickerson , J. Pach, A problem of Leo Moser about repeated distances on the sphere, American Mathematical Monthly, v.96 n.7, p.569-575, Aug.–Sep. 1989 [doi>10.2307/2325175]
• 9: P. Erdos and G. Purdy, Some extremal problems in geometry III, Proc. 6th South-Eastern Conf. Combinatorics, Graph Theory, and Comput., 1975, pp. 291-308.
• 10: P. Erdos and G. Purdy, Some extremal problems in geometry IV, Proc. 7th South-Eastern Conf. Combinatorics, Graph Theory, and Comput., 1976, pp. 307-322.
• 11: H. Lenz, Zur Zerlegung von Punktmengen in solche kleineren Durchmessers, Arch. Math. 6 (1955), 413-416.
• 12: J. Pach andP. K. Agarwal, Combinatorial Geometry, Wiley Interscience, 1995.
• 13: P. J. de Rezende and D.-T. Lee, Point set pattern matching in d-dimensons, Algorithmica 13 (1995), 387-404.
• 14: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 15: J. Spencer, E. Szemeredi and W. Trotter, Unit distances in the Euclidean plane, In: Graph Theory and Combinatorics (Proc. Cambridge Conf. on Combinatorics, B. Bollobas, ed.), 293-308, Academic Press, 1984.
• 16: László A. Székely, Crossing Numbers and Hard Erdös Problems in Discrete Geometry, Combinatorics, Probability and Computing, v.6 n.3, p.353-358, September 1997 [doi>10.1017/S0963548397002976]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory, Verification