Similar simplices in a d-dimensional point set

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Similar simplices in a d-dimensional point set

Full text

Pdf (183 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-third annual symposium on Computational geometry table of contents

Gyeongju, South Korea

SESSION: Session 7 table of contents

Pages: 232 - 238

Year of Publication: 2007

ISBN:978-1-59593-705-6

Authors

Pankaj K. Agarwal	Duke University, Durham, NC
Roel Apfelbaum	Tel Aviv University, Tel Aviv, Israel
George Purdy	University of Cincinnati, Cincinnati, OH
Micha Sharir	Tel Aviv University, Tel Aviv, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 37, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1247069.1247112 What is a DOI?

ABSTRACT

We consider the problem of bounding the maximum possible number f_k,d(n) of k-simplices that are spanned by a set of n pointsin R^d and are similar to a given simplex. We first show that f_2,3(n) = O(n^13/6), and then tacklethe general case, and show that f_{d-2, d}(n) = O(n^d-8/5) and f_d-1,d(n) = O^*(n^d-72/55), for any d.Our technique extends to derive bounds for other valuesof k and d, and we illustrate this by showing that f_2,5(n)=O(n^8/3).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ábrego , György Elekes , Silvia Fernández-Merchant, Structural Results For Planar Sets With Many Similar Subsets, Combinatorica, v.24 n.4, p.541-554, September 2004 [doi>10.1007/s00493-004-0033-8]
	2	B. M. Ábrego and S. Frenándes-Merchant, On the maximum number of equilateral triangles, I, Discrete Comput. Geom. 23 (2000), 129--136.
	3	Pankaj K. Agarwal , Eran Nevo , János Pach , Rom Pinchasi , Micha Sharir , Shakhar Smorodinsky, Lenses in arrangements of pseudo-circles and their applications, Journal of the ACM (JACM), v.51 n.2, p.139-186, March 2004 [doi>10.1145/972639.972641]
	4	P. K. Agarwal and M. Sharir, On the number of congruent simplices in a point set, Discrete Comput. Geom. 28 (2002), 123--150.
	5	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.
	6	Boris Aronov , Vladlen Koltun , Micha Sharir, Incidences between Points and Circles in Three and Higher Dimensions, Discrete & Computational Geometry, v.33 n.2, p.185-206, February 2005 [doi>10.1007/s00454-004-1111-9]
	7	B. Aronov and M. Sharir, Cutting circles into pseudo--segments and improved bounds for incidences, Discrete Comput. Geom. 28 (2002), 475--490.
	8	M. D. Atkinson, An optimal algorithm for geometrical congruence, Journal of Algorithms, v.8 n.2, p.159-172, June 1987 [doi>10.1016/0196-6774(87)90036-8]
	9	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 ]
	10	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
	11	P. Brass, Combinatorial geometry problems in pattern recognition, Discrete Comput. Geom. 28 (2002), 495--510.
	12	Peter Braß , Christian Knauer, Testing the congruence of d-dimensional point sets, Proceedings of the sixteenth annual symposium on Computational geometry, p.310-314, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336217]
	13	P. Brass, W. Moser and J. Pach, Research Problems in Discrete Geometry, Springer Verlag, New York, 2005.
	14	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	15	G. Elekes and P. Erdos, Similar configurations and pseudo-grids, in Intuitive Geometry (K. Böröczky and G. Fejes Tóth, eds.), Colloq. Math. Soc. János Bolyai, vol. 63, Elsevier, 1994, 85--104.
	16	György Elekes , Csaba D. Tóth, Incidences of not-too-degenerate hyperplanes, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064098]
	17	P. Erdos and G. Purdy, Some extremal problems in geometry IV, Proc. 7th South-Eastern Conf. Combinatorics, Graph Theory, and Comput., 1976, 307--322.
	18	M. Laczkovich and I. Ruzsa, The number of homothetic subsets, in: The Mathematics of Paul Erdos, vol. 2, (R. Graham and J. Nešetřil, eds.), Springer Verlag, 1997, 294--302.
	19	H. Lenz, Zur Zerlegung von Punktmengen in solche kleineren Durchmessers, Arch. Math. 6 (1955), 413--416.
	20	Adam Marcus , Gábor Tardos, Intersection reverse sequences and geometric applications, Journal of Combinatorial Theory Series A, v.113 n.4, p.675-691, May 2006 [doi>10.1016/j.jcta.2005.07.002]
	21	J. Pach and M. Sharir, Geometric incidences, in Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics, Vol. 342, Amer. Math. Soc., Providence, RI, 2004, 185--223.
	22	P. J. de Rezende and D.--T. Lee, Point set pattern matching in d-dimensions, Algorithmica 13 (1995), 387--404.
	23	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]