×

On the number of similar instances of a pattern in a finite set. (English) Zbl 1353.05030

Summary: New bounds on the number of similar or directly similar copies of a pattern within a finite subset of the line or the plane are proved. The number of equilateral triangles whose vertices all lie within an \(n\)-point subset of the plane is shown to be no more than \(\lfloor{(4 n-1)(n-1)/18}\rfloor\). The number of \(k\)-term arithmetic progressions that lie within an \(n\)-point subset of the line is shown to be at most \((n-r)(n+r-k+1)/(2 k-2)\), where \(r\) is the remainder when \(n\) is divided by \(k-1\). This upper bound is achieved when the \(n\) points themselves form an arithmetic progression, but for some values of \(k\) and \(n\), it can also be achieved for other configurations of the \(n\) points, and a full classification of such optimal configurations is given. These results are achieved using a new general method based on ordering relations.

MSC:

05B25 Combinatorial aspects of finite geometries
05A99 Enumerative combinatorics
52C10 Erdős problems and related topics of discrete geometry
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] B. M. ´Abrego, G. Elekes, and S. Fern´andez-Merchant. Structural results for planar sets with many similar subsets. Combinatorica, 24(4):541-554, 2004. · Zbl 1075.52009
[2] B. M. ´Abrego and S. Fern´andez-Merchant. On the maximum number of equilateral triangles. I. Discrete Comput. Geom., 23(1):129-135, 2000. · Zbl 0963.52007
[3] B. M. ´Abrego and S. Fern´andez-Merchant. Convex polyhedra in R3spanning Ω(n4/3) congruent triangles. J. Combin. Theory Ser. A, 98(2):406-409, 2002. · Zbl 1028.52007
[4] B. M. ´Abrego, S. Fern´andez-Merchant, and B. Llano. On the maximum number of translates in a point set. Discrete Comput. Geom., 43(1):1-20, 2010. · Zbl 1185.68586
[5] P. K. Agarwal, R. Apfelbaum, G. Purdy, and M. Sharir. Similar simplices in a ddimensional point set. In Computational Geometry (SCG’07), pages 232-238. ACM, New York, 2007. · Zbl 1218.52021
[6] R. Apfelbaum and M. Sharir. Repeated angles in three and four dimensions. SIAM J. Discrete Math., 19(2):294-300, 2005. · Zbl 1090.52501
[7] P. Brass. Exact point pattern matching and the number of congruent triangles in a three-dimensional pointset. In Algorithms—ESA 2000 (Saarbr¨ucken), volume 1879 of Lecture Notes in Comput. Sci., pages 112-119. Springer, Berlin, 2000. · Zbl 0974.68543
[8] P. Brass. Combinatorial geometry problems in pattern recognition. Discrete Comput. Geom., 28(4):495-510, 2002. · Zbl 1011.68117
[9] P. Brass, W. Moser, and J. Pach. Research problems in discrete geometry. Springer, New York, 2005. the electronic journal of combinatorics 23(4) (2016), #P4.3922 · Zbl 1086.52001
[10] P. Brass and J. Pach. Problems and results on geometric patterns. In Graph Theory and Combinatorial Optimization, volume 8 of GERAD 25th Anniv. Ser., pages 17-36. Springer, New York, 2005. · Zbl 1083.68110
[11] G. R. Burton and G. B. Purdy. The directions determined by n points in the plane. J. London Math. Soc. (2), 20(1):109-114, 1979. · Zbl 0409.52005
[12] V. Cortier, X. Goaoc, M. Lee, and H.-S. Na. A note on maximally repeated subpatterns of a point set. Discrete Math., 306(16):1965-1968, 2006. · Zbl 1097.68120
[13] H. T. Croft, K. J. Falconer, and R. K. Guy. Unsolved problems in geometry. Problem Books in Mathematics. Springer-Verlag, New York, 1991. · Zbl 0748.52001
[14] A. Dumitrescu, J. Pach, and G. T´oth. Drawing Hamiltonian cycles with no large angles. Electron. J. Combin., 19(2):#P31, 13, 2012. · Zbl 1243.05138
[15] G. Elekes. On the structure of sets with many k-term arithmetic progressions. Acta Arith., 138(2):145-164, 2009. · Zbl 1228.11016
[16] G. Elekes and P. Erd˝os. Similar configurations and pseudo grids. In Intuitive Geometry (Szeged, 1991), volume 63 of Colloq. Math. Soc. J´anos Bolyai, pages 85-104. North-Holland, Amsterdam, 1994. · Zbl 0822.52004
[17] P. Erd˝os. On sets of distances of n points. Amer. Math. Monthly, 53(5):248-250, 1946. · Zbl 0060.34805
[18] P. Erd˝os and G. Purdy. Some extremal problems in geometry. J. Combinatorial Theory Ser. A, 10:246-252, 1971. · Zbl 0219.05006
[19] P. Erd˝os and G. Purdy. Some extremal problems in geometry. III. In Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, No. XIV, pages 291-308. Utilitas Math., Winnipeg, Man., 1975. · Zbl 0328.05018
[20] P. Erd˝os and G. Purdy. Some extremal problems in geometry. IV. In Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congressus Numerantium, No. XVII, pages 307-322. Utilitas Math., Winnipeg, Man., 1976. · Zbl 0345.52007
[21] J. Erickson, F. Hurtado, and P. Morin. Centerpoint theorems for wedges. Discrete Math. Theor. Comput. Sci., 11(1):45-54, 2009. · Zbl 1194.51003
[22] S. P. Fekete and H. Meijer. On minimum stars and maximum matchings. Discrete Comput. Geom., 23(3):389-407, 2000. · Zbl 1112.68476
[23] M. Laczkovich and I. Z. Ruzsa. The number of homothetic subsets. In The Mathematics of Paul Erd˝os, II, volume 14 of Algorithms Combin., pages 294-302. Springer, Berlin, 1997. · Zbl 0871.52012
[24] J. Pach and P. K. Agarwal. Combinatorial geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1995. · Zbl 0881.52001
[25] J. Pach and R. Pinchasi. How many unit equilateral triangles can be generated by N points in convex position? Amer. Math. Monthly, 110(5):400-406, 2003. the electronic journal of combinatorics 23(4) (2016), #P4.3923 · Zbl 1187.52016
[26] J. Pach and M. Sharir. Repeated angles in the plane and related problems. J. Combin. Theory Ser. A, 59(1):12-22, 1992. · Zbl 0749.52014
[27] J. Pach and M. Sharir. Combinatorial geometry and its algorithmic applications, volume 152 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2009. · Zbl 1157.52001
[28] M. J. van Kreveld and M. T. de Berg. Finding squares and rectangles in sets of points. BIT, 31(2):202-219, 1991. · Zbl 0726.68044
[29] C. Xu and R. Ding. The number of isosceles right triangles determined by n points in convex position in the plane. Discrete Comput. Geom., 31(3):491-499, 2004. · Zbl 1060.52009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.