InforLorV4, PascalFrancis, Corpus, bibRecord, 000431

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

Identifieur interne : 000431 ( PascalFrancis/Corpus ); précédent : 000430; suivant : 000432

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

Auteurs : Véronique Cortier ; Xavier Goaoc ; Mira Lee ; Hyeon-Suk Na

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.

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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0012-365X`
A02	`01`			`@0 DSMHA4`
A03		`1`		`@0 Discrete math.`
A05				`@2 306`
A06				`@2 16`
A08	`01`	`1`	`ENG`	`@1 A note on maximally repeated sub-patterns of a point set`
A11	`01`	`1`		`@1 CORTIER (Véronique)`
A11	`02`	`1`		`@1 GOAOC (Xavier)`
A11	`03`	`1`		`@1 LEE (Mira)`
A11	`04`	`1`		`@1 NA (Hyeon-Suk)`
A14	`01`			`@1 LORIA - CNRS, 615 rue du Jardin Botanique, B.P. 101 @2 54602 villers-les-Nancy @3 FRA @Z 1 aut.`
A14	`02`			`@1 LORIA- INRIA Lorraine, 615 rue du Jardin Botanique, B.P. 101 @2 54602 Villers-les-Nancy @3 FRA @Z 2 aut.`
A14	`03`			`@1 Division of Computer Science, Korea Advanced Institute of Science and Technology (KAIST), 373-1, Guseong-dong @2 Yuseong-gu, Daejeon 305-701 @3 KOR @Z 3 aut.`
A14	`04`			`@1 School of Computing, Soongsil University, 1-1, Sangdo-dong @2 Dongjak-gu, Seoul 156-743 @3 KOR @Z 4 aut.`
A20				`@1 1965-1968`
A21				`@1 2006`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 15322 @5 354000142263110150`
A44				`@0 0000 @1 © 2006 INIST-CNRS. All rights reserved.`
A45				`@0 2 ref.`
A47	`01`	`1`		`@0 06-0398732`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Discrete mathematics`
A66	`01`			`@0 NLD`
C01	`01`		`ENG`	`@0 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.`
C02	`01`	`X`		`@0 001A02F02`
C02	`02`	`X`		`@0 001A02B01B`
C03	`01`	`X`	`FRE`	`@0 Polynôme @5 17`
C03	`01`	`X`	`ENG`	`@0 Polynomial @5 17`
C03	`01`	`X`	`SPA`	`@0 Polinomio @5 17`
C03	`02`	`X`	`FRE`	`@0 Géométrie discrète @5 18`
C03	`02`	`X`	`ENG`	`@0 Discrete geometry @5 18`
C03	`02`	`X`	`SPA`	`@0 Geometría discreta @5 18`
C03	`03`	`X`	`FRE`	`@0 Pire cas @4 INC @5 70`
C03	`04`	`X`	`FRE`	`@0 Ensemble point @4 CD @5 96`
C03	`04`	`X`	`ENG`	`@0 Point set @4 CD @5 96`
C03	`05`	`X`	`FRE`	`@0 Configuration répétée @4 CD @5 97`
C03	`05`	`X`	`ENG`	`@0 Repeated configuration @4 CD @5 97`
N21				`@1 268`

Format Inist (serveur)

NO :	PASCAL 06-0398732 INIST
ET :	A note on maximally repeated sub-patterns of a point set
AU :	CORTIER (Véronique); GOAOC (Xavier); LEE (Mira); NA (Hyeon-Suk)
AF :	LORIA - CNRS, 615 rue du Jardin Botanique, B.P. 101/54602 villers-les-Nancy/France (1 aut.); LORIA- INRIA Lorraine, 615 rue du Jardin Botanique, B.P. 101/54602 Villers-les-Nancy/France (2 aut.); Division of Computer Science, Korea Advanced Institute of Science and Technology (KAIST), 373-1, Guseong-dong/Yuseong-gu, Daejeon 305-701/Corée, République de (3 aut.); School of Computing, Soongsil University, 1-1, Sangdo-dong/Dongjak-gu, Seoul 156-743/Corée, République de (4 aut.)
DT :	Publication en série; Niveau analytique
SO :	Discrete mathematics; ISSN 0012-365X; Coden DSMHA4; Pays-Bas; Da. 2006; Vol. 306; No. 16; Pp. 1965-1968; Bibl. 2 ref.
LA :	Anglais
EA :	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.
CC :	001A02F02; 001A02B01B
FD :	Polynôme; Géométrie discrète; Pire cas; Ensemble point; Configuration répétée
ED :	Polynomial; Discrete geometry; Point set; Repeated configuration
SD :	Polinomio; Geometría discreta
LO :	INIST-15322.354000142263110150
ID :	06-0398732

Links to Exploration step

Pascal:06-0398732

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><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>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation><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>
</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><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>
</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>
</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><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>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation><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>
</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><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>
</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>
<server><NO>PASCAL 06-0398732 INIST</NO>
<ET>A note on maximally repeated sub-patterns of a point set</ET>
<AU>CORTIER (Véronique); GOAOC (Xavier); LEE (Mira); NA (Hyeon-Suk)</AU>
<AF>LORIA - CNRS, 615 rue du Jardin Botanique, B.P. 101/54602 villers-les-Nancy/France (1 aut.); LORIA- INRIA Lorraine, 615 rue du Jardin Botanique, B.P. 101/54602 Villers-les-Nancy/France (2 aut.); Division of Computer Science, Korea Advanced Institute of Science and Technology (KAIST), 373-1, Guseong-dong/Yuseong-gu, Daejeon 305-701/Corée, République de (3 aut.); School of Computing, Soongsil University, 1-1, Sangdo-dong/Dongjak-gu, Seoul 156-743/Corée, République de (4 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Discrete mathematics; ISSN 0012-365X; Coden DSMHA4; Pays-Bas; Da. 2006; Vol. 306; No. 16; Pp. 1965-1968; Bibl. 2 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001A02F02; 001A02B01B</CC>
<FD>Polynôme; Géométrie discrète; Pire cas; Ensemble point; Configuration répétée</FD>
<ED>Polynomial; Discrete geometry; Point set; Repeated configuration</ED>
<SD>Polinomio; Geometría discreta</SD>
<LO>INIST-15322.354000142263110150</LO>
<ID>06-0398732</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

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

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000431 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |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
	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.

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

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

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