Disse tions orientations and trees

Description

Niveau: Supérieur, Doctorat, Bac+8
Disse tions, orientations, and trees, with appli ations to optimal mesh en oding and to random sampling ÉRIC FUSY and GILLES SCHAEFFER LIX, É ole polyte hnique, Fran e and DOMINIQUE POULALHON LIAFA, Université Paris 7, Fran e We present a bije tion between some quadrangular disse tions of an hexagon and unrooted binary trees, with interesting onsequen es for enumeration, mesh ompression and graph sampling. Our bije tion yields an e ient uniform random sampler for 3- onne ted planar graphs, whi h turns out to be determinant for the quadrati omplexity of the urrent best known uniform random sampler for labelled planar graphs [Fusy, Analysis of Algorithms 2005?. It also provides an en oding for the set P(n) of n-edge 3- onne ted planar graphs that mat hes the entropy bound 1 n log 2 jP(n)j = 2+ o(1) bits per edge (bpe). This solves a theoreti al problem re ently raised in mesh ompression, as these graphs abstra t the ombinatorial part of meshes with spheri al topology. We also a hieve the optimal parametri rate 1 n log 2 jP(n; i; j)j bpe for graphs of P(n) with i verti es and j fa es, mat hing in parti ular the optimal rate for triangulations.

• spheri al


• algorithm


• derived maps


• appli ation leads


• tra ed ba


• uniform sampling


• algorithms


• rooted


• random generation


• maps

Sujets

• Algorithm

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 10
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Dissections,
orien
tations,
and
for
edded
Sub
trees,
=
with
for
applications
origin
to
2
optimal
sphere
mesh
??

algorithm
ding
dditional
and
Bender
to
)
random
set
sampling
Whitney
?RIC
ote
FUSY
edge.
and
indep
GILLES
a
SCHAEFFER
et
LIX,
Com
?cole
ting,
p
traced
olytechnique,
al
F
asymptotic
rance
ij
and

