A note on maximally repeated sub-patterns of a point set
Identifieur interne : 000415 ( PascalFrancis/Checkpoint ); précédent : 000414; suivant : 000416A 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.
Descripteurs français
- Pascal (Inist)
English descriptors
Abstract
We answer a question raised by Brass on the number of maximally repeated sub-patterns in a set of n points in Rd, We show that this number, which was conjectured to be polynomial, is in fact Θ(2n/2) in the worst case, regardless of the dimension d.
Affiliations:
- Corée du Sud, France
- Grand Est, Lorraine (région), Région capitale de Séoul
- Séoul, Villers-les-Nancy, villers-les-Nancy
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:06-0398732Le 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></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></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><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0012-365X</s0></fA01><fA02 i1="01"><s0>DSMHA4</s0></fA02><fA03 i2="1"><s0>Discrete math.</s0></fA03><fA05><s2>306</s2></fA05><fA06><s2>16</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>A note on maximally repeated sub-patterns of a point set</s1></fA08><fA11 i1="01" i2="1"><s1>CORTIER (Véronique)</s1></fA11><fA11 i1="02" i2="1"><s1>GOAOC (Xavier)</s1></fA11><fA11 i1="03" i2="1"><s1>LEE (Mira)</s1></fA11><fA11 i1="04" i2="1"><s1>NA (Hyeon-Suk)</s1></fA11><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></fA14><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></fA14><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></fA14><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></fA14><fA20><s1>1965-1968</s1></fA20><fA21><s1>2006</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>15322</s2><s5>354000142263110150</s5></fA43><fA44><s0>0000</s0><s1>© 2006 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>2 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>06-0398732</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Discrete mathematics</s0></fA64><fA66 i1="01"><s0>NLD</s0></fA66><fC01 i1="01" l="ENG"><s0>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.</s0></fC01><fC02 i1="01" i2="X"><s0>001A02F02</s0></fC02><fC02 i1="02" i2="X"><s0>001A02B01B</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Polynôme</s0><s5>17</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Polynomial</s0><s5>17</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Polinomio</s0><s5>17</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Géométrie discrète</s0><s5>18</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Discrete geometry</s0><s5>18</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Geometría discreta</s0><s5>18</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Pire cas</s0><s4>INC</s4><s5>70</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Ensemble point</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Point set</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Configuration répétée</s0><s4>CD</s4><s5>97</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Repeated configuration</s0><s4>CD</s4><s5>97</s5></fC03><fN21><s1>268</s1></fN21></pA></standard></inist><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/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000415 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000415 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|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. |  |