A note on maximally repeated sub-patterns of a point set
Identifieur interne : 005625 ( Main/Curation ); précédent : 005624; suivant : 005626A 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
- KwdEn :
- mix :
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.
Url:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000431
- to stream PascalFrancis, to step Curation: Pour aller vers cette notice dans l'étape Curation :000602
- to stream PascalFrancis, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000415
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :005820
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000801
- to stream Hal, to step Curation: Pour aller vers cette notice dans l'étape Curation :000801
- to stream Hal, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :004428
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :005A56
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>
<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>
</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>
<double idat="0012-365X:2006:Cortier V:a:note:on"><HAL><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">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="1"><hal:affiliation type="researchteam" xml:id="struct-2366" status="OLD"><idno type="RNSR">200318302K</idno>
<orgName>Combination of approaches to the security of infinite states systems</orgName>
<orgName type="acronym">CASSIS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/cassis</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-866" type="direct"></relation>
<relation active="#struct-242365" type="indirect"></relation>
<relation active="#struct-300261" type="indirect"></relation>
<relation active="#struct-300360" type="indirect"></relation>
<relation name="UMR6174" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-866" type="direct"><org type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno>
<idno type="RNSR">200412232H</idno>
<orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName>
<orgName type="acronym">FEMTO-ST</orgName>
<desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.femto-st.fr</ref>
</desc>
<listRelation><relation active="#struct-242365" type="direct"></relation>
<relation active="#struct-300261" type="direct"></relation>
<relation active="#struct-300360" type="direct"></relation>
<relation name="UMR6174" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-242365" type="indirect"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno>
<idno type="ISNI">0000 0001 2188 3779 </idno>
<orgName>Université de Franche-Comté</orgName>
<orgName type="acronym">UFC</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.univ-fcomte.fr</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300261" type="indirect"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName>
<orgName type="acronym">UTBM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300360" type="indirect"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName>
<orgName type="acronym">ENSMM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR6174" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city" wicri:auto="siege">Besançon</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de Franche-Comté</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName>
<placeName><settlement type="city" wicri:auto="siege">Belfort</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de technologie de Belfort-Montbéliard</orgName>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno>
<orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName>
<orgName type="acronym">VEGAS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/vegas</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-121665" status="VALID"><orgName>Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<orgName type="acronym">KAIST</orgName>
<desc><address><addrLine>335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://www.kaist.edu/edu.html</ref>
</desc>
<listRelation><relation active="#struct-365285" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-365285" type="direct"><org type="institution" xml:id="struct-365285" status="INCOMING"><orgName>Korea Advanced Institute of Science and Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
<author><name sortKey="Hyeon Suk, Na" sort="Hyeon Suk, Na" uniqKey="Hyeon Suk N" first="Na" last="Hyeon-Suk">Na Hyeon-Suk</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7891" status="VALID"><orgName>School of Computing - Soongsil University, Séoul</orgName>
<desc><address><addrLine>Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://com_e.ssu.ac.kr/</ref>
</desc>
<listRelation><relation active="#struct-300888" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300888" type="direct"><org type="institution" xml:id="struct-300888" status="VALID"><orgName>Soongsil University, Seoul</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00097239</idno>
<idno type="halId">hal-00097239</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00097239</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00097239</idno>
<date when="2006">2006</date>
<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>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">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="1"><hal:affiliation type="researchteam" xml:id="struct-2366" status="OLD"><idno type="RNSR">200318302K</idno>
<orgName>Combination of approaches to the security of infinite states systems</orgName>
<orgName type="acronym">CASSIS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/cassis</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-866" type="direct"></relation>
<relation active="#struct-242365" type="indirect"></relation>
<relation active="#struct-300261" type="indirect"></relation>
<relation active="#struct-300360" type="indirect"></relation>
<relation name="UMR6174" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-866" type="direct"><org type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno>
<idno type="RNSR">200412232H</idno>
<orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName>
<orgName type="acronym">FEMTO-ST</orgName>
<desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.femto-st.fr</ref>
</desc>
<listRelation><relation active="#struct-242365" type="direct"></relation>
<relation active="#struct-300261" type="direct"></relation>
<relation active="#struct-300360" type="direct"></relation>
<relation name="UMR6174" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-242365" type="indirect"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno>
<idno type="ISNI">0000 0001 2188 3779 </idno>
<orgName>Université de Franche-Comté</orgName>
<orgName type="acronym">UFC</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.univ-fcomte.fr</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300261" type="indirect"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName>
<orgName type="acronym">UTBM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300360" type="indirect"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName>
<orgName type="acronym">ENSMM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR6174" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city" wicri:auto="siege">Besançon</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de Franche-Comté</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName>
<placeName><settlement type="city" wicri:auto="siege">Belfort</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de technologie de Belfort-Montbéliard</orgName>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno>
<orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName>
<orgName type="acronym">VEGAS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/vegas</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-121665" status="VALID"><orgName>Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<orgName type="acronym">KAIST</orgName>
<desc><address><addrLine>335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://www.kaist.edu/edu.html</ref>
</desc>
<listRelation><relation active="#struct-365285" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-365285" type="direct"><org type="institution" xml:id="struct-365285" status="INCOMING"><orgName>Korea Advanced Institute of Science and Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
<author><name sortKey="Hyeon Suk, Na" sort="Hyeon Suk, Na" uniqKey="Hyeon Suk N" first="Na" last="Hyeon-Suk">Na Hyeon-Suk</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7891" status="VALID"><orgName>School of Computing - Soongsil University, Séoul</orgName>
<desc><address><addrLine>Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://com_e.ssu.ac.kr/</ref>
</desc>
<listRelation><relation active="#struct-300888" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300888" type="direct"><org type="institution" xml:id="struct-300888" status="VALID"><orgName>Soongsil University, Seoul</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
</analytic>
<series><title level="j">Discrete Mathematics</title>
<idno type="ISSN">0012-365X</idno>
<imprint><date type="datePub">2006</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><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 P.~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 $\Theta(2^{n/2})$ in the worst case, regardless of the dimension~$d$.</div>
</front>
</TEI>
</HAL>
<INIST><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>
</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>
</double>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005625 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/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= Curation |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. | ![]() |