DOMINIQUE
i
POULALHON
to
LIAF
tially
A,
study
Universit?
where
P
d
a
No.
ris
This
7,
terest,
F
ey
rance
t
W
graphs
e
wing
presen
[
t
T
a
and

generation
b
ork
et
an
w
mer-
een
where
some
of
quadrangular
(
dissections
3
of
i
an
2
hexagon

and
elled)
unro
j
oted
2
binary
By
trees,
ha
with
b
in
omorphisms,
teresting
that


for
a
en
and
umeration,
mark
mesh
Name,

20YY,
and
planar
graph
is
sampling.
t
Our
it

a
yields
t
an
t

dra
t

uniform

random
Graph
sampler
Categories
for
Descriptors:

Mathematics
planar
algorithms
graphs,
Algorithms
whic
W
h

turns
ding,
out
INTRODUCTION
to
this
b
b
e
k
determinan
of
t
the
for
an
the
[Bender

ask

simple
y
remark
of
ula
the
i;


t
2
b

est
j
kno
2
wn
+
uniform
for
random
of
sampler

for
graphs
lab
er-
elled
and
planar
+
graphs
n
[
y
F
theorem
usy
these
,
e
Analysis
unique
of
on
Algorithms
to
2005
that
℄
ts
It
r
also

pro
maps
vides
map
an
em

the
ding
o
for
with
the
orien
set
CM
P
ol.
(
Mon
n
ages
)

of
map.
n
algorithm
-edge
of

enden
planar
in
graphs
and
that
is
matc

hes
k
the
ingredien
en
in
trop

y
straigh
b
line
ound
wing
1
for
n
planar
log
[
2
hon
jP
al.,
(
Dra
n
℄
)
and
j

=
G.2.1
2
Discrete
+
℄
o
binatorial
(1)
General
bits
erms:
p
A
er
Key
edge
ords
(bp
Phrases:
e).
Coun
This
Co
solv
Random
es
1.
a
One

of
problem
w


tly
e
raised

in
to
mesh


Ed
as
in
these
A
graphs
ic

Mathematic
the
Monthly

℄
binatorial
he
part
ed
of
a
meshes
explanation
with
the

able
top
form
ology
jP
.
n;
W
j
e
j
also
1
ac
5
hiev
4
e
n
the
2
optimal
2
parametric
+
rate

1
j
n
i
log
2
2
(1)
jP
the
(
y
n;
the
i;
of
j
(unlab
)
planar
j
with
bp
v
e

for

graphs
n
of
i
P
j
(
edges,
n
going
)
innit
with
.
i
a
v
of

[1933],
and
graphs
j
v

essen
matc
a
hing
em
in
edding
particular
the
the
up
optimal
home-
rate
so
for
their
triangulations.
amoun
Our
to

of
ding
o
relies
d
on
onne
a
d
linear
,
time
a
algorithm
is
to
graph

b
an
in
orien
plane
tation
r
asso
ote

means
to
a
the
ed
minimal
ted
Sc
A
hn
Journal
yder
V
w
V,
o
N,
o
th
d
P
of
10
a
.2

?ric
F
the
ds.
algorithms
usy
Let
et
uniform
al.
n
1.1
ula
Graphs,

dissections
outputs
and
in
trees
1.1
Another
and
kno
j
wn
the
prop
t
ert
plane
y
uniform
of
with

e
planar
t
graphs
N,
with
of
n
with
edges
5
is
3-
the
b


that
are
they
ondence
are

in
form

b
one-to-one


i.e.,
ondence
P
with
all
dissections
uniform
of
rst
the
oulalhon
sphere
are
in
A
to
v
n
the
quadrangles
b
that
ro
ha
to
v
as
e
jP
no
er

i

Mullin
The
whic
heart
It
of
o
our
of
pap
binary
er
that
lies

in

a
leading
further
of
one-to-one
r

v
ondence.
[1964]
Theorem
A
1.1.
is
Ther
ro
e
giv
is
t
a
ro
one-to-one
equal

same
orr
0
esp

ondenc

e
ph
b
et
etwe
℄
en
ran-
unr
testing
o
ra
ote
V
d
quite
binary
ed.
tr

e
represen
es
n
with
jP
n
coun
no

des
edges
and
utte
unr
renemen
o
in
ote
that
d
ij
quadr
um
angular
ro
disse
maps


of
(due
an
Sc
hexagon
[1968])
with
F
n
follo
interior
explains
vertic
of
es

and
pro
no
since

ypical

en
The
men
mapping
one-to-one
from
ecializes
binary
to
trees
triangulations
to
with
dissections,
degree
whic
the
h
deriv
w

e
for

ote
the
with

originally
e
Bro
,

is
Random
easily
b
describ
Theorem
ed

and
sampler
resem

bles
algorithm

n
that
random
w
the
ere
n


tly
edges
prop
hances
osed
ts.
for
yield
simpler
for
kinds
.
of
generation
maps
maps

or
haeer
w
1997;
in
Bouttier
(see
et
b
al.
1994;
2002;
Sc
P
v
oulalhon
es
and
planar
Sc
used
haeer
dra
℄
[de
The
et
pro
Journal
of
V,
that
th
the
in
mapping
olv
is
Theorem
a
leads

to
is
implicit
instead
tation
rather
the

um
relying
ers
on
0
new
j
prop
ting
erties
oted
of
maps

n
orien
due
tations
T
[Ossona
[1963]),
de
its
Mendez
t
℄
discussed
related

to
yields
Sc
of
hn
0
yder
j
w
n
o
b
o
of
ds
oted
of

triangulations
with
and
v

and
planar

maps
to

and
hn
hellen
yder
erg
1990;
from
di
h
Battista
orm
et
(1)
al.
ws.
1999;
partially
F
the
elsner

℄
the
.

Con
of
v

ersely

,
binomials,
the
these

t
of
of
the
tree
tree
umerations.
from
us
the
tion
dissection
the
relies

on
sp
a
par-
linear

time

algorithm
plane
to
(i.e.,

maps
the
all
minimal
of
Sc
3),
hn
to
yder
rst
w
e
o
ation
o
the
ds
ting
of
ula
a
un-

o
map
d
(or
triangulations
equiv
i
alen

tly
found
,
y
the
wn
minimal
using

metho
0
1.2
-orien
sampling
tation

of
ypro
the
of
asso
1.1

an
deriv
t
ed
random
map,
for
see