A note on maximally repeated sub-patterns of a point set

Véronique Cortier (1) , Xavier Goaoc (2) , Mira Lee (3) , Na Hyeon-Suk (4)

1 CASSIS - Combination of approaches to the security of infinite states systems
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
3 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
4 School of Computing - Soongsil University, Séoul

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbb{R}^d$. We show that this number, which was conjectured to be polynomial, is in fact $\Theta(2^{n/2})$ in the worst case, regardless of the dimension $d$.

Mots clés: Discrete geometry; point sets; repeated configurations

Domaines: Mathématique discrète [cs.DM]

Véronique Cortier, Xavier Goaoc, Mira Lee, Na Hyeon-Suk. A note on maximally repeated sub-patterns of a point set. Discrete Mathematics, 2006, 306 (16), pp.1965-1968. ⟨10.1016/j.disc.2006.03.045⟩. ⟨hal-00097239⟩