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. Rapport de recherche RR-5773, INRIA, 2005.

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

@techreport{CORTIER:2005:INRIA-00070247:1,
    hal_id = {inria-00070247},
    title = {{A note on maximally repeated sub-patterns of a point set}},
    author = {Cortier, V{\'e}ronique and Goaoc, Xavier and Lee, Mira and Na, Hyeon-Suk},
    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$.}},
    keywords = {discrete geometry; point sets; repeated configurations},
    language = {Anglais},
    affiliation = {CASSIS - INRIA Lorraine - LORIA / LIFC , VEGAS - INRIA Lorraine - LORIA , Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] - KAIST , School of Computing - Soongsil University, S{\'e}oul},
    pages = {5},
    type = {Rapport de recherche},
    institution = {INRIA},
    number = {RR-5773},
    year = {2005},
}