\documentclass[12pt]{article}
\usepackage{e-jc,amsmath,amssymb,amsthm}
\usepackage{tikz,xspace,wrapfig,array}

\usetikzlibrary{patterns}
\usepackage[ruled,linesnumbered,vlined,commentsnumbered]{algorithm2e}
\usepackage{pgfplots}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}

\newcommand{\dhl}[1]{\ensuremath{\downharpoonleft{\hspace*{-.4em} #1}}}

\newcommand{\ind}{0.8}
\newcommand{\longueur}{24+\ind}
\newcommand{\largeur}{8}
\newcommand{\A}{\ensuremath{\mathcal A_{L,l,\alpha}}\xspace}
\newcommand{\C}{\ensuremath{\mathcal C}\xspace}
\def\note#1{\marginpar{\tiny\it #1}}
\newcommand{\Z}{\ensuremath{\mathcal Z}}
\newcommand{\polyo}{\ensuremath{\mathfrak p}\xspace}
\newcommand{\ie}{\emph{i.e.}\xspace}
\newcommand{\eg}{\emph{e.g.}\xspace}

%\bibliographystyle{plain}
\usepackage{filecontents}
%
\begin{filecontents}{biblio.bib}
@article{B74,
title = "Convex n-ominoes ",
journal = "Discrete Mathematics ",
volume = "8",
number = "3",
pages = "219 - 226",
year = "1974",
note = "",
issn = "0012-365X",
doi = "10.1016/0012-365X(74)90134-4",
url = "http://www.sciencedirect.com/science/article/pii/0012365X74901344",
author = "Edward A. Bender"
}



@article{BMRR06,
author = {Barequet, G. and Moffie, M. and Rib\'o, A. and Rote, G.},
title = {Counting Polyominoes on Twisted Cylinders},
journal = {INTEGERS},
year = {2006},
OPTkey = {},
volume = {6},
OPTnumber = {},
pages = {A22},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
OPTurl = {},
OPTdoi = {},
OPTissn = {},
OPTlocalfile = {},
abstract = {Using numerical methods, we analyze the growth in the number of polyominoes on
a twisted cylinder as the number of cells increases. These polyominoes are related to
classical polyominoes (connected subsets of a square grid) that lie in the plane. We thus
obtain improved lower bounds on the growth rate of the number of these polyominoes,
which is also known as Klarner's constant}
}

@article{KR73,
    AUTHOR = {Klarner, D. A. and Rivest, R. L.},
     TITLE = {A procedure for improving the upper bound for the number of
              {$n$}-ominoes},
   JOURNAL = {Canad. J. Math.},
  FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de
              Math\'ematiques},
    VOLUME = {25},
      YEAR = {1973},
     PAGES = {585--602},
      ISSN = {0008-414X},
   MRCLASS = {05A20},
  MRNUMBER = {MR0323587 (48 \#1943)},
MRREVIEWER = {R. C. Read}
}

@Article{G54,
author = {Golomb, S.W.},
title = {Checker Boards and Polyominoes},
journal = {The American Mathematical Monthly, Advances in Applied Mathematics},
year = {1954},
OPTkey = {},
volume = {61},
number = {10},
pages = {675--682},
month = {Dec},
OPTnote = {},
OPTannote = {},
OPTurl = {},
OPTdoi = {},
OPTissn = {},
OPTlocalfile = {},
OPTabstract = {}
}

@article{DV84,
  author    = {Marie-Pierre Delest and
               G{\'e}rard Viennot},
  title     = {Algebraic Languages and Polyominoes Enumeration},
  journal   = {Theor. Comput. Sci.},
  volume    = {34},
  year      = {1984},
  pages     = {169-206},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{CR03,
  author    = {Giusi Castiglione and
               Antonio Restivo},
  title     = {Reconstruction of L-convex Polyominoes},
  journal   = {Electronic Notes in Discrete Mathematics},
  volume    = {12},
  year      = {2003},
  pages     = {290-301},
  ee        = {http://dx.doi.org/10.1016/S1571-0653(04)00494-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{CFRR05,
  author    = {Giusi Castiglione and
               Andrea Frosini and
               Antonio Restivo and
               Simone Rinaldi},
  title     = {Enumeration of L-convex polyominoes by rows and columns},
  journal   = {Theor. Comput. Sci.},
  volume    = {347},
  number    = {1-2},
  year      = {2005},
  pages     = {336-352},
  ee        = {http://dx.doi.org/10.1016/j.tcs.2005.06.031},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DRS08,
  author    = {Enrica Duchi and
               Simone Rinaldi and
               Gilles Schaeffer},
  title     = {The number of Z-convex polyominoes},
  journal   = {Advances in Applied Mathematics},
  volume    = {40},
  number    = {1},
  year      = {2008},
  pages     = {54-72},
  ee        = {http://dx.doi.org/10.1016/j.aam.2006.07.004},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

\end{filecontents}
%
\usepackage[style=numeric,backend=bibtex]{biblatex}
\bibliography{biblio}

\date{\dateline{Aug 29, 2011}{?}\\ \small Mathematics Subject Classification:  05A05, 05A16, 05A19}

\title{Counting $k$-convex polyominoes\thanks{This work was completed
    with the support of the ANR (project 
    MAGNUM ANR-2010-BLAN-0204).}}
\author{Anne Micheli\\ LIAFA UMR 7089, Universit\'e Paris Diderot
    and CNRS, \\ Case 7014, 75205 Paris, France.\\ \and  Dominique Rossin\\ LIX UMR 7161, Ecole
    Polytechnique and CNRS, \\91128 Palaiseau, France.}
\begin{document}
\maketitle
\begin{abstract}
 We compute an asymptotic estimate of a lower bound of the number of $k$-convex polyominoes of semiperimeter $p$. This approximation can be written as $\mu(k) p 4^p$ where 
$\mu(k)$ is a rational fraction of $k$ which up to $\mu(k)$ is the asymptotics of convex polyominoes. 
\end{abstract}


A polyomino is a connected set of unit square cells drawn in the plane $\Z \times \Z$ \cite{G54}. The size of a polyomino is the number of its cells.  A central problem, which proved to be difficult, is to find exactly or even asymptotically  $A(n)$, the number a polyominoes of size $n$. Klarner proves that $\lim_{n \rightarrow \infty} \sqrt[n]{A(n)}$ exists and is upper bounded by $4.64$ \cite{KR73}.  The lower bound was recently improved up to $3.98$ \cite{BMRR06}. 

In order to approximate the number of polyominoes, subclasses have been introduced, one of them being {\em convex} polyominoes. A horizontal, resp. vertical, convex polyomino is a polyomino for which each 
row, resp. column, is convex. Figure \ref{fig:convPol} gives an
example of horizontal but not vertical convex polyomino and of a
horizontal and vertical convex polyomino called {\em convex}
polyomino. Bender gives an asymptotic estimate $fr^{-n}$ of the number
of convex polyominoes with $n$ cells, $f$ and $r$ being numerical
constants \cite{B74}.

\begin{figure}[h]
 \begin{center}
  
\begin{tikzpicture}[scale=.3]
\useasboundingbox (0,0) rectangle (15,5);
\draw [help lines] (0,0) grid (8,5);
\draw [ultra thick] (0,0) grid (2,1);
\draw [ultra thick] (0,1) grid (7,2);
\draw [ultra thick] (5,2) grid (6,3);
\draw [ultra thick] (4,3) grid (8,4);
\draw [ultra thick] (1,4) grid (7,5);
\end{tikzpicture}
\begin{tikzpicture}[scale=.3]
\draw [help lines] (0,0) grid (8,5);
\draw [ultra thick] (3,0) grid +(2,1);
\draw [ultra thick] (1,1) grid +(4,1);
\draw [ultra thick] (0,2) grid +(8,1);
\draw [ultra thick] (2,3) grid +(2,1);
\draw [ultra thick] (3,4) grid +(1,1);

\end{tikzpicture}

\caption{a horizontal (but not vertical) convex polyomino and a convex polyomino}\label{fig:convPol}
 \end{center}

\end{figure}

Convex polyominoes are often considered according to number of rows
and columns, called semiperimeter. Delest and Viennot \cite{DV84}
prove that the number of convex polyominoes of semiperimeter 
$p+4$ is $f_{p+4} = (2p+11)4^p-4(2p+1){2p \choose p} \sim 2p 4^p$. 

In \cite{CR03}, Castiglione and Restivo observe that in a convex
polyomino each pair of cells can be joined by a monotone path
(monotone means that it contains only two kinds of steps, \eg East
$(1,0)$ and North $(0,1)$ or East and South $(0,-1)$).  
The minimal number $k$ of turns in the monotone paths linking two
cells gives rise to a parameter which we call the {\em complexity}, and is
the basis of how we shall classify  polyominoes here. 
A polyomino is called {\em $k$-convex} if every pair of cells can be
connected with a path of complexity at most $k$ and there exists a
path of complexity $k$ linking two cells. Examples of $k$-convex 
($k = 0,1,2$) polyominoes are given in Figure \ref{fig:kConvexPolyomino}.


$1$-convex polyominoes are also called $L$-convex \cite{CR03},
$2$-convex polyominoes are also denoted $Z$-convex. The generating
function  for $L$-convex polyominoes where the variable $t$ marks
semiperimeter is given by $G(t) = \frac{1-2t+t^2}{1-4t+2t^2}$
\cite{CFRR05}. $Z$-convex polyominoes have been recently studied by
Duchi, Rinaldi and Schaeffer \cite{DRS08} who compute the rational
generating function and provide an asymptotics in $\frac{p}{24} 4^p$
when the semiperimeter is $p+2$. 

In this article we provide a lower bound for the number of $k$-convex polyominoes for any $k$ and show that the asymptotics is also $\mu(k) p 4^p$.
The key idea in this article is to transform a random walk into a set
of polyominoes. Random walks are chosen with small deviation. Thus the
boundary of the obtained polyominoes is delimited by two
rectangles and we show that in that case, the polyominoes are $k$-convex.
The first section gives basic definitions and first results on random
walks with small deviations and polyominoes. In the second section, we
describe the algorithm that tranform one random walk into a set of
bounded polyominoes and prove its correctness. Finally, in the last
section, we give the asymptotic number of a lower bound of $k$-convex polyominoes.

\section{Small deviation random walks and polyominoes}

\subsection{Random walks}

A random walk of size $n$ is a sequence of $n$ steps in the plane
chosen uniformly at random between $(0,1)$, called ${\mathbf n}$ step,
and $(1,0)$, called ${\mathbf e}$ step. 
Figure \ref{fig:randomWalk} illustrates the parameter called
the \emph{deviation of a walk}. This is the maximal distance between the walk and the first
diagonal. 
Here we consider only those walks with deviation smaller that $c \sqrt
n$. This restriction is justified by the following proposition, which
is a direct consequence of the central limit theorem:

\begin{prop}
The number of random walks of size $n$ with deviation less than $c \sqrt n$ is asymptotically $\lambda 2^n$ where $\lambda = \lambda(c)$.
\end{prop}

\begin{center}
\begin{figure}[ht]
\begin{minipage}[b]{.4\textwidth}
\begin{tikzpicture}
\begin{scope}[scale=.3]
\draw[help lines,fill, lightgray] (1,2) rectangle +(1,1);
\draw[help lines,fill, lightgray] (3,2) rectangle +(1,1);
\useasboundingbox (0,0) rectangle (6,8);
\draw [help lines] (0,0) grid (5,5);
\draw [ultra thick] (1,2) grid (4,3);
\draw[thick, dotted] (1.5,2.5) -- (3.5,2.5);
\end{scope}
\begin{scope}[scale=.3,xshift=200]
\useasboundingbox (0,0) rectangle (8,8);
\draw[help lines,fill, lightgray] (3,5) rectangle +(1,1);
\draw[help lines,fill, lightgray] (5,2) rectangle +(1,1);
\draw [help lines] (0,0) grid (7,7);
\draw [ultra thick] (1,2) grid +(1,2);
\draw [ultra thick] (2,1) grid +(1,5);
\draw [ultra thick] (3,1) grid +(1,5);
\draw [ultra thick] (4,2) grid +(1,3);
\draw [ultra thick] (5,2) grid +(1,2);
\draw[thick, dotted] (3.5,5.5) -- (3.5,2.5) -- (5.5,2.5);
\draw (2.5,1) node[below] {{\tiny{$\mathbf{S}$}}};
\draw (6.5,2.5) node {{\tiny{$\mathbf{E}$}}};
\draw (3.5,6) node[above] {{\tiny{$\mathbf{N}$}}};
\draw (.5,3.5) node {{\tiny{$\mathbf{W}$}}};
\end{scope}
\begin{scope}[scale=.3,xshift=100, yshift=240]
\draw[help lines,fill, lightgray] (1,5) rectangle +(1,1);
\draw[help lines,fill, lightgray] (6,2) rectangle +(1,1);
\draw [help lines] (0,0) grid (8,8);
\draw [ultra thick] (1,5) grid +(1,1);
\draw [ultra thick] (2,4) grid +(1,3);
\draw [ultra thick] (3,3) grid +(1,4);
\draw [ultra thick] (4,2) grid +(1,4);
\draw [ultra thick] (5,1) grid +(1,4);
\draw [ultra thick] (6,2) grid +(1,2);
\draw[thick, dotted] (1.5,5.5) -- (4.5,5.5) -- (4.5,2.5) -- (6.5,2.5) ;
\draw (0.5,5.5) node {{\tiny{$\mathbf{W}$}}};
\draw (3.5,7.5) node {{\tiny{$\mathbf{N}$}}};
\draw (5.5,0.5) node {{\tiny{$\mathbf{S}$}}};
\draw (7.5,2.5) node {{\tiny{$\mathbf{E}$}}};
\end{scope}
\end{tikzpicture}
\caption{A $0$,$1$,$2$-convex polyomino}\label{fig:kConvexPolyomino}
\end{minipage}
\begin{minipage}[b]{.6\textwidth}
\centering\begin{tikzpicture}[scale=0.2]
\draw[help lines] (0,0) grid (23,23);
   \draw[thick] (0,0)  --node (S2){} ++(1,0) -- ++(0,1) -- ++(1,0) --  ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(1,0)  -- ++(1,0) -- ++(1,0) -- ++(0,1) --++(1,0) -- ++(1,0) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(0,1) --  ++(1,0) -- ++(0,1) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(1,0) -- ++(1,0) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(1,0) -- ++(1,0) -- ++(0,1) -- ++(1,0) -- ++(1,0);
\draw[dashed, very thick] (0,0) -- (23,23);
\draw [gray, dotted, thick] (4,0) -- (25,21);
\draw [gray, dotted, thick] (0,4) -- (19,23);
\draw[<->] (23,23) -- node[above,sloped] {{\small deviation}} (25,21);
\end{tikzpicture}
\caption{A random walk of size $46$}\label{fig:randomWalk}
\end{minipage}

\end{figure}
\end{center}


\subsection{$k$-convex polyominoes}


They are several paths that join two selected cells. Among the paths of minimal complexity we can choose a canonical one as stated in the following lemma.

\begin{lem}[Canonical path of minimal complexity]
 For each pair of points $P,Q$ with complexity $h$, there exists a path joining $P$ and $Q$ with $h$ turns such that each
turn (except perhaps the last one) lies on the border of the polyomino.
\end{lem}

\begin {proof}
Let $w = u_1 u_2 \ldots u_{h+2}$ be a path joining $u_1=P$ and $u_{h+2}=Q$. Let $i \geq 2$ be the smallest integer such
that $u_i$ does not belong to the border. If $i = h+1$ then the Lemma is verified. Otherwise, the idea is to shift the
point $u_i$ by $1$ along the segment $[u_{i-1},u_i]$ as shown in Figure \ref{fig:border}. Three cases could occur:
\begin{itemize}
 \item $(i)$ The new path has the same number of turns and point $u_i$ is closer to the border of the polyomino by $1$
unit. 
\item $(ii)$ The new path has $h-1$ turns, at points $u_2,\ldots, u_h$, which contradicts the fact that $P$ and $Q$ are
at distance $h$.
\item $(iii)$ The new path has $h-1$ turns, at points $u_2,\ldots, u_i,u_{i+2},\ldots,u_{h+1}$, since point $u_{i+1}$ is
not a turn anymore which contradicts the fact that $P$ and $Q$ are at distance $h$.
\end{itemize}
Thus, only the first case $(i)$ occurs and repeating the shift, we obtain a new path where $u_i$ is on the border.
$u_2,\ldots,u_{i-1}$ have not been moved and thus lie on the border.

\begin{figure}[h]
\begin{center}

\begin{tikzpicture}[scale=0.3]
 \draw (0,5) -- (0,4) -- (1,4) -- (1,2) -- (2,2) -- (2,1) -- (3,1) -- (3,0);
 \draw (4,7) -- (4,6) -- (6,6) -- (6,5) -- (7,5) -- (7,3) -- (8,3) -- (8,1);
\draw [very thick] (2,5) -- (2,4) -- (5,4) -- (5,2);
\draw [very thick, dotted] (2,4) -- (2,3) -- (5,3);
\draw [fill] (2,4) circle  (7pt);
\draw [fill] (5,4) circle  (7pt);

\draw (2,4) node [left] {$u_i$};
\draw (5,4) node [right] {$u_{i+1}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.3]
 \draw (0,5) -- (0,4) -- (1,4) -- (1,2) -- (2,2) -- (2,1) -- (3,1) -- (3,0);
 \draw (4,7) -- (4,6) -- (6,6) -- (6,5) -- (7,5) -- (7,3) -- (8,3) -- (8,1);
\draw [very thick] (2,5) -- (2,4) -- (5,4) -- (5,3);
\draw [very thick, dotted] (2,4) -- (2,3) -- (5,3);
\draw [fill] (2,4) circle  (7pt);
\draw [fill] (5,4) circle  (7pt);
\draw [fill] (5,3) circle  (7pt);

\draw (5,3) node [right] {$Q$};

\draw (2,4) node [left] {$u_i$};
\draw (5,4) node [right] {$u_{i+1}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.3]
 \draw (0,5) -- (0,4) -- (1,4) -- (1,2) -- (2,2) -- (2,1) -- (3,1) -- (3,0);
 \draw (4,7) -- (4,6) -- (6,6) -- (6,5) -- (7,5) -- (7,3) -- (8,3) -- (8,1);
\draw [very thick] (2,5) -- (2,4) -- (5,4) -- (5,3) -- (7,3);
\draw [very thick, dotted] (2,4) -- (2,3) -- (5,3);
\draw [fill] (2,4) circle  (7pt);
\draw [fill] (5,4) circle  (7pt);

\draw (2,4) node [left] {$u_i$};
\draw (5,4) node [right] {$u_{i+1}$};
\end{tikzpicture}
  \caption{Cases $(i),(ii),(iii)$ for a path joining $P$ and $Q$ }\label{fig:border}
\end{center}
\end{figure}

\end {proof}

Moreover it is straightforward that only pairs of points on the boundary of the polyomino must be taken into account
when computing the convexity. More precisely, Figure \ref{fig:kConvexPolyomino}
displays four special points on the boundary which play a key role, the north point $N$ (resp. $W, S$ and $E$) being the first northern cell  of the polyomino preceded by a lower one, encountered by a counterclockwise walk around it.

\subsection{$k$-bounded polyominoes}

Typically, the  shape of random $k$-convex polyominoes resembles a
rectangle rotated by $\pi/4$, such that the ratio of height to length
is a function of $k$. We  introduce a subclass of $k$-convex polyominoes that we call {\em $k$-bounded polyominoes}. 
More precisely, a $k$-bounded polyomino is a convex polyomino whose boundary is at a small distance from such a rectangle.

Formally, there exists $l > 0$ such that the boundary lies within a rectangular strip of width  $\alpha = \frac{l}{4k}$ delimited by two rectangles, a $L \times l$ one with $L=(k-1)l+\frac{l}{2k}$, and a smaller one at distance $\alpha$ (see Figure \ref{fig:polyomino}).


\begin{figure}
 \begin{center}

\begin{tikzpicture}
\tikzstyle{remplissage}=[thick,pattern=crosshatch];
\tikzstyle{ligne}=[thick];
\tikzstyle{bleu}=[blue!30,thick];
\tikzstyle{bleuP}=[blue!30,thick,dotted];
\tikzstyle{rouge}=[red,thick];
\tikzstyle{rougeP}=[red,thick,dotted];
\tikzstyle{jaune}=[yellow];

\useasboundingbox (0,0) rectangle (8,8);
\begin{scope}[scale=.25]
\draw [remplissage] (\longueur,0) -- (0,\longueur) -- (\largeur,\longueur+\largeur) -- (\longueur+\largeur,\largeur) -- (\longueur,0);
\draw [fill=white] (\longueur,\ind) -- (\ind,\longueur) -- (\largeur,\longueur+\largeur-\ind) -- (\longueur+\largeur-\ind,\largeur) -- (\longueur,\ind);
\draw [<->] (0,0) -- node[above] {$\frac{L}{\sqrt 2}$}  (\longueur,0);
\draw [<->] (0,0) -- node[right] {$\frac{L}{\sqrt 2}$}  (0,\longueur);
\draw [>-<] (0,18) -- node[below] {${\sqrt 2}\alpha$} (\ind,18);

%\draw [>-<] (0,\longueur+\largeur) -- node[below] {$\frac{l}{\sqrt 2}$}  (\largeur,\longueur+\largeur);
%\draw[help lines] (0,\longueur) -- (0,\largeur+\longueur);
\draw (\largeur/2,\longueur+\largeur/2) node[above] {$l$};
\draw (\largeur+0.5*\longueur,\largeur+0.5*\longueur) node[above] {$L$};

\draw [help lines] (\ind,18) -- (\ind,\longueur);
\draw[bleu] (0,\longueur) -- (\largeur+\largeur,\longueur) -- (\largeur+\largeur,\longueur-2*\largeur) -- (4*\largeur,\longueur-2*\largeur) --  (4*\largeur,\longueur-2*\largeur-\ind) --  (4*\largeur+\ind,\longueur-2*\largeur-\ind);
\draw[bleuP] (\ind,\longueur) -- (2*\largeur-\ind,\longueur) -- (2*\largeur-\ind,\longueur-2*\largeur+2*\ind) -- (4*\largeur-3*\ind,\longueur-2*\largeur+2*\ind) -- (4*\largeur-3*\ind,\longueur-2*\largeur-\ind) --  (4*\largeur+\ind,\longueur-2*\largeur-\ind);
\draw[rouge] (\largeur,\largeur+\longueur) -- (\largeur,\longueur-\largeur) -- (3*\largeur,\longueur-\largeur) -- (3*\largeur,\ind) -- (3*\largeur+\ind,\ind) -- (3*\largeur+\ind,0);
\draw[rougeP] (\largeur,\largeur+\longueur-\ind) -- (\largeur,\longueur-\largeur+\ind) -- (3*\largeur-2*\ind,\longueur-\largeur+\ind) -- (3*\largeur-2*\ind,4*\ind) --(3*\largeur+\ind,4*\ind) -- (3*\largeur+\ind,0);
\draw[jaune,fill=yellow,opacity=0.5] (\largeur/2,\longueur+\largeur/2) -- (\largeur/2+\ind,\longueur+\largeur/2) -- (\largeur/2,\longueur+\largeur/2-\ind) -- (\largeur/2,\longueur+\largeur/2);
\draw[jaune,fill=yellow,opacity=0.5] (\largeur/2,\longueur+\largeur/2) -- (1.5*\largeur,\longueur+\largeur/2) -- (1.5*\largeur+\ind,\longueur+\largeur/2-\ind) -- (\largeur/2,\longueur+\largeur/2-\ind) -- (\largeur/2,\longueur+\largeur/2);
\draw[jaune,fill=yellow,opacity=0.5] (1.5*\largeur-\ind,\longueur+\largeur/2) -- (1.5*\largeur+\ind,\longueur+\largeur/2-\ind) -- (1.5*\largeur+\ind,\longueur-1.5*\largeur-\ind) -- (1.5*\largeur-\ind,\longueur-1.5*\largeur+\ind);
\draw[jaune,fill=yellow,opacity=0.5] (1.5*\largeur+\ind,\longueur-1.5*\largeur-\ind) -- (1.5*\largeur-\ind,\longueur-1.5*\largeur+2*\ind) -- (3.5*\largeur-2*\ind,\longueur-1.5*\largeur+2*\ind) -- (3.5*\largeur+\ind,\longueur-1.5*\largeur-\ind);
\draw[jaune,fill=yellow,opacity=0.5] (3.5*\largeur-3*\ind,\longueur-1.5*\largeur+2*\ind) -- (3.5*\largeur+\ind,\longueur-1.5*\largeur-\ind) -- (3.5*\largeur+\ind,\longueur-2.5*\largeur-\ind) -- (3.5*\largeur-3*\ind,\longueur-2.5*\largeur-5*\ind);
\draw[orange,fill=orange,opacity=0.5] (\largeur/2,\longueur+\largeur/2) -- (\largeur/2+\ind,\longueur+\largeur/2) -- (\largeur/2+\ind,\longueur-0.5*\largeur-\ind) -- (\largeur/2,\longueur-0.5*\largeur);
\draw[orange,fill=orange,opacity=0.5] (\largeur/2+\ind,\longueur-0.5*\largeur-\ind) -- (\largeur/2,\longueur-0.5*\largeur+\ind) -- (2.5*\largeur-\ind,\longueur-0.5*\largeur+\ind) -- (2.5*\largeur+\ind,\longueur-0.5*\largeur-\ind);
\draw[orange,fill=orange,opacity=0.5]  (2.5*\largeur-2*\ind,\longueur-0.5*\largeur+\ind) -- (2.5*\largeur+\ind,\longueur-0.5*\largeur-\ind) --  (2.5*\largeur+\ind,\longueur-2.5*\largeur-\ind) -- (2.5*\largeur-2*\ind,\longueur-2.5*\largeur+2*\ind);
\draw[orange,fill=orange,opacity=0.5] (2.5*\largeur+\ind,\longueur-2.5*\largeur-\ind) -- (2.5*\largeur-2*\ind,\longueur-2.5*\largeur+3*\ind) -- (\longueur+\largeur-\ind,\longueur-2.5*\largeur+3*\ind) -- (\longueur+\largeur-5*\ind,\longueur-2.5*\largeur-1*\ind);
\draw [ligne] (\longueur,\ind) -- (\ind,\longueur) -- (\largeur,\longueur+\largeur-\ind) -- (\longueur+\largeur-\ind,\largeur) -- (\longueur,\ind);

\draw (0,\longueur) node[left] {W};
\draw (\largeur,\largeur+\longueur) node[above] {N};
\draw (\largeur+\longueur,\largeur) node[right] {E};
\draw (\longueur,0) node[below] {S};

\draw [remplissage] (\largeur+3,\longueur+\largeur-1) rectangle +(2,1);
\draw  (\largeur+6,\longueur+\largeur-0.5) node[right] {Area of polyomino's border};
\draw [rouge] (\largeur+5,\longueur+\largeur-3) -- +(2,0);
\draw [bleu] (\largeur+5,\longueur+\largeur-3.2) -- +(2,0);
\draw [rougeP] (\largeur+5,\longueur+\largeur-3.4) -- +(2,0);
\draw [bleuP] (\largeur+5,\longueur+\largeur-3.6) -- +(2,0);
\draw (\largeur+8,\longueur+\largeur-3) node [right] {Extremal paths};
\draw [orange, fill=orange, opacity=0.5] (\largeur+8,\longueur+\largeur-6) rectangle +(2,1);
\draw [yellow, fill=yellow, opacity=0.5] (\largeur+8,\longueur+\largeur-7) rectangle +(2,1);
\draw (\largeur+11,\longueur+\largeur-6) node [right] {Complexity computing};

\end{scope}
\end{tikzpicture}
\caption{Definition of $k$-bounded polyominoes ($k=4$)}
\label{fig:polyomino}
\end{center}
\end{figure}

The values have been chosen such that the plain, resp. dashed,
line which represents the monotone path linking extremal cells (N/S or E/W
if $k$ is even and N/E or S/W if $k$ is odd) of the outer, resp. inner, rectangle has $k$ turns. 
Indeed, the choice of $L,l$ is such that every polyomino  that is $k$-bounded, is also $k$-convex as stated in the following theorem:

\begin{thm}
A $k$-bounded polyomino  is $k$-convex.\label{prop:kconvex}
\end{thm}

\begin{proof}
By definition of $k$-convexity, the complexity of every path linking a
pair of points in the polyomino must be less than $k$ and at
least one pair must be of complexity $k$. 

To ensure the k-convexity for every $k$-bounded polyomino, it is enough to check 
this result for some specific paths.
Similarly to the definition of point $N$ of a polyomino, we denote by
$N_0$, resp. $N_1$, the northest point of the outer, resp. inner,
rectangle, the same goes for the other directions $S,E,W$ (Figure
\ref{fig:endExternalRay} displays point $S_0$ and $S_1$).

We call external (resp. internal) path, the monotone path 
linking extremal points of the outer $L\times l$  (resp. inner
$(L-2\alpha)\times (l-2\alpha)$) rectangle
 (Figure \ref{fig:polyomino} displays the external, resp. internal, path in
plain, resp. dashed, line).  

Remark that the external (resp. internal) path linking $N_0$ (resp. $N_1$)
to $S_0$ (resp. $S_1$) has an even number of turns whereas the external 
(resp. internal) path linking $N_0$ (resp. $N_1$)
to $E_0$ (resp. $E_1$) has an odd number of turns. In the following, we will consider
an even $k$, meaning that we will work with the extremal path linking $N_0$ (resp. $N_1$)
to $S_0$ (resp. $S_1$), but the same holds for an odd $k$, considering then 
the extremal path linking $N_0$ (resp. $N_1$) to $E_0$ (resp. $E_1$).

$L = (k-1)l+2 \alpha$ ensures
that the external path ends up as shown in Figure
\ref{fig:endExternalRay}, thus has complexity $k$, \ie the complexity of the monotone path linking any point on
segment $[N_0N_1]$ and any point on segment $[S_0S_1]$ is at least $k$. 
Thus, $k$-bounded polyominoes  are at least $k$-convex. 


The complexity of the internal path between $N_1$ and $S_1$ is at least the
same as the complexity of the external one, but it can be greater. 
Figure \ref{fig:endExternalRay} illustrates the increase by
$\alpha\sqrt 2$ in the distance between the internal and external path
at each turn. Thus, after $k-1$ turns the distance
between them is $(k-1)\alpha\sqrt 2$.
But this distance is also constrained by the fact that the
internal path must not reach point $S_1$ in more than $k$ turns. This
implies that (see Figure \ref{fig:endExternalRay}):
$$(k-1)\sqrt 2 \alpha  + (\sqrt 2 \alpha +1)\leq \sqrt 2 (l-2\alpha)$$
A simple calculation shows that $\alpha \leq \frac{l-1/\sqrt 2}{k+2}$ is required.


\begin{figure}
{\tiny
\begin{tikzpicture}[scale=.3]
\useasboundingbox (-5,-4) rectangle (15,14);
\draw [help lines] (0,0) grid (15,10);
 \draw [very thick] (0,10) -- (10,0) -- (15,5) -- (10,10);
\draw[very thick] (2,10) -- (10,2) -- (13,5) -- (8,10);
\draw[black!50, very thick] (10,0) -- (10,3) -- (7,3) -- (7,11);
\draw[very thick,black!50, dotted] (4,11) -- (4,8) -- (10,8) -- (10,3);
\draw[<->] (4,11) -- node[above] {$(k-1)\alpha \sqrt 2 $} (7,11);
\draw[<->] (4,-3) -- node[below] {$\sqrt 2(l-2\alpha)$} (10,-3);
\draw (5,1) node (t) {$(k-1)^{th}$ turn};
\draw[thick,->,shorten >= 4pt] (t) -- (7,3);
\draw[thick,->,shorten >= 4pt] (t) -- (4,8);
\draw[<->] (13,3) -- node[above right] {$\alpha$} (12,4);
\draw[<->] (7,-1) -- node[below] {$\sqrt 2 \alpha + 1$} (10,-1);
\useasboundingbox (17,-2) rectangle (37,14);
\draw [help lines] (22,0) grid (37,10);
\draw (32,-0.5) node {{\tiny$\mathbf{S_0}$}};
\draw (32.8,2.3) node {{\tiny$\mathbf{S_1}$}};
 \draw [very thick] (22,10) -- (32,0) -- (37,5) -- (32,10);
\draw[very thick] (24.5,10) -- (32,2.5) -- (34.5,5) -- (29.5,10);
\draw[black!50, very thick] (32,0) -- (32,3) -- (29,3) -- (29,11);
\draw[very thick,black!50, dotted] (26,11) -- (26,8.5) -- (31,8.5) -- (31,3.5) -- (32,3.5) -- (32,3);
%\draw[<->] (4,11) -- node[above] {$(k-1)\alpha \sqrt 2 $} (7,11);
%\draw[<->] (-1,8) -- node[left] {$(l-\alpha)\sqrt 2$} (-1,0);
\draw (27,1) node (t) {$(k-1)^{th}$ turn};
\draw[thick,->,shorten >= 4pt] (t) -- (29,3);
\draw[thick,->,shorten >= 4pt] (t) -- (26,8);
\draw[<->] (35,3) -- node[above right] {$\alpha$} (33.75,4.25);
%\draw[<->] (7,-1) -- node[below] {$\sqrt 2 \alpha + 1$} (10,-1);
\end{tikzpicture}
}
\caption{End of the internal/external paths}\label{fig:endExternalRay}
\end{figure}

In order to obtain $k$-convexity, we determine the value of $\alpha$ such that
the complexity of the monotone path linking any pair of points $(A,B)$ is at most $k$. 
We call a segment the border of a polyomino between two specified points
$A$ and $B$, turning clockwise from $A$ to $B$. 
For $k \geq 2$, 
we can restrict positions of $A$ (resp. $B$) to be on the 
segment WN (resp. segment ES).

The first step of any path from $A$ to $B$ goes from $A$ to $A'$, 
which belongs to one of the extremal paths, and follows it as shown
in Figure \ref{fig:everyPath} until reaching $B'$ (which is the point
on the $(k-1)^{\mbox{th}}$ segment of the internal path at the same 
ordinate than $B$) and then goes to
$B$. This path has exactly $k$ turns. Each internal path, the one linking
$N_1$ to $S_1$ and the one linking $W_1$ to $E_1$, allows to
reach a part of the segment ES. To cover all this
segment, the two parts must intersect. This situation occurs when the internal path starting from
$N_1$ (resp. $W_1$) ends on segment $E_1S_1$ on the half part containing $S_1$ (resp. $E_1$).
It gives the following inequalities~: 
\begin{eqnarray*}
& L +l - 2\alpha -k(l-2\alpha) \leq \frac{l}{2} & 
\left(\mbox{resp. } k (l-2\alpha) \geq L - 2\alpha+\frac{l}{2} \right)\\
\Leftrightarrow & ((k-1)l+2\alpha)+l - 2\alpha -k(l-2\alpha) \leq \frac{l}{2}&\\
\Leftrightarrow & \alpha \leq \frac{l}{4k} &
\end{eqnarray*}
Thus $\alpha = \frac{l}{4k}$ refines the previous value if $l>1$ and $k\geq 2$.

%\note{Attention il faut changer tous les W en N car on a un pb de parit�entre les dessins et le texte}

\begin{figure}
\tiny
\begin{center}
\begin{tikzpicture}
\tikzstyle{remplissage}=[thick,pattern=crosshatch];
\tikzstyle{ligne}=[thick];
% \tikzstyle{bleu}=[blue!30,thick];
% \tikzstyle{bleuP}=[blue!30,thick,dotted];
% \tikzstyle{rouge}=[red,thick];
% \tikzstyle{rougeP}=[red,thick,dotted];
% \tikzstyle{jaune}=[yellow];
\tikzstyle{bleu}=[black!40,thick];
\tikzstyle{bleuP}=[black!40,thick,dotted];
\tikzstyle{rouge}=[black!70,thick];
\tikzstyle{rougeP}=[black!70,thick,dotted];
\tikzstyle{jaune}=[black!20];

\useasboundingbox (-5.5,3) rectangle (8,5);
\begin{scope}[rotate=45,yshift=-\longueur, scale=.2]%[rotate around={45:(\longueur ,0)},scale=.20]
\draw [remplissage] (\longueur,0) -- (0,\longueur) -- (\largeur,\longueur+\largeur) -- (\longueur+\largeur,\largeur) -- (\longueur,0);
\draw [fill=white] (\longueur,\ind) -- (\ind,\longueur) -- (\largeur,\longueur+\largeur-\ind) -- (\longueur+\largeur-\ind,\largeur) -- (\longueur,\ind);
%\draw [<->] (0,0) -- node[above] {$\frac{L}{\sqrt 2}$}  (\longueur,0);
%\draw [<->] (0,0) -- node[right] {$\frac{L}{\sqrt 2}$}  (0,\longueur);
%\draw [>-<] (0,18) -- node[below] {$\frac{\alpha}{\sqrt 2}$} (\ind,18);

%\draw [>-<] (0,\longueur+\largeur) -- node[below] {$\frac{l}{\sqrt 2}$}  (\largeur,\longueur+\largeur);
%\draw[help lines] (0,\longueur) -- (0,\largeur+\longueur);
%\draw (\largeur/2,\longueur+\largeur/2) node[above] {$l$};
%\draw (\largeur+0.5*\longueur,\largeur+0.5*\longueur) node[above] {$L$};

%\draw [help lines] (\ind,18) -- (\ind,\longueur);
\draw[opacity=.3,fill=black!30] (0,\longueur) -- (\largeur,\longueur) -- (\largeur,\largeur+\longueur);
\draw[opacity=.3,fill=black!30] (3*\largeur-2*\ind,4*\ind) --(3*\largeur+5*\ind,4*\ind) -- (\longueur+\largeur,\largeur) -- (3*\largeur-2*\ind,\largeur);
\draw[bleu] (0,\longueur) -- (\largeur+\largeur,\longueur) -- (\largeur+\largeur,\longueur-2*\largeur) -- (4*\largeur,\longueur-2*\largeur) --  (4*\largeur,\longueur-2*\largeur-\ind) --  (4*\largeur+\ind,\longueur-2*\largeur-\ind);
\draw[bleuP] (\ind,\longueur) -- (2*\largeur-\ind,\longueur) -- (2*\largeur-\ind,\longueur-2*\largeur+2*\ind) -- (4*\largeur-3*\ind,\longueur-2*\largeur+2*\ind) -- (4*\largeur-3*\ind,\longueur-2*\largeur-5*\ind); %(4*\largeur+\ind,\longueur-2*\largeur-\ind);
\draw[rouge] (\largeur,\largeur+\longueur) -- (\largeur,\longueur-\largeur) -- (3*\largeur,\longueur-\largeur) -- (3*\largeur,\ind) -- (3*\largeur+\ind,\ind) -- (3*\largeur+\ind,0);
\draw[rougeP] (\largeur,\largeur+\longueur-\ind) -- (\largeur,\longueur-\largeur+\ind) -- (3*\largeur-2*\ind,\longueur-\largeur+\ind) -- (3*\largeur-2*\ind,4*\ind) --(3*\largeur+5*\ind,4*\ind);% -- (3*\largeur+\ind,0);
\coordinate (A) at (.3*\largeur,\longueur+.3*\largeur);
\draw[fill] (A) circle (15pt) node[above left] {$A$};
\draw[fill] (\largeur,\longueur+.3*\largeur) circle (12pt) node[right] {$A'$};
\draw[fill] (\longueur+0.6*\largeur,.6*\largeur) circle (15pt) node[right] {$B$};
\draw[fill] (\longueur-\ind,.6*\largeur) -- node[above left] {$B'$} +(-2*\ind,0);
%\draw[fill] (\longueur-\ind,.6*\largeur) -- ci +(-2*\ind,0);
\fill (\longueur-3*\ind,.6*\largeur) circle (12pt);

\end{scope}

\end{tikzpicture}
\caption{Paths with $k$ turns in a $k$-convex polyomino.}
\label{fig:everyPath}
\end{center}
\end{figure}


\end{proof}

\section{An algorithm deriving a set of $k$-bounded polyominoes from a
random walk }

\subsection{Description of the algorithm}
Let $w = w_1 w_2 \ldots w_{2p-6}$ be a random walk made of an odd number of East steps ({\bf e}) and an odd number of North steps ({\bf n}). 
We give an algorithm to transform this walk
into a set $S_w$ of k-convex polyominoes of perimeter $2p$. The proof of the correctness of our algorithm will be given in the next
section. In this algorithm, we cut the path into different pieces and apply reflections on each piece. For example, $\overleftarrow{w_i}$ is 
the symmetry along the vertical axis and can be seen as the transformation of ${\mathbf e}$ (resp. ${\mathbf w}$) step into ${\mathbf w}$ (resp. ${\mathbf e}$) step. Similarly, $\dhl{w_i}$ 
is the reflection along the horizontal axis (exchange of ${\mathbf n}$ and ${\mathbf s}$ steps).

\begin{figure}
\begin{algorithm}[H]
\label{algo:bendwalk}
\SetKwData{I}{i}
\SetKwData{E}{$E_w$}

\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{$w=w_1\,w_2\,\ldots\,w_{2p-6}$ a random path made of North and East steps, $i \in \{1 \ldots 2p-6\}$}
\Output{A convex polyomino $w'$ of perimeter $2p$}

Let $j$ maximal such that $|w_1,w_2,\ldots,w_{j-1}|_{\mathbf{n}} = |w_j,w_{j+1},\ldots,w_{2p-6}|_{\mathbf{n}}$ + 1\;
Let $k$ maximal such that $|w_1,w_2,\ldots,w_{i-1}|_{\mathbf{e}}+|w_{k},w_{k+2},\ldots,w_{2p-6}|_{\mathbf{e}} = |w_{i},w_{i+1},\ldots,w_{k-1}|_{\mathbf{e}}$ + 1\;
$w' \leftarrow {\bf e} w_1\,w_2\,\ldots\,w_{i-1}\,{\bf nw}\,\overleftarrow{w_i}\ldots \overleftarrow{w_{j-1}}\,{\bf
w} \dhl{\overleftarrow{w_j}} \ldots  \dhl{\overleftarrow{w_{k-1}}} {\bf s} \dhl{w_k}
\ldots \dhl{w_{2p-6}} {\bf s}$\;
\caption{Function $\mathtt{BendWalk}$}
\end{algorithm}

\begin{algorithm}[H]
\SetKwFunction{bendWalk}{BendWalk}
\SetKwData{I}{i}
\SetKwData{eps}{$\epsilon$}
\SetKwData{E}{$E_w$}

\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{$c \in [0,1]$, $w=w_1\,w_2\,\ldots\,w_{2p-6}$ a  path with deviation less than $c \sqrt p$, $k$ the expected convexity}
\Output{\E a set of $k$-convex polyominoes of perimeter $2p$}
  $\alpha \gets \frac{p}{4 k^2 + 2}$, $l \gets 4k\alpha$;\\
  \lForEach{\I in $[\sqrt2 (l - \alpha -  \frac{\alpha}{6}) , \sqrt2 (l - \alpha +  \frac{\alpha}{6})]$}{\bendWalk{w,\I}}
\caption{Function $\mathtt{Polyominoes}$}
\end{algorithm}\label{algo}
\end{figure}


\subsection{Correctness}\label{sec:correctness}

The correctness of the algorithm is done in two steps. First, we prove
that it outputs a set of polyominoes. Then, we prove that those
polyominoes are asymptotically $k$-bounded, hence $k$-convex by Theorem \ref{prop:kconvex}. 

Notice first that the obtained geometric shape is closed. This is a
direct consequence of the form of $w'$ in step $3$ of function
$\mathtt{BendWalk}$ and the conditions described in step $1$ and $2$.  Moreover it is a polyomino as $w'$ is a closed self-avoiding walk in the plane. Recalling that $w' \leftarrow {\bf {\mathbf s}{\mathbf e}} w_1\,w_2\,\ldots\,w_{i-1}\,{\bf {\mathbf n}{\mathbf w}}\,\overleftarrow{w_i}\ldots \overleftarrow{w_{j-1}}\,{\bf
{\mathbf w}} \dhl{\overleftarrow{w_j}} \ldots  \dhl{\overleftarrow{w_{k-1}}} {\bf {\mathbf s}} \dhl{w_k}
\ldots \dhl{w_{2p-6}}$, this defines four different segments, the
first one beeing made of ${\mathbf e}$ and ${\mathbf n}$ steps, the
next ones consisting in ${\mathbf n}$ and ${\mathbf w}$ steps, then
${\mathbf w}$ and ${\mathbf s}$ steps and finally ${\mathbf s}$ and
${\mathbf e}$  steps. For the path to intersect itself, the only possibilities are in each change of directions or between two opposite segments. 
The first possibility is forbidden by the insertion of some steps between each segment (printed in bold face). The second possibility cannot  happen since  the initial walk has a deviation bounded by $c \sqrt p$, which is less than half the distance (recall $l = {\mathcal O}(p)$) between opposite segments.

The second step is to prove that the obtained polyominoes  are asymptotically $k$-bounded. In fact, we can prove this result for all output polyominoes, nevertheless, we only need an asymptotic behaviour which is easier to prove. 


We consider the strip ${\mathcal S}$ of width  $\alpha$ and  outer rectangle of size $L \times l$ where $L = (k-1) + \frac{l}{2k}$. The starting point of our polyomino is $S$, the south point. Notice first that if $\hat{w}$ is the {\em alternating path} $({\mathbf n}{\mathbf e})^{+}$ and $i = l-\alpha$, the obtained polyomino is the closest to the median rectangle. Since the path has small deviation, this implies the following statistics on :

\begin{itemize}
\item the number $n$ of steps between the south point, \ie the origin, and each  corner,
\item the difference $d$ between the number of ${\mathbf n}$ and ${\mathbf e}$ steps at the same points,
\end{itemize}

\begin{tabular}{|c|c|c|c|c|}
\hline
 & $S$ & $E$ & $N$ & $W$\\
 \hline
 $n$ & $0$ & $i \in [l-\alpha \pm \frac{\alpha}{6}]$ &  $j \in [p \pm {\mathcal O}( \sqrt{p}) ]$ & $k \in [p+i \pm {\mathcal O}( \sqrt{p}) ]$ \\
 \hline
 $|d|$ &  $0$ &  $\leq c \sqrt{i}$ &  ${\mathcal O}(\sqrt p)$ &  ${\mathcal O}(\sqrt p)$ \\
 \hline
\end{tabular}

\hspace*{1cm} 

For example, the point $N$ separates the path into two parts, the
first one having one more north step than the second one. Since the
deviation is bounded by $c \sqrt{p}$, $w_1 \ldots w_p$ contains nearly
half of the north steps.
This implies the result for $j$ and for $d$. 
The same argument holds for point $W$. 

Considering the alternating path $\hat{w}$ and a given $i$, it is straightforward to prove that the obtained polyomino $P(\hat{w},i)$ stays within the strip and moreover the distance between this polyomino and the border of the strip is bounded by $\frac{\alpha}{6}$.
To conclude our proof,  given another path and a value $i$, the distance between the obtained polyomino and $P(\hat{w},i)$ is bounded by the sum of all possible deviations at each corner that is ${\mathcal O}(\sqrt p)$. Since $\alpha = {\mathcal O}(p)$, the polyomino lies asymptotically in the strip.



\begin{thm}
Algorithm $\mathtt{BendWalk}$ defines an injection between the set of
random walks
with a distinguished step and the set of convex polyominoes.
\end{thm}\label{thm:injectif}

\begin{proof}
In fact, given the output polyomino by function $\mathtt{BendWalk}(w,i)$, it is straightforward to recover the arguments $w$ and $i$. 
To do so, notice that the added steps in the algorithm can be deduced from the points $E,N,W,S$ of the polyomino.
\end{proof}

\subsection{Enumeration of $k$-bounded polyominoes}

As shown in Section \ref{sec:correctness}, Algorithm $\mathtt{BendWalk}$ outputs a subset of $k$-bounded polyominoes. Hence we have:
\begin{thm}
The number of $k$-bounded, hence $k$-convex, polyominoes is asymptotically at least
$\mu \frac{p}{k^2} 4^p$, where $\mu$ is a constant. 
Furthermore, the number of $k$-convex polyominoes is asymptotically ${\mathcal{O}}(p 4^{p})$.
\end{thm}

\begin{proof}
By Theorem \ref{thm:injectif}, function ${\mathtt{BendWalk}}$ is injective and outputs one polyomino. The number of calls for a given walk $w$ is exactly  $\sqrt{2} \frac{\alpha}{3}$. The number of possible walks of length $2p-6$ with deviation bounded by $c \sqrt{p}$ is $\lambda(c) 2^{2p-6}$ by central-limit theorem. Taking the expression of $\alpha$ in $p$, the number of $k$-bounded polyominoes is asymptotically at least $\mu \frac{p}{k^2} 4^p$.
\end{proof}

\section{Conclusion}

The result provided is an asymptotic estimate of a lower bound of the number of
$k$-convex polyominoes. The estimate is ${\mathcal O}(p 4^p)$ for
every value of $k$. A more precise result including the function
$\mu(k)$ would be relevant but unfortunately our approach cannot
approximate the correlation with $k$. 

 Nevertheless, the two graphs below seem to point out that $k$-convex
 polyominoes of semiperimeter $p$ have an asymtotics in
 $\mathcal{O}(\frac{1}{k^2}(p-4)4^{p-4})$. 

The following figures depict experimental results obtained by uniform sampling of 
convex polyominoes of semiperimeter $p=302$. For each polyomino we compute its $k$-convexity and in the first diagram we draw the first  ratios $P_k/P_{k+1}$ between two consecutive numbers of
$k$-convex polyominoes. The plot seems to have a finite limit when $k$
increases. The second diagram plots $F(k)$ the number of $k$-convex polyominoes divided by $(p-4) 4^{p-4}$ with respect to $k$. It
seems to show that the asymptotic number of $k$-convex polyominoes is also
in $\mathcal{O}(\frac{1}{k^2})$.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.9]
\begin{axis}[ xlabel=$k$,
ylabel=$P_{k}/P_{k+1}$
]
\addplot[color=blue,mark=*]
table[x=k,y=ratio] {data.table.tex};
\end{axis}
\end{tikzpicture}
\begin{tikzpicture}[scale=.9]
\begin{axis}[ xlabel=$k$,
ylabel=$F(k)$
]
\addplot[color=blue,mark=*]
table[x=k,y=Fk] {data-table2.tex};
\addplot [color=red,domain=2:30, samples=100]{14.0/(x^(2)+x+1)/3.0};
\end{axis}
\end{tikzpicture}

\caption{Experimental results on the asymptotic number of $k$-convex polyominoes}
\end{center}
\end{figure}

\printbibliography

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
