Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  822.52004
Autor:  Elekes, G.; Erdös, Paul
Title:  Similar configurations and pseudo grids. (In English)
Source:  Böröczky, K. (ed.) et al., Intuitive geometry. Proceedings of the 3rd international conference held in Szeged, Hungary, from 2 to 7 September, 1991. Amsterdam: North-Holland, Colloq. Math. Soc. János Bolyai. 63, 85-104 (1994).
Review:  Given a finite set P of points in the plane, it is of interest to find another, n-point, set A which contains many similar or homothetic copies of P. When P is a square or equilateral triangle, it is easily seen that a suitable regular grid achieves c · n2 similar copies and c · n3/2 homothetic copies.
Such constructions might appear to depend on the fact that the square and equilateral triangle tile the plane in a lattice tiling. The authors show that this is not the case. If P is a triangle, or can be represented in the complex plane by a set of algebraic complex numbers {\xii}, then there exist ``pseudogrids'' containing c · n2 similar copies or c · n3/2 homothetic copies. The points of these pseudogrids are the values of polynomials in {\xii} with certain bounds on coefficients and degree. Even if P cannot be so represented, O(n2) similar copies and O(n3/2) homothetic copies may be achieved.
The results for homothetic copies are extended to higher dimensions. If Rd it is possible to construct pseudogrids which contain c · n(d+1)/d homothetic copies of a pattern P with algebraic coordinates, or O(n(d+1)/d) homothetic copies of an arbitrary pattern.
Reviewer:  R.Dawson (Halifax)
Classif.:  * 52A37 Other problems of combinatorial convexity
                   52C20 Tilings in 2 dimensions (discrete geometry)
Keywords:  similar configurations; homothetic configurations; pseudogrids

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page