InforLorV4, Main, Exploration, bibRecord, 005625

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

Identifieur interne : 005625 ( Main/Exploration ); précédent : 005624; suivant : 005626

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

Auteurs : Véronique Cortier [France] ; Xavier Goaoc [France] ; Mira Lee [Corée du Sud] ; Hyeon-Suk Na [Corée du Sud]

Source :

Discrete mathematics [ 0012-365X ] ; 2006.

RBID : Pascal:06-0398732

Descripteurs français

Pascal (Inist)
- Polynôme, Géométrie discrète, Pire cas, Ensemble point, Configuration répétée.

English descriptors

KwdEn :
- Discrete geometry, Point set, Polynomial, Repeated configuration.
mix :
- Discrete geometry, point sets, repeated configurations.

Abstract

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

Url:

https://hal.archives-ouvertes.fr/hal-00097239

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A note on maximally repeated sub-patterns of a point set</title>
<author><name sortKey="Cortier, Veronique" sort="Cortier, Veronique" uniqKey="Cortier V" first="Véronique" last="Cortier">Véronique Cortier</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA - CNRS, 615 rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">villers-les-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>LORIA- INRIA Lorraine, 615 rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 Villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Villers-les-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Division of Computer Science, Korea Advanced Institute of Science and Technology (KAIST), 373-1, Guseong-dong</s1>
<s2>Yuseong-gu, Daejeon 305-701</s2>
<s3>KOR</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Corée du Sud</country>
<wicri:noRegion>Yuseong-gu, Daejeon 305-701</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
<affiliation wicri:level="1"><inist:fA14 i1="04"><s1>School of Computing, Soongsil University, 1-1, Sangdo-dong</s1>
<s2>Dongjak-gu, Seoul 156-743</s2>
<s3>KOR</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>Corée du Sud</country>
<placeName><settlement type="city">Séoul</settlement>
<region type="capital">Région capitale de Séoul</region>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">06-0398732</idno>
<date when="2006">2006</date>
<idno type="stanalyst">PASCAL 06-0398732 INIST</idno>
<idno type="RBID">Pascal:06-0398732</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000431</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000602</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000415</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000415</idno>
<idno type="wicri:doubleKey">0012-365X:2006:Cortier V:a:note:on</idno>
<idno type="wicri:Area/Main/Merge">005820</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00097239</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00097239</idno>
<idno type="wicri:Area/Hal/Corpus">000801</idno>
<idno type="wicri:Area/Hal/Curation">000801</idno>
<idno type="wicri:Area/Hal/Checkpoint">004428</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004428</idno>
<idno type="wicri:doubleKey">0012-365X:2006:Cortier V:a:note:on</idno>
<idno type="wicri:Area/Main/Merge">005A56</idno>
<idno type="wicri:Area/Main/Curation">005625</idno>
<idno type="wicri:Area/Main/Exploration">005625</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A note on maximally repeated sub-patterns of a point set</title>
<author><name sortKey="Cortier, Veronique" sort="Cortier, Veronique" uniqKey="Cortier V" first="Véronique" last="Cortier">Véronique Cortier</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA - CNRS, 615 rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">villers-les-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>LORIA- INRIA Lorraine, 615 rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 Villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Villers-les-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Division of Computer Science, Korea Advanced Institute of Science and Technology (KAIST), 373-1, Guseong-dong</s1>
<s2>Yuseong-gu, Daejeon 305-701</s2>
<s3>KOR</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Corée du Sud</country>
<wicri:noRegion>Yuseong-gu, Daejeon 305-701</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
<affiliation wicri:level="1"><inist:fA14 i1="04"><s1>School of Computing, Soongsil University, 1-1, Sangdo-dong</s1>
<s2>Dongjak-gu, Seoul 156-743</s2>
<s3>KOR</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>Corée du Sud</country>
<placeName><settlement type="city">Séoul</settlement>
<region type="capital">Région capitale de Séoul</region>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Discrete mathematics</title>
<title level="j" type="abbreviated">Discrete math.</title>
<idno type="ISSN">0012-365X</idno>
<imprint><date when="2006">2006</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Discrete mathematics</title>
<title level="j" type="abbreviated">Discrete math.</title>
<idno type="ISSN">0012-365X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Discrete geometry</term>
<term>Point set</term>
<term>Polynomial</term>
<term>Repeated configuration</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Polynôme</term>
<term>Géométrie discrète</term>
<term>Pire cas</term>
<term>Ensemble point</term>
<term>Configuration répétée</term>
</keywords>
<keywords scheme="mix" xml:lang="en"><term>Discrete geometry</term>
<term>point sets</term>
<term>repeated configurations</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We answer a question raised by Brass on the number of maximally repeated sub-patterns in a set of n points in R<sup>d</sup>
, We show that this number, which was conjectured to be polynomial, is in fact Θ(2<sup>n/2</sup>
) in the worst case, regardless of the dimension d.</div>
</front>
</TEI>
<affiliations><list><country><li>Corée du Sud</li>
<li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Région capitale de Séoul</li>
</region>
<settlement><li>Séoul</li>
<li>Villers-les-Nancy</li>
<li>villers-les-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Cortier, Veronique" sort="Cortier, Veronique" uniqKey="Cortier V" first="Véronique" last="Cortier">Véronique Cortier</name>
</region>
<name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
</country>
<country name="Corée du Sud"><noRegion><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
</noRegion>
<name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005625 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005625 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:06-0398732
   |texte=   A note on maximally repeated sub-patterns of a point set
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

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

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

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.