Asymptotic analysis and random sampling of digitally convex polyominoes

DOI10.1007/978-3-642-37067-0_9MaRDI QIDQ4924463zbMATH OpenOpenAlexFDO

Authors Olivier Bodini, Philippe Duchon, Alice Jacquot, Ljuben Mutafchiev

Publication date 31 May 2013

Published in Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2108

Mathematics Subject Classification ID

Polyominoes (05B50) Computational aspects related to convexity (52B55) Combinatorial probability (60C05) Combinatorics on words (68R15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Recent work of Brlek extit{et al.} gives a characterization of digitally convex polyominoes using combinatorics on words. From this work, we derive a combinatorial symbolic description of digitally convex polyominoes and use it to analyze their limit properties and build a uniform sampler. Experimentally, our sampler shows a limit shape for large digitally convex polyominoes.

Recommendations

• Generating convex polyominoes at random
• Combinatorial View of Digital Convexity
• First steps in the algorithmic reconstruction of digital convex sets
• Some large polyominoes' perimeter: a stochastic analysis
• On the generation of convex polyominoes

Cited in

(5)

• Large deviations of convex polyominoes
• Further steps on the reconstruction of convex polyominoes from orthogonal projections
• New Stick Number Bounds from Random Sampling of Confined Polygons
• Boltzmann distribution on ``short integer partitions with power parts: limit laws and sampling
• Probability that n points are in convex position in a regular -gon: asymptotic results

This page was built for publication: Asymptotic analysis and random sampling of digitally convex polyominoes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4924463)