Random lattice triangulations

structure and algorithms

Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer

Research output: Contribution to journalArticle

9 Citations (Scopus)
54 Downloads (Pure)

Abstract

The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in R 2 whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation σ has weight λ |σ| , where λ is a positive real parameter, and |σ| is the total length of the edges in σ . Empirically, this model exhibits a “phase transition” at λ=1 (corresponding to the uniform distribution): for λ<1 distant edges behave essentially independently, while for λ>1 very large regions of aligned edges appear. We substantiate this picture as follows. For λ<1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for λ>1 we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations.
Original languageEnglish
Pages (from-to)1650-1685
Number of pages36
JournalAnnals of Applied Probability
Volume25
Issue number3
DOIs
Publication statusPublished - Jun 2015

Fingerprint

Triangulation
Integer Points
Point in a polygon
Glauber Dynamics
Mixing Time
Geometric object
Algebraic Geometry
Uniform distribution
Markov chain
Polynomial time
Phase Transition
Decay

Cite this

Random lattice triangulations : structure and algorithms. / Caputo, Pietro; Martinelli, Fabio; Sinclair, Alistair; Stauffer, Alexandre.

In: Annals of Applied Probability, Vol. 25, No. 3, 06.2015, p. 1650-1685.

Research output: Contribution to journalArticle

Caputo, Pietro ; Martinelli, Fabio ; Sinclair, Alistair ; Stauffer, Alexandre. / Random lattice triangulations : structure and algorithms. In: Annals of Applied Probability. 2015 ; Vol. 25, No. 3. pp. 1650-1685.
@article{cab962f99331424296b464fa3c9f76f5,
title = "Random lattice triangulations: structure and algorithms",
abstract = "The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in R 2 whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation σ has weight λ |σ| , where λ is a positive real parameter, and |σ| is the total length of the edges in σ . Empirically, this model exhibits a “phase transition” at λ=1 (corresponding to the uniform distribution): for λ<1 distant edges behave essentially independently, while for λ>1 very large regions of aligned edges appear. We substantiate this picture as follows. For λ<1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for λ>1 we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations.",
author = "Pietro Caputo and Fabio Martinelli and Alistair Sinclair and Alexandre Stauffer",
year = "2015",
month = "6",
doi = "10.1214/14-AAP1033",
language = "English",
volume = "25",
pages = "1650--1685",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "3",

}

TY - JOUR

T1 - Random lattice triangulations

T2 - structure and algorithms

AU - Caputo, Pietro

AU - Martinelli, Fabio

AU - Sinclair, Alistair

AU - Stauffer, Alexandre

PY - 2015/6

Y1 - 2015/6

N2 - The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in R 2 whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation σ has weight λ |σ| , where λ is a positive real parameter, and |σ| is the total length of the edges in σ . Empirically, this model exhibits a “phase transition” at λ=1 (corresponding to the uniform distribution): for λ<1 distant edges behave essentially independently, while for λ>1 very large regions of aligned edges appear. We substantiate this picture as follows. For λ<1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for λ>1 we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations.

AB - The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in R 2 whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation σ has weight λ |σ| , where λ is a positive real parameter, and |σ| is the total length of the edges in σ . Empirically, this model exhibits a “phase transition” at λ=1 (corresponding to the uniform distribution): for λ<1 distant edges behave essentially independently, while for λ>1 very large regions of aligned edges appear. We substantiate this picture as follows. For λ<1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for λ>1 we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations.

UR - http://www.e-publications.org/ims/submission/AAP/user/submissionFile/14254?confirm=c1c1ae8d

UR - http://dx.doi.org/10.1214/14-AAP1033

U2 - 10.1214/14-AAP1033

DO - 10.1214/14-AAP1033

M3 - Article

VL - 25

SP - 1650

EP - 1685

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 3

ER -