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

A note on maximally repeated sub-patterns of a point set. Véronique Cortier, Xavier Goaoc, Mira Lee, and Hyeon-Suk Na. Discrete Mathematics, 306(16):1965–1968, August 2006.

Download

[PDF] [HTML]

Abstract

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^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$.

BibTeX

@Article{XavierDM06,
  author = 	 {V\'eronique Cortier and Xavier Goaoc and Mira Lee and Hyeon-Suk Na},
  title = 	 {A note on maximally repeated sub-patterns of a point set},
  journal = 	 {Discrete Mathematics},
  year = 	 {2006},
  volume = 	 {306},
  number = 	 {16},
  pages = 	 {1965-1968},
  month = 	 {August},
DOI = {10.1016/j.disc.2006.03.045},
abstract = {We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^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$.},
}