Rectangular Dissections and Edge-Flip Chains in Lattice Triangulations
Equitable Rectangular Dissections
Dana Randall
Georgia Institute of Technology
Joint with: Sarah Cannon and Sarah Miracle
Rectangular Dissections
Rectangular dissections arise in:
•
VLSI layout
•
Mapping graphs for floor layouts
•
Combinatorial applications
Equitable Rectangular Dissection
:
A partition of an
n x n
lattice region into
n
2
/a
rectangles or area
a
whose corners
lie on lattice points.
Rectangular Dissections
Partition
n
x
n
lattice region into rectangles such
that:
•
There are
n
2
/a
rectangles each with area
a
•
The corners of rectangles lie on lattice points
The Edge-Flip Chain
Repeat:
1.
Pick an random edge
e
,
2.
Flip edge
e
with prob. ½,
if possible.
Main Questions
:
Does the
Edge-Flip Chain
connect
the
set of rectangular dissections? (Note: need
n=2
k
)
Is it
rapidly mixing
?
Related Tiling Problems / Flip Chains
Domino Tilings
?
?
Polynomial time
mixing
[Luby, R. Sinclair]
[R., Tetali]
Background: Lattice Triangulations
•
Triangulations of
general point sets
:
Open
•
Triangulations of point sets in
convex position
:
Fast
[McShine, Tetali ‘98], [Molloy, Reed, Steiger ‘98]
•
Triangulations on subsets of
Z
2
:
Open
Weighted
Triangulations on subsets of
Z
2
[Caputo, Martinelli, Sinclair, Stauffer ‘13]
Another
Edge-Flip Chain
:
The Edge-Flip chain:
Weight
(σ) = λ
(total
length of edges)
Results
[CMSS]
:
[Pietro Caputo, Fabio Martinelli, Alistair Sinclair and Alexandre Stauffer. “Random
Lattice Triangulations: Structure and Algorithms.”
45
th
Symposium on Theory of
Computing
(STOC), 2013.]
[Caputo, Martinelli, Sinclair, Stauffer ‘13]
Background: Weighted Triangulations
Weighted Rectangular Dissections
let
weight
(σ) = λ
(
total
length of edges)
.
Given
λ > 0
,
The
Weighted
Edge-Flip Chain
Repeat:
1.
Pick a random edge
e.
2.
If
e
is flippable, let
e’
be the new edge it can be flipped to.
3.
Flip edge
e
with probability min ( 1,
(|
e’
|
-
|
e
|)
).
Weighted
Rectangular Dissections
Given
λ > 0
,
λ < 1
λ > 1
let
weight
(σ) = λ
(
total
length of edges)
.
Weighted
Rectangular Dissections
Given
λ > 0
,
λ < 1
λ > 1
let
weight
(σ) = λ
(
total
length of edges)
.
•
Does the Edge-Flip Chain connect the state space?
•
Is there always a move?
But first:
How fast?
Connectivity
Thm
:
The Edge-Flip Chain
connects
the set of dissections of
the n x n lattice region into n rectangles of area n.
It’s not immediately obvious that a valid move even exists!
P
r
o
o
f
s
k
e
t
c
h
:
I
n
d
u
c
t
i
o
n
o
n
“
h
-
r
e
g
i
o
n
s
”
:
•
Simply-connected subset of rectangles from a dissection
•
All rectangles have height at most h
•
All vertical sections on the boundary have height c
.
h
(for some integer c)
For n =16, an 8-region
and a 4-region.
Proof Sketch: Connectivity
Thm 1
:
The Edge-Flip Chain
connects
the set of dissections
of the n x n lattice region into n rectangles of size n.
Proof sketch:
Induction on “
h-regions
”:
•
Prove can tile every h-region with all rectangles of height h
•
Inside every h-region, find an
h
/
2
-region or an h-region with
smaller area
I.H.
h/2
h
h/2
•
Inductively show we can reach tiling with all height n rectangles.
Weighted
Rectangular Dissections
Given
λ > 0
,
λ < 1
λ > 1
let
weight
(σ) = λ
(
total
length of edges)
.
1.
Look at a restricted class of rect. dissections:
Dyadic Tilings
.
How fast?
2. Then we’ll consider the general case.
Dyadic Tilings
A
dyadic tiling
of the
unit
square is a set of
2
k
dyadic rectangles
,
each with area
2
-
k
(whose union is the full square).
Thm
: The
Edge-Flip Chain
connects the set of
dyadic tilings
.
[Janson, R., Spencer ‘02]
Background: Dyadic Tilings
Thm
: Every dyadic tiling has a horizontal or
vertical “fault line” (or both).
Dyadic rectangles:
R =
[
a 2
-s
, (a+1) 2
-s
]
x
[
b 2
-t
, (b+1) 2
-t
]
Let
A
k
be the number of tilings with
2
k
rectangles of area
2
-k
.
Background: Dyadic Tilings
Recursive sampling:
[Janson, R., Spencer
’
02]
V
not
…
(And similarly for
“infinite” tilings.)
Stochastic Approaches: Dyadic Tilings
The Edge-Flip Chain
:
There is a
different
Markov chain
that is rapidly mixing:
[JRS’02]
?
Stochastic Approaches: Dyadic Tilings
The Edge-Flip Chain
:
There is a
different
Markov chain
that is rapidly mixing:
[JRS’02]
?
Rotate any dyadic rectangle (any scale), and dilate if necessary.
Mixing of the Edge-Flip Chain is open.
Results:
Dyadic Tilings
λ = 0.80
λ = 1.00
λ = 1.03
Rigorous proofs all the way to the critical point λ
c
= 1 !
?
Thm
:
[Cannon, Miracle, R. ‘15]
Results:
General
Rectangular Dissections
λ = 0.80
λ = 1.00
λ = 1.03
Exponential mixing for very different reasons
Thm
:
[Cannon, Miracle, R. ‘15]
Proof Sketches
1.
(Dyadic)
When
λ < 1
, the edge-flip chain is
poly
.
2.
(Both)
When
λ > 1
, the edge-flip chain is
exp
.
3.
(General)
When
λ < 1
, the edge-flip chain is
exp
.
Fast Mixing for Dyadic Tilings
Proof Technique:
Path coupling with an exponential metric
[Bubley, Dyer] [Greenberg, Pascoe, R.]
Thm
:
For any constant
λ < 1
, the edge-flip chain on the
set of dyadic tilings converges in time
O(
n
2
log
n
)
.
If two configurations differ by flipping edge
f
to edge
e
, then
the distance between them is
λ
|f|-|e|
.
The coupled configurations are get closer in expectation in each step.
(Rest is standard.)
1.
(Dyadic)
When
λ < 1
, the edge-flip chain is
fast
.
2.
(Both)
When
λ > 1
, the edge-flip chain is
slow
.
3.
(General)
When
λ < 1
, the edge-flip chain is
slow
.
Proof Sketches
Slow Mixing when λ>1
P
r
o
o
f
i
d
e
a
:
S
h
o
w
t
h
a
t
a
b
o
t
t
l
e
n
e
c
k
e
x
i
s
t
s
.
Thm
:
For any constant
λ > 1
, the edge-flip chain requires
time
exp
(
Ω(n
2
)
)
.
The Bottleneck when
λ > 1
At least one
1 x n rectangle
No 1 x n or n x 1
rectangles
At least one
n x 1 rectangle
The Bottleneck when
λ > 1
≥
n(n+1)
≥
n(n+1)
1.
(Dyadic)
When
λ < 1
, the edge-flip chain is
fast
.
2.
(Both)
When
λ > 1
, the edge-flip chain is
slow
.
3.
(General)
When
λ < 1
, the edge-flip chain is
slow
.
Proof Sketches
Slow Mixing λ<1, Gen. Rect. Dis.
P
r
o
o
f
i
d
e
a
:
I
t
i
s
h
a
r
d
t
o
r
e
m
o
v
e
t
w
o
w
e
l
l
-
s
e
p
a
r
a
t
e
d
b
a
r
s
.
T
h
m
:
F
o
r
a
n
y
c
o
n
s
t
a
n
t
λ
<
1
,
t
h
e
e
d
g
e
-
f
l
i
p
c
h
a
i
n
o
n
rectangular dissections requires time
exp
(Ω
(
n
log
n
))
.
Key Ideas:
1.
In order to remove a “bar” you need
two bars next to each other.
2.
If you have 2 separated bars, you must
also have lots of other thin rectangles.
The Bottleneck when
λ<1
Separation ≥ n/2 + 2
Separation < n/2 + 2
At least 4 bars and
separation = n/2 + 2
•
Pair up the bars left to right
•
The
separation
is the sum of the “gaps”
Separation
=
g
1
+
g
2
+ 4
The exponentially small cut implies slow mixing.
Summary and Open Problems
1.
What happens when λ = 1 (dyadic and general tilings)?
2.
What if we allow 90
o
or 180
o
rotations of sub-rectangles?
3.
Decay of correlations? Average edge length? …
4.
Dyadic Tilings:
General Rectangle Dissections:
?
?
With 180
o
Rotations
20,000,000 moves
40,000,000 moves
60,000,000 moves
Simulations with 180
o
rotations:
n = 64,
= 0.8, starting at all vertical
Summary and Open Problems
1.
What happens when λ = 1 (dyadic and general tilings)?
2.
What if we allow 90
o
or 180
o
rotations of sub-rectangles?
3.
Decay of correlations? Average edge length? …
4.
Dyadic Tilings:
General Rectangle Dissections:
?
?
Thank you!
Explore equitable rectangular dissections and their applications in VLSI layout, graph mapping, and combinatorial problems in this scholarly work by Dana Randall from Georgia Institute of Technology. Discover the concept of partitioning an n x n lattice region into n2/a rectangles or areas where corners lie on lattice points, and delve into the intriguing Edge-Flip Chain dynamics, questioning its connectivity and mixing properties. Related tiling problems and weighted triangulations are also discussed in this insightful study.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Equitable Rectangular Dissections Dana Randall Georgia Institute of Technology Joint with: Sarah Cannon and Sarah Miracle
Rectangular Dissections Equitable Rectangular Dissection: A partition of an n x n lattice region into n2/a rectangles or area a whose corners lie on lattice points. Rectangular dissections arise in: VLSI layout Mapping graphs for floor layouts Combinatorial applications
Rectangular Dissections Partition n x nlattice region into rectangles such that: There are n2/a rectangles each with area a The corners of rectangles lie on lattice points The Edge-Flip Chain Repeat: 1. Pick an random edge e, 2. Flip edge e with prob. , if possible. Main Questions: Does the Edge-Flip Chain connect the set of rectangular dissections? (Note: need n=2k) Is it rapidly mixing?
Related Tiling Problems / Flip Chains Domino Tilings Lozenge Tilings Polynomial time mixing [Luby, R. Sinclair] [R., Tetali] Fortresses: PMs on square-oct lattice Lattice Triangulations ? ?
Background: Lattice Triangulations Another Edge-Flip Chain: Triangulations of general point sets: Open Triangulations of point sets in convex position: Fast [McShine, Tetali 98], [Molloy, Reed, Steiger 98] Triangulations on subsets of Z2: Open Weighted Triangulations on subsets of Z2 [Caputo, Martinelli, Sinclair, Stauffer 13]
Background: Weighted Triangulations [Caputo, Martinelli, Sinclair, Stauffer 13] Weight ( ) = (totallength of edges) The Edge-Flip chain: Results [CMSS]:
Weighted Rectangular Dissections let weight ( ) = (totallength of edges). Given > 0, The Weighted Edge-Flip Chain Repeat: 1. Pick a random edge e. 2. If e is flippable, let e be the new edge it can be flipped to. 3. Flip edge e with probability min ( 1, (|e |-|e|) ).
Weighted Rectangular Dissections let weight ( ) = (totallength of edges). Given > 0, < 1 > 1
Weighted Rectangular Dissections let weight ( ) = (totallength of edges). Given > 0, < 1 > 1 How fast? But first: Does the Edge-Flip Chain connect the state space? Is there always a move?
Connectivity Thm: The Edge-Flip Chain connects the set of dissections of the n x n lattice region into n rectangles of area n. It s not immediately obvious that a valid move even exists! Proof sketch: Induction on h-regions : Simply-connected subset of rectangles from a dissection All rectangles have height at most h All vertical sections on the boundary have height c.h (for some integer c) For n =16, an 8-region and a 4-region.
Proof Sketch: Connectivity Thm 1: The Edge-Flip Chain connects the set of dissections of the n x n lattice region into n rectangles of size n. Proof sketch: Induction on h-regions : Prove can tile every h-region with all rectangles of height h Inside every h-region, find an h/2-region or an h-region with smaller area h/2 I.H. h h/2 Inductively show we can reach tiling with all height n rectangles.
Weighted Rectangular Dissections let weight ( ) = (totallength of edges). Given > 0, < 1 > 1 How fast? 1. Look at a restricted class of rect. dissections: Dyadic Tilings. 2. Then we ll consider the general case.
Dyadic Tilings A dyadic rectangle is a region R with dimensions R = [a 2-s, (a+1) 2-s]x [b 2-t, (b+1) 2-t ] , where a, b, s and t are nonnegative integers. Dyadic Not dyadic A dyadic tiling of the unit square is a set of 2k dyadic rectangles, each with area 2-k (whose union is the full square). A dyadic tiling Not a dyadic tiling Thm: The Edge-Flip Chain connects the set of dyadic tilings. [Janson, R., Spencer 02]
Background: Dyadic Tilings Dyadic rectangles: R = [a 2-s, (a+1) 2-s]x [b 2-t, (b+1) 2-t ] Thm: Every dyadic tiling has a horizontal or vertical fault line (or both). Let Ak be the number of tilings with 2k rectangles of area 2-k. Thm: [CLSW, LSV] A0=1, A1=2, and for k 2, Ak = 2 Ak-1 Ak-2 . 2 4 Thm: The asymptotic behavior of Ak is Ak -1 2 , where = 1+ 5 / 2 and 1.8445 k
Background: Dyadic Tilings Recursive sampling: [Janson, R., Spencer 02] V V H H V not H H V V V H V H H V V HV V V H 2 Root: V : An-1 / An 2 2 HHH : (An-1 An-2 )/ An (And similarly for infinite tilings.) 2 2 HHV : An-2 (An-1 An-2 )/ An 2 2 HVH : An-2 (An-1 An-2 )/ An
Stochastic Approaches: Dyadic Tilings The Edge-Flip Chain: ? There is a different Markov chain that is rapidly mixing: [JRS 02]
Stochastic Approaches: Dyadic Tilings The Edge-Flip Chain: ? There is a different Markov chain that is rapidly mixing: [JRS 02] Rotate any dyadic rectangle (any scale), and dilate if necessary. Mixing of the Edge-Flip Chain is open.
Results: Dyadic Tilings = 0.80 = 1.00 = 1.03 Thm: [Cannon, Miracle, R. 15] ? Rigorous proofs all the way to the critical point c= 1 !
Results: GeneralRectangular Dissections = 0.80 = 1.00 = 1.03 Thm: [Cannon, Miracle, R. 15] ? Exponential mixing for very different reasons
Proof Sketches 1. (Dyadic) When < 1, the edge-flip chain is poly. 2. (Both) When > 1, the edge-flip chain is exp. 3. (General) When < 1, the edge-flip chain is exp.
Fast Mixing for Dyadic Tilings Thm:For any constant < 1 , the edge-flip chain on the set of dyadic tilings converges in time O(n2 log n). Proof Technique: Path coupling with an exponential metric [Bubley, Dyer] [Greenberg, Pascoe, R.] If two configurations differ by flipping edge f to edge e, then the distance between them is |f|-|e|. The coupled configurations are get closer in expectation in each step. (Rest is standard.)
Proof Sketches 1. (Dyadic) When < 1, the edge-flip chain is fast. 2. (Both) When > 1, the edge-flip chain is slow. 3. (General) When < 1, the edge-flip chain is slow.
Slow Mixing when >1 Thm:For any constant > 1 , the edge-flip chain requires time exp( (n2)). Proof idea: Show that a bottleneck exists. S S
The Bottleneck when > 1 No 1 x n or n x 1 rectangles At least one 1 x n rectangle At least one n x 1 rectangle
The Bottleneck when > 1 No 1 x n or n x 1 rectangles one 1 x n rectangle one n x 1 rectangle (n2+4)/2 ( )(log n)n n(n+1) n(n+1)
Proof Sketches 1. (Dyadic) When < 1, the edge-flip chain is fast. 2. (Both) When > 1, the edge-flip chain is slow. 3. (General) When < 1, the edge-flip chain is slow.
Slow Mixing <1, Gen. Rect. Dis. Thm: For any constant < 1 , the edge-flip chain on rectangular dissections requires time exp( (n log n)). Proof idea: It is hard to remove two well-separated bars. Key Ideas: 1. In order to remove a bar you need two bars next to each other. 2. If you have 2 separated bars, you must also have lots of other thin rectangles.
The Bottleneck when <1 Pair up the bars left to right The separationis the sum of the gaps Separation = g1 + g2 + 4 At least 4 bars and separation = n/2 + 2 Separation n/2 + 2 Separation < n/2 + 2 The exponentially small cut implies slow mixing.
Summary and Open Problems Dyadic Tilings: ? General Rectangle Dissections: ? 1.What happens when = 1 (dyadic and general tilings)? 2.What if we allow 90o or 180o rotations of sub-rectangles? 3.Decay of correlations? Average edge length? 4.
With 180o Rotations Simulations with 180o rotations: n = 64, = 0.8, starting at all vertical 20,000,000 moves 40,000,000 moves 60,000,000 moves
Summary and Open Problems Dyadic Tilings: ? General Rectangle Dissections: ? 1.What happens when = 1 (dyadic and general tilings)? 2.What if we allow 90o or 180o rotations of sub-rectangles? 3.Decay of correlations? Average edge length? 4.
