uniform Constant-Time Algorithms for Properties of Images
Piotr Berman\thanks{Pennsylvania State University
USA; {\tt berman@cse.psu.edu
We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property (that is, the smallest fraction of pixels that need to change in the image to ensure that the image satisfies the desired property). Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise. Prior to this work, only one tolerant testing algorithm for an image property (image partitioning) has been published. We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so that it becomes a half-plane? a representation of a convex object? a representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error $\eps$, after reading a number of pixels polynomial in $1/\eps$ and independent of the size of the image. The running time of the testers for half-plane and convexity is also polynomial in $1/\eps$. Tolerant testers for these three properties were not investigated previously. For convexity and connectedness, even the existence of distance approximation algorithms with query complexity independent of the input size is not implied by previous work. (It does not follow from the VC-dimension bounds, since VC dimension of convexity and connectedness, even in two dimensions, depends on the input size. It also does not follow from the existence of non-tolerant testers.) Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons $P_\mydelta$ such that (1) every convex image has a nearby polygon in $P_\mydelta$ and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in $P_\mydelta$. This construction might be of independent interest. %We design algorithms that approximate the distance to the three properties within a small additive error that have access only to labeled random samples from the input. Most previous sublinear-time algorithms for image analysis were {\em query-based, that is, they could query pixels of their choice. We consider algorithms with two types of input access: {\em uniform algorithms that draw independent uniformly random pixels, and {\em block-uniform algorithms that draw pixels from independently random square blocks of the image. For the first two, our algorithms are uniform; for connectedness, they are block-uniform. All our algorithms have low sample complexity that depends polynomially on the inverse of the error parameter and is independent of the input size. % % or, equivalently, tolerant testers for being a half-plane, convexity and connectedness. Tolerant testers for these properties, even with query access to the image, were not investigated previously. Tolerance is important in image processing applications because it allows algorithms to be resilient to noise in the image. We also give (non-tolerant) testers for convexity and connectedness with better complexity than our distance approximation algorithms and previously known query-based testers. % %To obtain our algorithms for convexity, we design two fast proper PAC learners of convex sets in two dimensions that work under the uniform distribution: non-agnostic and agnostic. % % %%Specifically, we have (omitting for readability big-O and dependence on delta): % %%-- an agnostic proper PAC learner under the uniform distribution with sample complexity 1/\eps^2 log 1/\eps and time complexity poly(1/\eps); % %%-- a proper PAC learner under the uniform distribution with sample and time complexity 1/\eps^(3/2).
Tolerant-testing-image-properties.tex
\def\withcomments{1}
\def\full{1}
\documentclass[11pt,english]{article}
\usepackage{babel,comment}
\usepackage{amsmath, amsthm, amssymb, url}
\usepackage[numbers,longnamesfirst]{natbib}
\usepackage{verbatim}
%\usepackage[lflt]{floatflt}
\usepackage{cleveref,paralist}
\usepackage[usenames,dvipsnames]{color} % piotr
\usepackage{multirow}
%\usepackage{mathtools}
\usepackage{bigstrut}
\usepackage[disable]{todonotes}
\usepackage{fullpage, bbm}
%\usepackage[f]{esvect}

\usepackage[ruled, noend, noline]{algorithm2e}

\ifnum\full=0
%\usepackage[text={16cm,24cm}]{geometry} %space saving tricks
%\setlength{\parskip}{0cm}
%\setlength{\parindent}{1em}
%\usepackage{mathptmx}
\usepackage[compact]{titlesec}
\titlespacing{\section}{0pt}{2ex}{1ex}
\titlespacing{\subsection}{0pt}{1ex}{1ex}
\titlespacing{\subsubsection}{0pt}{0.5ex}{0ex}
\renewenvironment{itemize}[1]{\begin{compactitem}#1}{\end{compactitem}}
\renewenvironment{enumerate}[1]{\begin{compactenum}#1}{\end{compactenum}}
\fi

% Use \citet (textual, authors listed) and \citep (parenthetic, number only)
\newtheorem{openproblem}{Open Problem}
\newtheorem{question}{Question}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{sublemma}[theorem]{SubLemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{myclaim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{observation}{Observation}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}{Definition}[section]
\newtheorem{defn}[definition]{Definition}

\newtheorem{protocol}{Protocol}%[section]

\numberwithin{figure}{section}
%\numberwithin{table}{section}

\newcommand{\cD}{D} %our notation for domain (has to be different than notation below)
\newcommand{\D}{{\mathcal D}} %our notation for distribution
\newcommand{\cR}{{\mathcal R}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cP}{{\mathcal P}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\C}{{\mathcal C}}
\newcommand{\eps}{{\epsilon}}
\newcommand{\ie}{{\textit i.e. }}
\newcommand{\AND}{\mbox{ and }}
\newcommand{\es}{\varnothing}
\newcommand{\MNM}{\mbox{\sc Mnm}_1}
\newcommand{\dis}{dist}
\newcommand{\Dis}{Dist}
\newcommand{\zeromset}{\{0,1,\dots,m-1\}}
\newcommand{\depth}{t}
\newcommand{\quest}{\text{\sf ?}\xspace}
\newcommand{\onevec}{{\mathbf 1}_d}
\newcommand{\kvec}{{\mathbf k}}
\newcommand{\ste}{{\epsilon\emph{-tester}}}
\newcommand{\tte}{{(\epsilon_{1},\epsilon_{2})\emph{-tester}}}
\newcommand{\de}{{\mydelta\emph{-additive-estimator}}}

\newcommand{\Accept}{\textbf{Accept}\xspace}
\newcommand{\accept}{\textbf{accept}\xspace}
\newcommand{\Reject}{\textbf{Reject}\xspace}
\newcommand{\reject}{\textbf{reject}\xspace}

\newcommand{\integerset}[1]{[0..{#1})}
\newcommand{\domain}{\integerset{n}^2}
%\newcommand{\pf}{\textbf{p}}
\newcommand{\gp}{\text{GP}}
\newcommand{\side}{r}
\newcommand{\rblock}{$\side$-block\xspace}
\newcommand{\rblocks}{$\side$-blocks\xspace}
\newcommand{\blockxy}{\ensuremath{B_\side(x,y)}\xspace}
\newcommand{\lind}{t} %level index

\newcommand{\UH}{\text{UH}}
\newcommand{\LH}{\text{LH}}
\newcommand{\hull}{\text{Hull}}

\newcommand{\Best}{{\sf Best}\xspace}
\newcommand{\Stv}{{\sf StValid}\xspace}
\newcommand{\Compst}{{\sf ComputeStatus}\xspace}
\newcommand{\Constgr}{{\sf ConstructGraph}\xspace}

\newcommand{\mindist}{{\sf MinDist}\xspace}
\newcommand{\BestFixed}{{\sf Best For Fixed Base}\xspace}
\newcommand{\errle}{\dout_{\text{left}}}
\newcommand{\errri}{\dout_{\text{right}}}
\newcommand{\Tend}{{\bf T}_{\text{end}}}
\newcommand{\Tfin}{{\bf T}_{\text{fin}}}
\newcommand{\Tcut}{{\bf T}_{\text{cut}}}

\newcommand{\Tstart}{{\bf T}_0}
\newcommand{\stripset}{{\bf R}}
\newcommand{\triset}{{\bf T}}
\newcommand{\qset}{{\bf Q}}
\newcommand{\err}{\mbox{\it err}_S}
\newcommand{\con}{144}
\newcommand{\bm}{B_M}
\newcommand{\bmp}{B_{M'}}
\newcommand{\hp}[2]{H^{#1}_{#2}}%half-plane
\newcommand{\sepline}[2]{L^{#1}_{#2}}%separating line
\newcommand{\hpi}[2]{M^{#1}_{#2}}%separating line
\newcommand{\myerr}[1]{Err(#1)}

\renewcommand{\arraystretch}{2}


\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\avg}{\mathbb E}
\DeclareMathOperator*{\E}{\mathbb E}
\DeclareMathOperator*{\Var}{\mathrm Var}
%\DeclareMathOperator{\vs}{vs}

\newcommand{\mydelta}{\epsilon} %% to replace distance approximation parameter
\newcommand{\bigdelta}{{\epsilon_0}} %% to replace distance approximation parameter
\newcommand{\dsquares}{d_{\rm squares}}
\newcommand{\dhatsquares}{\hat{d}_{\rm squares}}
\newcommand{\dout}{\hat{d}}

%To ensure qed squares at the end of proofs.
\newenvironment{myproof}{\begin{proof}%\small
}{
\end{proof}}
\newenvironment{proofof}[1]{\begin{myproof}[\ifnum\llncs=0 Proof \fi of {#1}]%\small
}{\end{myproof}}


\ifnum\withcomments=1
   \newcommand{\mnote}[1]{{\color{red}\footnote{{\color{red} {\bf M:} #1}}}}
   \newcommand{\pnote}[1]{{\color{green}\footnote{{\color{green} {\bf P:} #1}}}}
   \newcommand{\snote}[1]{{\color{black}\footnote{{\color{black} {\bf S:} #1}}}}
\else
   \newcommand{\mnote}[1]{}
   \newcommand{\pnote}[1]{}
   \newcommand{\snote}[1]{}
\fi

\newcommand{\mch}[1]{{\color{black}#1}}

\date{}
\ifnum\full=1
\title{Tolerant Testers of Image Properties\footnote{A preliminary version of this article was published in the proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP, 2016~\cite{BMR16icalp}}}
\else
\title{Tolerant Testers of Image Properties}
%\title{uniform Constant-Time Algorithms for Properties of Images}
\fi
\author{Piotr Berman\thanks{Pennsylvania State University, USA; {\tt berman@cse.psu.edu}.}\\
\and Meiram Murzabulatov\thanks{Pennsylvania State University, USA; {\tt meyram85@yahoo.co.uk}. This author was supported by NSF CAREER award CCF-0845701 and NSF award CCF-1422975.
}\\
\and Sofya Raskhodnikova\thanks{Pennsylvania State University, USA; {\tt sofya@cse.psu.edu}. This author was supported by NSF CAREER award CCF-0845701, NSF award CCF-1422975, and by Boston University's Hariri Institute for Computing and Center for Reliable Information Systems and Cyber Security and, while visiting the Harvard Center for Research on Computation \& Society, by a Simons Investigator grant to Salil Vadhan.
%"Boston University's Hariri Institute and Center for RISCS."
}
}
\begin{document}
\raggedbottom
\setlength{\parskip}{0pt}
\maketitle
\begin{abstract}
We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property (that is, the smallest fraction of pixels that need to change in the image to ensure that the image satisfies the desired property). Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise. Prior to this work, only one tolerant testing algorithm for an image property (image partitioning) has been published.

We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so that it becomes a half-plane? a representation of a convex object? a representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error $\eps$, after reading a number of pixels polynomial in $1/\eps$ and independent of the size of the image. The running time of the testers for half-plane and convexity is also polynomial in $1/\eps$.
Tolerant testers for these three properties were not investigated previously. For convexity and connectedness, even the existence of distance approximation algorithms with query complexity independent of the input size is not implied by previous work. (It does not follow from the VC-dimension bounds, since VC dimension of convexity and connectedness, even in two dimensions, depends on the input size. It also does not follow from the existence of non-tolerant testers.)

Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons  $P_\mydelta$ such that (1) every convex image has a nearby polygon in $P_\mydelta$ and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in $P_\mydelta$. This construction might be of independent interest.

%We design algorithms that approximate the distance to the three properties within a small additive error that have access only to labeled random samples from the input. Most previous sublinear-time algorithms for image analysis were {\em query-based}, that is, they could query pixels of their choice. We consider algorithms with two types of input access: {\em uniform} algorithms that draw independent uniformly random pixels, and {\em block-uniform} algorithms that draw pixels from independently random square blocks of the image.  For the first two, our algorithms are uniform; for connectedness, they are block-uniform. All our algorithms have low sample complexity that depends polynomially on the inverse of the error parameter and is independent of the input size.
%
% or, equivalently, tolerant testers for being a half-plane, convexity and connectedness. Tolerant testers for these properties, even with query access to the image, were not investigated previously. Tolerance is important in image processing applications because it allows algorithms to be resilient to noise in the image. We also give (non-tolerant) testers for convexity and connectedness with better complexity than our distance approximation algorithms and previously known query-based testers.
%
%To obtain our algorithms for convexity, we design two fast proper PAC learners of convex sets in two dimensions that work under the uniform distribution: non-agnostic and agnostic.
%
%
%%Specifically, we have (omitting for readability big-O and dependence on delta):
%
%%-- an agnostic proper PAC learner under the  uniform distribution with sample complexity 1/\eps^2 log 1/\eps and time complexity poly(1/\eps);
%
%%-- a proper PAC learner under the uniform distribution with sample and time complexity 1/\eps^(3/2).
\end{abstract}
%\ifnum\full=0
%\thispagestyle{empty}
%\setcounter{page}{0}
%\fi
\section{Introduction}\label{sec:intro}
Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. Images are huge objects, and our visual system manages to process them very quickly without examining every part of the image. Moreover, many applications in image analysis have to process a large number of images online, looking for an image that satisfies a certain property among images that are generally very far from satisfying it. Or, alternatively, they look for a subimage satisfying a certain property in a large image (e.g., a face in an image where most regions are part of the background.) There is a growing number of proposed {\em rejection-based} algorithms that employ a quick test that is likely to reject a large number of unsuitable images (see, e.g., citations in \cite{KleinerKNB11}).

Property testing~\cite{RS96,GGR98} is a formal study of fast algorithms that accept objects with a given property and reject objects that are far. Testing image properties in this framework was first considered in \cite{Ras03}. Ron and Tsur~\cite{TsurR10} initiated property testing of images with a different input representation, suitable for testing properties of sparse images. Since these models were proposed, several sublinear-time algorithms for visual properties were implemented and used: namely, those by Kleiner et al.\ and Korman et al.\ \cite{KleinerKNB11,KormanRT,KormanRTA13}.

However, for sublinear-time algorithms to reach their full potential in image processing, they have to be resilient to noise: images are often noisy, and it is undesirable to reject images that differ only on a small fraction of pixels from an image satisfying the desired property. Tolerant testing was introduced by Parnas, Ron and Rubinfeld~\cite{PRR06}  exactly with this goal in mind---to deal with noisy objects. It builds on the property testing model and calls for algorithms that accept objects that are close to having a desired property and reject objects that are far. Another related task is approximating distance of a given object to a nearest object with the property within additive error~$\mydelta$. (Distance approximation algorithms imply tolerant testers in a straightforward
\ifnum\full=1
way: see the remark after Definition~\ref{def:distance-approx-alg}).
\else
way.)
\fi
The only image problem for which tolerant testers were studied is the image partitioning problem investigated by Kleiner et al.~\cite{KleinerKNB11}.
\subparagraph{Our results.}
We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so that it becomes a half-plane? a representation of a convex object? a representation of a connected object?
In other words, we design algorithms that approximate the distance to being a half-plane, convexity and connectedness within a small additive error or, equivalently, tolerant testers for these properties. These problems were not investigated previously in the tolerant testing framework.
For all three properties, we give $\mydelta$-additive distance approximation algorithms that run in constant time (i.e., dependent only on $\mydelta$, but not the size of the image). We remark that even though it was known that these properties can be tested in constant time \cite{Ras03}, this fact does not necessarily imply constant-query tolerant testers for these properties. E.g., Fischer and Fortnow~\cite{FischerF06} exhibit a property (of objects representable with strings of length $n$) which is testable with a constant number of queries, but for which every tolerant tester requires $n^{\Omega(1)}$ queries.
For convexity and connectedness, even the existence of distance approximation algorithms with query (or time) complexity independent of the input size does not follow from previous work. It does not follow from the VC-dimension bounds, since VC dimension of convexity and connectedness, even in two dimensions, depends on the input size\footnote{For $n\times n$ images, the VC dimension of convexity is $\Theta(n^{2/3})$ (this is the maximum number of vertices of a convex lattice polygon in an $n\times n$ lattice \cite{Barany00}); for connectedness, it is $\Theta(n)$.}. Implications of the VC dimension bound on convexity are further discussed below.

Our results on distance approximation are summarized  in Table~\ref{table:all-results}. Our algorithm for convexity is the most important and technically difficult of our results, requiring a large number of new ideas to get running time polynomial in $1/\eps.$ To achieve this, we define a set of reference polygons  $P_\mydelta$ such that (1) every convex image has a nearby polygon in $P_\mydelta$ and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in $P_\mydelta$. It turns out that the empirical error of our algorithm is proportional to the sum of the square roots of the areas of the regions it considers in the dynamic program. To guarantee (2) and keep our empirical error small, our construction ensures that the sum of the square roots of the areas of the considered regions is small.
This construction might be of independent interest.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Joint results table
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table*}[t]
\begin{center}
\begin{tabular}{| l || c | c| c |}
\hline
\multicolumn{1}{|c||}{Property}& Sample Complexity &  Run Time & Access to Input
\\
\hline
Half-plane  &  $O\left(\frac 1 {\mydelta^2} \log \frac 1 \mydelta\right)$ & $O\left(\frac 1 {\mydelta^3} \log \frac 1 \mydelta\right)$ & uniformly random pixels
\\
Convexity &  $O\left(\frac 1 {\mydelta^2} \log \frac 1 \mydelta\right)$ & $O\left(\frac 1 {\mydelta^8} \right)$ & uniformly random pixels
\\
Connectedness &  $O\left(\frac 1 {\mydelta^4} \right)$ \ \ \ \ & $\exp\left(O\left(\frac 1 \mydelta \right)\right)$ &uniformly random blocks of pixels
\\
\hline
\end{tabular}
\end{center}
\caption{Our results on distance approximation.
%(s.b./ b.s.b. = uniform/block-uniform).
To get complexity of $(\eps_1,\eps_2)$-tolerant testing, substitute $\mydelta=(\eps_2-\eps_1)/2$.
}
\label{table:all-results}
\end{table*}
Our algorithms do not need sophisticated access to the input image: uniformly randomly sampled pixels suffice for our algorithms for the half-plane property and convexity. For connectedness, we allow our algorithms to query pixels from a uniformly random block. (See the end of Section~\ref{sec:defintions_notation} for a formal specification of the input access.)
%

Our algorithms for convexity and half-plane work by first implicitly learning the object\footnote{\label{fn:connection-to-learning}There is a known implication from learning to testing. As proved in \cite{GGR98}, a proper PAC learning algorithm for property ${\cal P}$
with sampling complexity $q(\eps)$ implies a 2-sided error (uniform) property tester for $\cal{P}$ that takes $q(\eps/2) + O(1/\eps)$ samples. There is an analogous implication from proper agnostic PAC learning to distance approximation with an overhead of $O(1/\eps^2)$ instead of $O(1/\eps)$. We choose to present our testers first and get learners as corollary because our focus is on testing and because we want additional features for our testers, such as 1-sided error, that do not automatically follow from the generic relationship.}.
\ifnum\full=1
PAC learning was defined by Valiant~\cite{Valiant84}, and agnostic learning, by Kearns et al.~\cite{KearnsSS94} and Haussler~\cite{Haussler92}.
\fi
 As a corollary of our analysis, we obtain fast proper agnostic PAC learners of half-planes and of convex sets in two dimensions that work under the uniform distribution.
 %For convex sets, we get two PAC learners: non-agnostic and agnostic. For half-planes, we get an agnostic PAC learner.
 The sample and time complexity\footnote{All our results are stated for error probability $\delta=1/3$. To get results for general $\delta$, by standard arguments, it is enough to multiply the complexity of an algorithm by $\log 1/\delta$.} of % agnostic
 the PAC learners is as indicated in Table~\ref{table:all-results} for distance approximation algorithms for corresponding properties.
 %; the complexity of non-agnostic PAC learner for convex sets in two dimensions corresponds to that of the property tester for convexity.
% beat VC-dimension lower bounds
% sampling complexity, but not the running time follow for half-plane


While the sample complexity of our agnostic half-plane learner (and hence our distance approximation algorithm for half-planes) follows from the VC dimension bounds, its running time does not. Agnostically learning half-spaces under the uniform distribution has been studied by \cite{KalaiKMS08}, but only for the hypercube $\{-1,1\}^d$ domains, not the plane.
%
Our PAC learner of convex sets, in contrast to our half-plane learner, \ dimension lower bounds on sample complexity. (The sample complexity of a PAC learner for a class
is at least proportional to the VC dimension of that class \cite{EHKV89}.) Since VC dimension of convexity of $n\times n$ images is
$\Theta(n^{2/3})$,
%http://www.renyi.hu/~barany/cikkek/psurveyAMS.pdf
%and VC dimension of connectedness is $\Theta(n^2)$,
proper PAC learners of convex sets in two dimensions (that work under arbitrary distributions) must have sample complexity $\Omega(n^{2/3})$. However, one can do much better with respect to the uniform distribution.
Schmeltz~\cite{Sch92} showed that a non-agnostic learner for that task needs
$\Theta(\mydelta^{-3/2})$ samples.
%We improve the sample complexity and the running time to $O(\mydelta^{-3/2})$.
Surprisingly, it appears that this question has not been studied at all for agnostic learners. Our agnostic learner for convex sets in
\ifnum\full=1
two dimensions
\else
2D
\fi
under the uniform distribution needs
$O\left(\frac 1 {\mydelta^2} \log \frac 1 \mydelta\right)$ samples and runs in time $O\left(\frac 1 {\mydelta^8} \right)$.

Finally, we note that for connectedness, we take a different approach. Our algorithms do not try to learn the object first; instead they rely on a combinatorial characterization of distance to connectedness. We show that distance to connectedness can be represented as an average of distances of sub-images to a related property.
\subparagraph{Comparison to other related work.}
Property testing has rich literature on graphs and functions, however, properties of images have been investigated very little. Even though superficially the inputs to various types of testing tasks might look similar, the problems that arise are different.
%
In the line of work on testing dense graphs, started by Goldreich et al.~\cite{GGR98}, the input is also an $n\times n$ binary matrix, but it represents an adjacency matrix of the dense input graph. So, the problems considered are different than in this work.
%
In the line of work on testing geometric properties, started by Czumaj, Sohler, and Ziegler~\cite{CzumajSZ00} and Czumaj and Sohler~\cite{CS01}, the input is a set of points represented by their coordinates. The allowed queries and the distance measure on the input space are different from ours. %For example, coordinates of points in 2D are given and one has to determine if they are in convex position or far from having that property.


A line of work potentially relevant for understanding connectedness of images is on connectedness of bounded-degree graphs. Goldreich and Ron~\cite{GR02}  gave a tester for this property, subsequently improved by Berman et al.~\cite{BermanRY14}. Campagna et al.~\cite{CampagnaGR13} gave a tolerant tester for this problem. Even though we view our image as a graph in order to define connectedness of images, there is a significant difference in how distances between instances are measured (see~\cite{Ras03} for details). We also note, that unlike in~\cite{CampagnaGR13}, our tolerant tester for connectedness is fully tolerant, i.e., it works for all settings of parameters.


The only previously known tolerant tester for image properties was given by Kleiner et al.~\cite{KleinerKNB11}. They consider the following class of image partitioning problems, each specified by a $k\times k$ binary template matrix $T$ for a small {\em constant} $k$. The image satisfies the property corresponding to $T$ if it can be partitioned by $k-1$ horizontal and $k-1$ vertical lines into blocks, where each block has the same color as the corresponding entry of $T$. Kleiner et al.\ prove that $O(1/\mydelta^2)$ samples suffice for tolerant testing of image partitioning properties. Note that VC dimension of such a property is $O(1)$, so by Footnote~\ref{fn:connection-to-learning}, we can get a $O(1/\mydelta^2\log 1/\mydelta)$ bound. Our algorithms required numerous new ideas to significantly beat VC dimension bounds (for convexity and connectedness) and to get low running time.

For the properties we study, distance approximation algorithms and tolerant testers were not investigated previously. In the standard property testing model, the half-plane property can be tested in $O(\eps^{-1})$ time~\cite{Ras03}, convexity can be tested in $O(\eps^{-4/3})$ time~\cite{BMR16socg}, and connectedness can be tested in $O(\eps^{-2}\log \eps^{-1})$ time~\cite{Ras03,BermanRY14}. As we explained, property testers with running time independent of $\eps$ do not necessarily imply tolerant testers with that feature.
%The techniques in the current work are completely different from those employed in the aforementioned standard property testers.
Many new ideas are needed to obtain our tolerant testers. In particular, the standard testers for half-plane and connectedness are adaptive while the testers here need only random samples from the image, so the techniques used for analyzing them are different. The tester for convexity in~\cite{BMR16socg} uses only random samples, but it is not based on dynamic programming.


%Korman et al.~\cite{KormanRT,KormanRTA13} give a sublinear-time approximation algorithm for the image matching problem. In this problem, given two $n\times n$ grayscale images, $M_1$ and $M_2$, the goal is to find a certain affine transformation of pixels of $M_1$ that results in an image that as close as possible to $M_2$ in $L_1$-distance.
%Berman et al.~\cite{BermanRY14} improved connectedness tester.

%Learning Convex Sets Under Uniform Distribution
%\subparagraph{Open problems.} We mention two open problems.
\subparagraph{Open questions.}
In this paper we give tolerant testers for several important problems on images.
It is open whether these testers are optimal. No nontrivial lower bounds are known for these problems. (For any non-trivial property, an easy lower bound on the query complexity of a distance approximation algorithm is $\Omega(1/\eps^2)$. This follows from the fact that $\Omega(1/\eps^2)$ coin flips are needed to distinguish between a fair coin and a coin that lands heads with probability $1/2+\eps$.) Thus, our testers for half-plane and convexity are nearly optimal in terms of query complexity (up to a logorithmic factor in $1/\eps$). But it is open whether their running time can be improved.
%It is also open whether ability to ask arbitrary queries and adaptivity help in testing these properties. Our (block-)uniform algorithms achieve the best known query complexity, even for adaptive algorithms. The exception is the half-plane property. The best known  (non-tolerant) testing algorithm for it~\cite{Ras03} is adaptive and has optimal query complexity of $O(\frac 1 {\eps}),$ while the best known uniform tester for this property has complexity $O(\frac{1}{\eps}\log \frac 1\eps)$\ifnum\full=1
%(see Footnote~\ref{fn:halfplane}).
%\else.
%\fi

\ifnum\full=1
\subparagraph{Organization.} We give formal definitions and notation in Section~\ref{sec:defintions_notation}. Algorithms for being a half-plane, convexity, and connectedness are given in Sections~\ref{sec:half-plane},~\ref{sec:convexity}, and~\ref{sec:connectedness}, respectively. The sections presenting algorithms for being a half-plane and convexity start by giving a distance approximation algorithm and conclude with the corollary about the corresponding PAC learner.
\else
\subparagraph{Organization.} We give formal definitions and notation in Section~\ref{sec:defintions_notation}, deferring some standard definitions to the {\color{black} full version}. Algorithms for being a half-plane, convexity, and connectedness are given in Sections~\ref{sec:half-plane},~\ref{sec:convexity}, and~\ref{sec:connectedness}, respectively.  We view our half-plane result as a good preparation for our distance approximation algorithm for convexity, the most technically difficult result in the paper. Corollaries about PAC learners as well as all omitted proofs and numerous figures can be found in the {\color{black} full version}.
\fi

\section{Definitions and Notation}\label{sec:defintions_notation}
We use $\integerset{n}$ to denote the set of integers $\{0,1,\ldots,n-1\}$ and $[n]$ to denote $\{1,2,\ldots,n\}$.
\ifnum\full=1
%\snote{See if we really need both $\integerset{n}$ and $[n]$.}
By $\log$ we mean the logarithm base 2, and by $\ln$, the logarithm base $e$.
\fi

\subparagraph{Image representation.}
We focus on black and white images. For simplicity, we only consider square images, but everything in this paper can be easily generalized to rectangular images.
We represent an image by an $n\times n$ binary matrix $M$ of pixel values, where 0 denotes white and 1 denotes black.
We index the matrix by $\integerset{n}^2$. The object is a subset of $\integerset{n}^2$
corresponding to black pixels; namely, $\{(i,j)\mid M[i,j]=1\}$.
\ifnum\full=1
The {\em left border of the image} is the set $\{(0,j)\mid j\in\integerset{n}\}$. The right, top and bottom borders are defined analogously. The image {\em border} is the set of pixels on all four borders.

For any region $R$, we use $A(R)$ to denote its area.
\fi

\ifnum\full=0
The {\em absolute distance}, $\Dis(M_1,M_2)$, between matrices $M_1$ and $M_2$ is the number of the entries on which they differ. The \emph{relative distance} between them is $\dis(M_{1},M_{2})=\Dis(M_{1},M_{2})/ n^{2}$.
A property $\mathcal{P}$ is a subset of binary matrices.
\else
\subparagraph{Distance to a property.} The {\em absolute distance}, $\Dis(M_1,M_2)$, between matrices $M_1$ and $M_2$ is the number of the entries on which they differ. The \emph{relative distance} between them is $\dis(M_{1},M_{2})=\Dis(M_{1},M_{2})/ n^{2}$.
A property $\mathcal{P}$ is a subset of binary matrices. The distance of an image represented by matrix $M$ to a property $\mathcal{P}$ is $\dis(M,\mathcal{P})=\min_{M'\in \mathcal{P}}$ $\dis(M,M')$. An image is {\em $\epsilon$-far} from the property if its distance to the property is at least $\epsilon$; otherwise, it is $\eps$-close to it.

\subparagraph{Computational Tasks.}
We consider several computational tasks: tolerant testing~\cite{PRR06}, additive approximation of the distance to the property, and proper (agnostic) PAC learning~\cite{Valiant84,KearnsSS94,Haussler92}.
\ifnum\full=1
Here we define them specifically for properties of images.
\fi
\begin{definition}[Tolerant tester]\label{def:tester}
 An {\em $(\eps_1,\eps_2)$-tolerant tester} for a property $\cP$ is a randomized algorithm that, given two parameters $\eps_1,\eps_2\in(0,1/2)$ such that $\eps_1<\eps_2$ and access to an $n\times n$ binary matrix $M$,
\ifnum\full=0
(1) accepts with probability at least 2/3 if $\dis(M,\cP)\leq\eps_1$;
(2) rejects with probability at least 2/3 if $\dis(M,\cP)\geq\eps_2$.
\else
\begin{enumerate}
\item accepts with probability at least 2/3 if $\dis(M,\cP)\leq\eps_1$;
\item rejects with probability at least 2/3 if $\dis(M,\cP)\geq\eps_2$.
\end{enumerate}
\fi

\end{definition}

%\begin{definition}[Tolerant tester]\label{def:tolerant-tester}
% An {\em $(\eps_1,\eps_2)$-tolerant tester} for a property $\cP$ is a randomized algorithm that, given two proximity parameters $0\leq \eps_1<\eps_2<1/2$ and access to an $n\times n$ matrix $M$ of binary values,
%\begin{enumerate}
%\item accepts with probability at least 2/3 if $\dis(M,\cP)\geq\eps_1$;
%\item rejects with probability at least 2/3 if $\dis(M,\cP)\geq\eps_2$.
%\end{enumerate}
%\end{definition}

\begin{definition}[Distance approximation algorithm]\label{def:distance-approx-alg}
An {\em $\mydelta$-additive distance approximation algorithm} for a property $\cP$ is a randomized algorithm that, given an error parameter $\mydelta\in(0,1/4)$ and access to an $n\times n$ binary matrix $M,$ outputs a value $\dout\in[0,1/2]$ that with probability at least 2/3 satisfies $|\dout -\dis(M,\cP)|\leq \mydelta$.
\end{definition}

As observed in \cite{PRR06}, we can obtain an $(\eps_1,\eps_2)$-tolerant tester for any property $\cP$ by running a distance approximation algorithm for $\cP$ with $\mydelta=(\eps_2-\eps_1)/2$. Thus, all our distance approximation algorithms directly imply tolerant testers.

\begin{definition}[Proper agnostic PAC learner]

A proper agnostic PAC learning algorithm for class $\cal P$ that works under the uniform distribution is given a parameter $\eps\in(0,1/2)$ and access to an image $M$. It can draw independent uniformly random samples $(i,j)$  and obtain $(i,j)$ and $M[i,j]$. With probability at least 2/3, it must output an image $M'\in {\cal P}$ such that $\dis(M,M')\leq\dis(M,{\cal P})+\eps$.
%given a parameter $\mydelta\in(0,1/4)$ and access to an image $M$. It can draw independent uniformly random samples $(i,j)$ and obtain $(i,j)$ and $M[i,j]$. With probability at least 2/3, it must output an image $M'\in {\cal P}$ such that $\dis(M,M')\leq\dis(M,{\cal P})+\eps$.
\end{definition}
\fi
\subparagraph{Access to the input.}
A {\em query-based} algorithm accesses its $n\times n$ input matrix $M$ by specifying a query pixel $(i,j)$ and obtaining $M[i,j]$.
\ifnum\full=1
The query complexity of the algorithm is the number of pixels it queries.
A {\em query-based} algorithm is {\em adaptive} if its queries depend on answers to previous queries and {\em nonadaptive} otherwise.
\fi
A {\em uniform} algorithm accesses its $n\times n$ input matrix by drawing independent samples $(i,j)$ from the uniform distribution over the domain (i.e., $\integerset{n}^2$) and obtaining $M[i,j]$.
%
A {\em block-uniform algorithm} accesses its $n\times n$ input matrix by specifying a block length $\side\in[n]$. For a block length $\side$ of its choice, the algorithm draws $x,y\in[\lceil n/\side\rceil]$ uniformly at random and obtains set $\{(i,j)\mid \lfloor i/\side\rfloor=x\text{ and } \lfloor j/\side\rfloor=y\}$ and $M[i,j]$ for all $(i,j)$ in this set.
The sample complexity of a {\em uniform} or a {\em block-uniform} algorithm is the number of pixels of the image it examines.

\begin{remark}\label{remark:bernoulli}
Uniform algorithms have access to independent (labeled) samples from the uniform distribution over the domain.
\ifnum\full=1
Sometimes it is more convenient to design
{\em Bernoulli algorithms} that
\else
{\em Bernoulli algorithms}
\fi
only have access to (labeled) Bernoulli samples from the %domain: namely, each domain point appears in the sample with probability $s/|\D|$, where $s$ is the sample parameter that controls the expected sample complexity and $\D$ is the domain.
image: namely, each pixel appears in the sample with probability $s/n^2$, where $s$ is the sample parameter that controls the expected sample complexity.
%
By standard arguments, a Bernoulli algorithm with the sample parameter $s$ can be used to obtain a uniform algorithm that takes $O(s)$ samples and has the same guarantees as the original algorithm (and vice versa).
\end{remark}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  Half-plane section
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Distance Approximation to the Nearest Half-Plane Image}\label{sec:half-plane}
{\color{black} 
%An image {\color{black}represented by matrix $M$ is a \emph{half-plane image}} if there exist an angle $\varphi\in[0,2\pi)$ and a real number $c$ such that $M[x,y]=1$ (i.e., pixel $(x,y)$ is black) iff $x\cos\varphi +y\sin\varphi \geq c$. In other words, an image is a half-plane image if there is a line, called a {\em separating line}, that separates black and white pixels of the image.For all $\varphi$ and $c$, let $\hp{\varphi}{c}$ denote the half-plane that satisfies the above inequality with parameters $\varphi$ and $c$, and let $\sepline{\varphi}{c}$ be the segment of the separating line that belongs to the image. We call $\varphi$ the {\em direction} of $\hp{\varphi}{c}$ (and $\sepline{\varphi}{c}$). Note that $\varphi$ is the oriented angle between the $x$-axis and a line perpendicular to $\sepline{\varphi}{c}$.
{\color{black} An image is called a \emph{half-plane image}} if there exist an angle $\varphi\in[0,2\pi)$ and a real number $c$ such that pixel $(x,y)$ is black in the image iff $x\cos\varphi +y\sin\varphi\geq c$. The line $x\cos\varphi +y\sin\varphi= c$, denoted $\sepline{\varphi}{c}$, is {\em a separating line} of the half-plane image, i.e., it
separates black and white pixels of the image. We call $\varphi$ the {\em direction} of the half-plane image (and $\sepline{\varphi}{c}$). Note that $\varphi$ is the oriented angle between the $x$-axis and a line perpendicular to $\sepline{\varphi}{c}$. For all $\varphi\in[0,2\pi)$ and $c\in\mathbb R$, the half-plane image with a separating line $\sepline{\varphi}{c}$ is denoted $\hpi{\varphi}{c}$ and the closed half-plane whose every point $(x,y)$ satisfies the inequality $x\cos\varphi +y\sin\varphi \geq c$ is denoted $\hp{\varphi}{c}$. We can think of a half-plane image as a discretized half-plane.
 
}
\begin{theorem}\label{thm:half-plane-dist-appr}
For $\eps\in(\frac{90}n,\frac 1 4)$, there is a uniform $\mydelta$-additive distance approximation algorithm for the half-plane property with sample complexity  $O(\frac{1}{\mydelta^2}\log\frac{1}{\mydelta})$ and time complexity $O(\frac{1}{\mydelta^{3}}\log \frac{1}{\mydelta}).$
\end{theorem}

\begin{proof}
{\color{black}At a high level, our algorithm for approximating the distance to being a half-plane (Algorithm~\ref{alg:half-plane}) constructs a small set $\mathcal M_\mydelta$ of reference half-plane images. It samples pixels uniformly at random and outputs the empirical distance to the closest reference half-plane image. The core property of $\mathcal M_\mydelta$ is that the smallest empirical distance to a half-plane image in $\mathcal M_\mydelta$ can be computed quickly.

\begin{definition}[Reference directions and half-planes]\label{def:reference-half-planes}
Given $\mydelta\in(0,\frac{1}{4})$, let $a=\mydelta n/\sqrt{2}$. Let $D_\mydelta$ be the set of directions of the form $i\mydelta$ for  $i\in\integerset{\lceil 2\pi/\mydelta\rceil},$ called {\em reference directions}. The set of {\em reference half-plane images}, denoted $\mathcal M_\mydelta$, consists of every half-plane image for which $\sepline{\varphi}{c}$ is a separating line, where $\varphi\in D_\mydelta$ and $c$ is an integer multiple of $a$. %Reference lines are separating line for half-planes in $M_\mydelta$.
\end{definition}
In other words, for every reference direction, we space separating lines of reference half-plane images distance $a$ apart. By definition, there are at most $\sqrt 2 n/a = 2/\mydelta$ reference half-plane images for each direction in $D_\mydelta$ and, consequently, $|\mathcal M_\mydelta|\leq 2 \pi/\mydelta \cdot(2/\mydelta) < 13/\mydelta^2$.

\begin{algorithm}
\caption{Distance approximation to being a half-plane.}
\label{alg:half-plane}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameters $n\in\mathbb{N}$, $\mydelta\in(90/n,1/4)$; Bernoulli access to an $n\times n$ binary matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl Sample a set $S$ of $s=\frac{6}{\mydelta^{2}}\ln\frac{7}{\mydelta}$ pixels uniformly at random with replacement.\;
\nl Let $D_\mydelta, \mathcal M_\mydelta$ be the sets of reference directions and half-planes, respectively (see Definition~\ref{def:reference-half-planes}) and $a=\eps n/\sqrt{2}$.\;
%\nl For two matrices $M_1$ and $M_2$, let $\dout(M_1,M_2)$ be the fraction of points in $S$ on which $M_1$ and $M_2$ differ.\;
\tcp{Compute $\displaystyle\dout=\min_{M'\in \mathcal M_\mydelta}\dout(M')$,
where $\dout(M')=\frac 1 s \cdot |\{p\in S : M[p]\neq M'[p]\}|$:}
\nl\label{step:half-planes-foreach-dir} \ForEach {$\varphi\in D_\mydelta$}\do{\tcp{Lines with direction $\varphi$ partition the image. Bucket sort samples by position in the partition:}
\nl\quad     Assign each sample $(x,y)\in S$ to bucket $j=\lfloor(x\cos\varphi+y\sin\varphi)/a\rfloor$.\;
\nl\quad     For each bucket $j$, compute $w_j$ and $b_j$, the number of white and black pixels it has.\;
\nl\label{step:half-planes-compute-estimate}\quad     For each $j$, where $\hpi{\varphi}{ja}\in \mathcal M_\mydelta$, compute
$\dout(\hpi{\varphi}{ja})=
\frac{1}{s}\sum_{k < j}b_k+\
\frac{1}{s}\sum_{k\ge j}w_k$.\;
}
\nl Output $\dout$, the minimum of the values computed in Step~\ref{step:half-planes-compute-estimate}.\;
\end{algorithm}


\begin{lemma}\label{lem:properties-of-reference-HP}
 For every half-plane image $M$, there is $M'\in \mathcal M_\mydelta$ such that $\dis(M,M')\leq\mydelta/1.8$.
\end{lemma}

%\begin{claim}\label{cl:properties-of-reference-HP}
%For every half-plane image $M$, there is $M'\in M_\mydelta$ such that the area of the symmetric difference of $M$ and $M'$ is at most $\mydelta n^2/2$.
%\end{claim}
\begin{proof}
We mentioned that a half-plane image can be viewed as a discretized half-plane. Next we define a set of half-planes that we use in the proof of the lemma.
\begin{definition}\label{def:hp}
The set of reference half-planes, denoted $\mathcal H_{\mydelta}$, consists of every half-plane $\hp{\varphi}{c}$, where $\varphi\in D_\mydelta$ and $c$ is an integer multiple of $a$. 
\end{definition}
\begin{claim}\label{cl:properties-of-reference-HP}
For every half-plane $H$, there is a half-plane $H'\in\mathcal{H_{\eps}}$ such that the area of the symmetric difference of $H$ and $H'$ is at most $\mydelta n^2/2$.
\end{claim}
\begin{proof}
Consider a half-plane $\hp{\varphi}{c}$. Let $\varphi'$ be a reference direction closest to $\varphi$. Then $|\varphi-\varphi'|\le\mydelta/2$. 
We consider two cases. 
\ifnum\full=1
See Figures~\ref{fig:nearby-ref-halfplane} and~\ref{fig:nearby-ref-halfplane2}.

\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-Ref-halfplane.pdf}
\caption{Proof of Lemma~\ref{lem:properties-of-reference-HP}: triangular regions.}
\label{fig:nearby-ref-halfplane}
\end{minipage}
\hspace{0.1\linewidth}
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-Ref-halfplane2.pdf}
\caption{Proof of Lemma~\ref{lem:properties-of-reference-HP}: triangular and quadrilateral regions.}
\label{fig:nearby-ref-halfplane2}
\end{minipage}
\end{figure}

\else
See the figures in the {\color{black} full version}.
\fi

{\bf Case 1:} Suppose that there is a reference half-plane $\hp{\varphi'}{c'}$ such that the lines $\sepline{\varphi}{c}$ and $\sepline{\varphi'}{c'}$ intersect inside inside $[0,n-1]^2$. Note that the length of every line segment inside $[0,n-1]^2$ is at most $\sqrt{2}n$. The symmetric difference of $\hp{\varphi}{c}$ and $\hp{\varphi'}{c'}$ inside $[0,n-1]^2$ consists of two regions
formed by lines $\sepline{\varphi}{c}$ and $\sepline{\varphi'}{c'}$. Each of these regions is either a triangle or (if it contains a corner of the image) a quadrilateral. First, suppose both regions are triangles. The sum of lengths of their bases, that lie on the same line, is at most $\sqrt{2}n$, whereas the sum of their heights is at most $\sin (\mydelta/2)\times\sqrt{2}n\leq \mydelta n/\sqrt{2}$. Hence, the sum of their areas is at most $\mydelta n^2/2$.

If exactly one of the regions is a quadrilateral, we add a line through the corner of the image contained in the quadrilateral and the intersection point of  $\sepline{\varphi}{c}$ and $\sepline{\varphi'}{c'}$. It partitions the symmetric difference of $\hp{\varphi}{c}$ and $\hp{\varphi'}{c'}$ into two pairs of triangular regions. Let $\varphi_1$ (respectively, $\varphi_2$) be the angle between the new line and $\sepline{\varphi}{c}$ (respectively, $\sepline{\varphi'}{c'}$). Then $\varphi_1+\varphi_2\leq\mydelta/2$. Applying the same reasoning as before to each pair of regions, we get that the sum of their areas is at most $\varphi_1 n^2+\varphi_2 n^2\leq \mydelta n^2/2$.
%
If both regions are quadrilaterals, we add a line as before for each of them and apply the same reasoning as before to the three resulting pairs of regions. Again, the area of the symmetric difference of $\hp{\varphi}{c}$ and $\hp{\varphi'}{c'}$ is at most $\mydelta n^2/2$. Thus, $\hp{\varphi'}{c'}$ is the required $M'$.

{\bf Case 2:} There exist reference half-planes $\hp{\varphi'}{c'}$ and $\hp{\varphi'}{c'+a}$ such that the line 
$\sepline{\varphi}{c}$ is between $L=\sepline{\varphi'}{c'}$ and $L'=\sepline{\varphi'}{c'+a}$. The region between $L$ and $L'$ inside the image has
length at most $\sqrt{2}n$ and width $a$. Thus, its area is at
most $\mydelta n^2$. Partition it into two regions: between $L$ and
$\sepline{\varphi}{c}$ and between $L'$ and $\sepline{\varphi}{c}$. One of the two regions has area at most
$\mydelta n^2/2$. Thus, $\hp{\varphi'}{c'}$ or $\hp{\varphi'}{c'+a}$ is the required $M'$.
\end{proof}

To complete the proof of the lemma we use the following theorem that relates the area of a lattice polygon and the number of integer points that the polygon covers. (A lattice polygon is a polygon whose vertices have integer coordinates.)
\begin{theorem}[Pick's theorem~\cite{pick}]\label{thm:pick}
For a simple lattice polygon $G$, let $\alpha$ denote the number of lattice points in the interior of $G$ and $\beta$ denote the number of lattice points on the boundary of $G$. Then $A(G)=\alpha+\beta/2-1$.
\end{theorem}

\begin{definition}
For a polygon $G$, let $Perim(G)$ denote the perimeter of $G$ and $Pix(G)$ denote the number of pixels in $G$, i.e., pixels in the interior of $G$ and on its boundary.
\end{definition}
\begin{proposition}\label{prop:area-pixel}
Let $G$ be a convex polygon. Then $Pix(G)\leq A(G)+Perim(G)/2+1$.
\end{proposition}
\begin{proof}
If all pixels in $G$ are collinear then $Pix(G)\leq Perim(G)/2+1\leq A(G)+Perim(G)/2+1$. This follows from the fact that the length of a line segment inside a polygon is at most half of the perimeter of the polygon and that the number of integer points on the line segment is at most the length of the line segment plus one. If not all pixels in $G$ are collinear then consider the convex hull of all pixels in $G$. Let $\alpha$ and $\beta$ denote the number of pixels in the interior and on the boundary of that convex hull, respectively. (Note that the convex hull is a lattice polygon). By Theorem~\ref{thm:pick}, we obtain that $\alpha+\beta/2-1\leq A(G)$ and $Pix(G)=\alpha+\beta\leq A(G)+\beta/2+1\leq A(G)+Perim(G)/2+1$.
\end{proof}


For some $\varphi$ and $c$, half-plane image $M=\hpi{\varphi}{c}$. Consider the half-plane $\hp{\varphi}{c}$. By Claim~\ref{cl:properties-of-reference-HP}, there is a half-plane $\hp{\varphi'}{c'}$ such that the area of the symmetric difference of $\hp{\varphi}{c}$ and $\hp{\varphi'}{c'}$ is at most $\mydelta n^2/2$, where $\varphi'\in D_{\mydelta}$ and $c$ is  a multiple of $a$. 

Recall that there are 4 cases for the symmetric difference of $H$ and $H'$. More precisely, it consists of: 1) two triangles, 2) a triangle and a quadrilateral, 3) a quadrilateral, or 4) two quadrilaterals. We consider the last case (this is the hardest case and the three other cases are handled similarly). Let the symmetric difference of $H$ and $H'$ consist of two quadrilaterals $Q_1$ and $Q_2$. (For reference, see Figure~\ref{fig:nearby-ref-halfplane2} where a triangle and a quadrilateral are shown.) Every line segment in the image has length at most $\sqrt{2}n$. Thus, $Perim(Q_1)+Perim(Q_2)\leq 6\sqrt{2}n$. By Proposition~\ref{prop:area-pixel}, we obtain that $Pix(Q_1)+Pix(Q_2)\leq A(Q_1)+A(Q_2)+(Perim(Q_1)+Perim(Q_2))/2+2\leq \eps n^2/2+3\sqrt{2}n+2\leq\eps n^2/1.8$ (recall that $\eps\in(90/n,1/4)$). This completes the proof.
\end{proof}
}
\subparagraph{Analysis of Algorithm~\ref{alg:half-plane}.}
Let $d_M$ be the distance of $M$ to being a half-plane. Then there exists a half-plane matrix $M^{*}$ such that $\dis(M,M^{*})=d_M$.
By a uniform convergence bound (see, e.g., \cite{Avrim-lecture-notes}), since $s\geq (2.6/\mydelta^2)(\ln |M_\mydelta| + \ln 6)$ for all $\mydelta\in(0,1/4)$, we get that with probability at least 2/3,
$|\dis(M,M')-\dout(M')|\leq \mydelta/2.25$ for all $M'\in M_\mydelta$. Suppose this event happened. Then $\dout\geq d_M-\mydelta/2.25$ because $\dis(M,M')\geq d_M$ for all half-planes $M'$. Moreover, by Lemma~\ref{lem:properties-of-reference-HP}, there is a matrix $\hat{M}\in H_{\mydelta}$
such that $\dis(M,\hat{M})\leq\dis(M,M^*)+\dis(M^*,\hat{M})
\leq d_M+\mydelta/1.8$. For this matrix, $\dout(\hat{M})\leq\dis(M,\hat{M})+\mydelta/2.25\leq d_M+\mydelta.$ Thus,
$d_M-\mydelta/2.25\leq\dout\leq d_M+\mydelta.$ That is, $|d_M-\dout|\leq \mydelta$ with probability 2/3, as required.


\subparagraph{Sample and time complexity.} The number of samples, $s$, is $O(1/\mydelta^2 \log 1/\mydelta)$. To analyze the running time, recall that $|D_\mydelta|=O(1/\mydelta)$. For each direction in $D_\mydelta$, we perform a bucket sort of all samples in expected $O(s)$ time. The remaining steps in the {\bf foreach} loop of Step~\ref{step:half-planes-foreach-dir} can also be implemented to run in $O(s)$ time. The expected running time of Algorithm~\ref{alg:half-plane} is thus $O(1/\mydelta \cdot s)=O(1/\mydelta^3\log 1/\mydelta)$.
Remark~\ref{remark:bernoulli} implies a tester with the same worst case running time.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Half-plane short version finishes here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifnum\full=1
\begin{corollary}\label{cor:half-plane-agnostic-learner}
The class of half-plane images is properly agnostically PAC-learnable with sample complexity  $O(\frac{1}{\mydelta^2}\log\frac{1}{\mydelta})$ and time complexity $O(\frac{1}{\mydelta^{3}}\log \frac{1}{\mydelta})$ under the uniform distribution.
\end{corollary}
\begin{proof}
We can modify Algorithm~\ref{alg:half-plane} to output, along with $\dout=\min_{M'\in M_\mydelta}\dout(M')$, a reference half-plane $\hat{M}$ that minimizes it. By the analysis of Algorithm~\ref{alg:half-plane}, with probability at least 2/3, the output $\hat{M}$ satisfies $\dis(M,\hat{M})\leq d_M+\mydelta.$
\end{proof}
\fi


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Commented out section on half-plane tester.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Distance Approximation to the Nearest Convex Image}\label{sec:convexity}
An image is \emph{convex} if the convex hull of all black pixels contains only black pixels.
%In this section, we give a nonadaptive $\ste$ for convexity. The tester samples
%pixels uniformly at random and finds the convex hull $B$ of black pixels from
%the sample. It rejects if there is a white pixel in $B$ and accepts
%otherwise. We construct regions $B',W$ and $F$ such that $B'$ is inside $B$
%and a convex image is obtained by making all pixels in $B'$ black and all pixels
%in $W\cup F$ white. We prove that the number of pixels in $F$ and with high
%probability the number of black pixels in $W$ are ``small''. This implies
%that $B'$ contains ``many'' white pixels (that are also in $B$) and thus,
%Algorithm~\ref{alg:nonadaptive-convexity-tester} detects at least one of them
%with high probability in Step~\ref{step:accept-reject}.
%
%In this section, we give an algorithm that approximates the distance of an image to being convex. Its performance is summarized in the following theorem.
\begin{theorem}\label{thm:convexity_dist_appr}
For $\eps\in(n^{-1/6},1/4)$, there is a uniform $\mydelta$-additive distance approximation algorithm for convexity with sample complexity $O(\frac{1}{\mydelta^{2}}\log \frac 1 \mydelta)$ and running time $O(\frac 1 {\mydelta^8})$.
\end{theorem}
\begin{proof}
The starting point for our algorithm for approximating the distance to convexity (Algorithm~\ref{alg:convexity-dist-approximation}) is similar to that of Algorithm~\ref{alg:half-plane} that approximates the distance to a nearest half-plane. We define a small set $P_\mydelta$ of reference polygons. Algorithm~\ref{alg:convexity-dist-approximation} %samples pixels uniformly at random, and
implicitly learns a nearby reference polygon and outputs the empirical distance from the image to that polygon. The key features of $P_\mydelta$ is that (1) every convex image has a nearby polygon in $P_\mydelta$, and (2) one can use dynamic programming (DP) to quickly compute the smallest empirical distance to a polygon in $P_\mydelta$.

We start by defining reference directions, lines, points, and line-point pairs that are later used to specify our DP instances.  %We assume w.l.o.g.\ that $1/\mydelta$ is an integer.
Reference directions are almost the same as in Definition~\ref{def:reference-half-planes}.





\begin{definition}[Reference lines, line-point pairs]\label{def:reference-lines}
Fix $\bigdelta=\mydelta/\con$.  The set of {\em reference directions} is $D_\mydelta=\{\pi/2\}\cup\{i\bigdelta:~i\in [0,\lceil 2\pi/\bigdelta\rceil)\}.$
For every $\varphi\in D_\mydelta$, define the set of {\em reference lines} $L_\varphi = \{\ell : \ell \text{ passes through the image and satisfies the equation }x\cos\varphi +y\sin\varphi = c, $\ where $c$ is an integer multiple of  $\bigdelta n$$\}$.
%\mch{Lines in $L_\mydelta$ are called {\em\bf{type-1} reference lines}}.
For each reference line, the set of {\em reference points on $\ell$} contains points w.r.t.\ $\ell$, which are inside $[0,n-1]^2$, spaced exactly $\bigdelta n$  apart (it does not matter how the initial point is picked). A {\em line-point pair} is a pair $(\ell,b),$ where $\ell$ is a %type-1
reference line and $b$ is a reference point w.r.t.\ $\ell$. (Note that there could be reference points on $\ell$ that were defined w.r.t.\ some other reference line. This is why we say ``a reference point w.r.t.\ $\ell$'', and not ``a reference point on $\ell$''.)
%\mch{Let $(\ell,b)$ and $(\ell',b')$ be any distinct line-point pairs. The line that passes through points $b$ and $b'$ is called a {\em\bf{type-2} reference line}}.
\end{definition}

Roughly speaking, a reference polygon is a polygon whose vertices are defined by line-point pairs. There are additional restrictions that stem from the fact that we need to be able to efficiently find a nearby reference polygon for an input image. The actual definition specifies which actions we can take while constructing a reference polygon. Reference polygons are built starting from reference boxes, which are defined next.

\ifnum\full=1
\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-tolerant-ref-box.pdf}
\caption{ A reference box.}
\label{fig:bounding-box}
\end{minipage}
\hspace{0.1\linewidth}
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-Triangles-of-T0.pdf}
\caption{ Triangles of the set $T_0$.}
\label{fig:triangles-T0}
\end{minipage}
\end{figure}
\fi


\begin{definition}[Reference box]\label{def:reference-box}
A {\em reference box} is a set of four line-point pairs $(\ell_i,b_i)$ for $i=0,1,2,3$, where $\ell_0,\ell_2$ are distinct horizontal lines, such that $\ell_0$ is above $\ell_2$, and $(\ell_1,\ell_3)$ are distinct vertical lines, such that $\ell_1$ is to the left of $\ell_3$. The reference box defines a vertex set $B_0=\{b_0,b_1,b_2,b_3\}$ and a triangle set $\Tstart,$ formed by removing the quadrilateral $b_0b_1b_2b_3$ from the rectangle delineated by the lines $\ell_0,\ell_1,\ell_2,\ell_3$\ifnum\full=1.
See Figures~\ref{fig:bounding-box}-~\ref{fig:triangles-T0}.
\else
.
\fi
\end{definition}
\ifnum\full=1
Note that line-point pairs do not depend on the input.
\else

\fi
Intuitively, by picking a reference box, we decide to keep the area inside the quadrilateral $b_0b_1b_2b_3$ black, the area outside the rectangle formed by $\ell_0,\ell_1,\ell_2,\ell_3$ white, and the triangles in $\Tstart$ gray, i.e., undecided for now.

\begin{definition}
For points $x,y$, let $\ell(x,y)$ denote the line that passes through $x$ and $y$. Let $xy$ denote the line segment between $x$ and $y$\ifnum\full=0 . \else\ and $|xy|$ denote the length of $xy$.\fi
\end{definition}

Reference polygons are defined next.  Intuitively, to obtain a reference polygon, we keep subdividing ``gray'' triangles in $\Tstart$ into smaller triangles and deciding to color the smaller triangles black or white or keep them gray (i.e., undecided for now). We also allow ``cutting off'' a quadrilateral that is adjacent to black and coloring it black (a.k.a.\ ``the base change operation'').
\ifnum\full=1
The main recoloring operation from Definition~\ref{def:reference-polygons} is illustrated in Figure~\ref{fig:tolerant-reducing-area}.
\fi
Even though the definition of reference polygons is somewhat technical, the readers can check their understanding of this concept by following Algorithm~\ref{alg:convexity-dist-approximation}, as it chooses the best reference polygon to approximate the input image.

\begin{definition}[Reference polygon]\label{def:reference-polygons}
A {\em reference polygon} is an image of a polygon $\hull(B),$ where the set
$B$ can be obtained from a reference box with a vertex set $B_0$ and a triangle set $\Tstart$ by the following recursive process.
Initially, $\Tend=\emptyset$ and $B=B_0$. %\{\bigtriangleup b_0b_1b_2,\bigtriangleup b_0b_3b_2\}.$
While $\Tstart\neq\emptyset,$ move a triangle $T$ from $\Tstart$ to $\Tend$ and
%\ifnum\full=1
perform the following steps:
%\else
%do the following:
%\fi

\begin{enumerate}
\item\label{item:ref-poly-definition} {\sf (Base Change).} Let $T=\bigtriangleup b'b''v,$ where
 $b',b''\in B.$ Select reference point $b'_0$ on $b'v$ w.r.t.\ line $\ell(b',v)$, and reference point $b''_0$ on $b''v$ w.r.t.\ line $\ell(b'',v)$. Add $b'_0,b''_0$ to $B$. (This corresponds to coloring the quadrilateral $b'b'_0b''_0b''$ black.) Let $h$ be the height of $\bigtriangleup b'_0b''_0v$ w.r.t.\ the base $b'_0b''_0.$

 %($h=0$ if $b'_0=b''_0=v$). Sofya: I think it is clear.

\item\label{item:ref-poly-definition-tall} {\sf (Subdivision Step)} If $h>6\bigdelta n$, choose whether to proceed with this step or go to Step~\ref{item:ref-poly-definition-short} (both choices correspond to a legal reference polygon); otherwise, go to Step~\ref{item:ref-poly-definition-short}. Let $\varphi$ be the angle between $\ell(b'_0,b''_0)$ and the $x$-axis, and $\hat\varphi\in D_\mydelta$ be such that $|\hat\varphi-\varphi|\leq {\bigdelta/2}$. Select a reference line-point pair $(\ell,b),$ where the line $\ell\in L_{\hat{\varphi}}$ crosses $b'_0v$ and $b''_0v$, whereas $b$ is in the triangle $\bigtriangleup b'_0b''_0v$. Let $v'$ (resp., $v''$) be the point of intersection of $\ell$ and $b'_0v$ (resp., $\ell$ and $b''_0v$). Let $T'=\bigtriangleup b_0'bv'$, $T''=\bigtriangleup b_0''bv''$%
\ifnum\full=1
, as shown on Figure~\ref{fig:tolerant-reducing-area}%
\fi
. Add $b$ to $B$ and triangles $T',T''$ to $\Tstart$. (This represents coloring $\bigtriangleup b'_0b''_0b$ black and keeping $T'$ and $T''$ gray.)

\item\label{item:ref-poly-definition-short} {\sf (End of Processing)} Do nothing. (This represents coloring $\bigtriangleup b'_0b''_0v$ white).
\end{enumerate}
\end{definition}
%They are specified by line-point pairs. (To specify a polygon, it is of course sufficient to specify its vertices. But it is important for our dynamic programming algorithm that all vertices are reference points on reference lines.)
\ifnum\full=1
\begin{figure}[ht]
\begin{minipage}[b]{0.55\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-tolerant-reducing-area.pdf}
\caption{ An illustration to Definition~\ref{def:reference-polygons}: Triangle $\bigtriangleup b'b''v$.}
\label{fig:tolerant-reducing-area}
\end{minipage}
\hspace{0.01\linewidth}
\begin{minipage}[b]{0.48\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-Rectangle-and-regions-of-lines-0.pdf}
\caption{ Regions $W_{\ell_0}$, $W_{\ell_1}$, $W_{\ell_2}$, and $W_{\ell_3}$.}
\label{fig:w-regions}
\end{minipage}
\end{figure}
\fi

By Remark~\ref{remark:bernoulli}, to prove Theorem~\ref{thm:convexity_dist_appr}, it suffices to design a Bernoulli tester that takes $s=O(\frac 1 {\mydelta^2}\log \frac 1\mydelta)$ samples in expectation and runs in time $O(\frac 1 {\mydelta^8})$. Our Bernoulli tester is Algorithm~\ref{alg:convexity-dist-approximation}.
In Algorithm~\ref{alg:convexity-dist-approximation}, we use the following notation for the (relative) empirical error with respect to an input image $M$, a set of sampled pixels $S,$ and the size parameter $s$. For an image $M'$, let
$\dout(M')=\frac 1 s \cdot |\{u\in S : M[u]\neq M'[u]\}|.$ For every region $R\subseteq\domain$, we let
$\dout_+(R)=\frac 1 s \cdot |\{u\in S\cap R : M[u]=0\}|,$ and
$\dout_-(R)=\frac 1 s \cdot |\{u\in S\cap R : M[u]=1\}|,$ i.e., the empirical error if we make $R$ black/white, respectively.

\begin{algorithm}
\caption{Bernoulli approximation algorithm for distance to convexity.}
\label{alg:convexity-dist-approximation}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameters $n\in\mathbb{N}$, $\mydelta\in(0,1/4)$; Bernoulli access to an $n\times n$ binary matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl\label{step:convexity-approx:sample}
Set $s=\Theta(\frac 1 {\mydelta^2}\log \frac 1\mydelta)$.
Include each image pixel in the sample $S$ w.p.\ $p=s/n^2$.\;
\tcp{Run the algorithm to find $\dout$, the smallest fraction of samples misclassified by a reference polygon in $P_\mydelta$. A dynamic programming implementation of the algorithm is given in \ifnum\full=0 Section~4.3 of the {\color{black} full version}.\else Section~\ref{sec:convexity-dist-approx-wrap-up}.\fi }
\nl
Let $W_{\ell_0}$ (resp., $W_{\ell_2}$) be the set of pixels of the image $M$ that lie either above $\ell_0$ or to the left of $b_0$ on $\ell_0$ (resp., either below $\ell_2$ or to the left of $b_2$ on $\ell_2$). Let $W_{\ell_1}$ (resp., $W_{\ell_3}$) be the set of pixels of $M-W_{\ell_0}-W_{\ell_2}$ to the left of $\ell_1$ (resp., to the right of $\ell_3$). \ifnum\full=1 (See Figure~\ref{fig:w-regions})\fi


\nl
Set $\dout=1$.
\;
\nl\label{step:polygons-foreach-top-bottom}
        \ForAll {line-point pairs $(\ell_0,b_0),(\ell_2,b_2)$, where $\ell_0,\ell_2$ are horizontal lines} \do{
\nl\quad\label{step:errle-init}     Set $\errle=1.$ \tcp*{\parbox[t]{4in}{The variable to compute the best error for the region to the left of $b_0b_2$, between $\ell_0$ and $\ell_2$.\;}}
\nl\quad\label{step:polygons-foreach-left}
\ForEach {line-point pair $(\ell_1,b_1)$, where $\ell_1$ is a vertical line} \do{
\nl\quad\quad Let $v_0$ (resp., $v_2$) be the point where $\ell_1$ intersects $\ell_0$ (resp., $\ell_1$ intersects $\ell_2$).\;
\nl\quad\quad\label{step:errle-compute}
               $\errle=\min (\errle,
                \dout_-(W_{\ell_1})+\dout_+(\bigtriangleup b_0b_1b_2)
                +\Best(\bigtriangleup b_0b_1v_0)+\Best(\bigtriangleup b_1b_2v_2))$\;
        }
\nl\quad        Similarly to Steps~\ref{step:errle-init}--\ref{step:errle-compute}, compute  $\errri$.\tcp*{\parbox[t]{10in}{The best error for the region to the right of $b_0b_2$, between $\ell_0$ and $\ell_2$.\;}}

\nl\quad    Compute $\dout=\min(\dout,
                    \dout_-(W_{\ell_0}\cup W_{\ell_2})
                    +\errle+\errri).$\;

    }
\nl         \Return $\dout$.
\end{algorithm}

\ifnum\full=1
Subroutine \Best, presented next,
\else
Subroutine \Best
\fi
chooses the option with the smallest empirical relative error among those given in Definition~\ref{def:reference-polygons}, items~\ref{item:ref-poly-definition}-\ref{item:ref-poly-definition-short}.
\ifnum\full=0
Its pseudocode is in the {\color{black} full version}.
\else
\begin{algorithm}
\caption{Subroutine \Best used in Algorithm~\ref{alg:convexity-dist-approximation}.}
\label{alg:subroutine-best}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{triangle $\bigtriangleup b'b''v$}
\DontPrintSemicolon
\BlankLine
\tcp{Use dynamic programming (see Section~\ref{sec:convexity-dist-approx-wrap-up} for implementation details).}
\nl Set $d^*=1.$

\nl\quad\label{step:forall-best-type2}\ForAll {reference points $b'_0$ and $b''_0$ on the sides $b'v$ and $b''v,$ respectively,}\do{

\nl\quad\quad Compute $d^*=\min(d^*, d_+(b'b''b''_0b'_0)+\BestFixed(b'_0b''_0v))$}

\nl\quad \Return $d^*$

\end{algorithm}


\begin{algorithm}\label{alg:subroutine-best-fixed-base}
\caption{Subroutine \BestFixed used in Algorithm~\ref{alg:subroutine-best}.}
\label{alg:subroutine-best-fixed-base}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{triangle $\bigtriangleup b'_0b''_0v$}
\DontPrintSemicolon
\BlankLine
\nl Set $d^*=d_-(\bigtriangleup b'_0b''_0v)$\;
\nl \If {the height of $\bigtriangleup b_1b_2v$ w.r.t.\ the base $b_1b_2$ is more than $6\bigdelta n$}{
%\nl            \Return $d^*$ }

%\nl\lElse{


\nl\quad\label{step:foreach-best-type1}\ForEach {line-point pair $(\ell,b)$, where $\ell\in L_{\hat\varphi}$ (see Definition~\ref{def:reference-polygons}, item 2), $b\in\bigtriangleup bb'_0b''_0$,
line $\ell$ intersects the side $b'_0v$ at some point $v'$ and the side $b''_0v$ at some point $v''$, resp.
} \do{

\nl\quad\quad Compute $d^*=\min(d^*, \dout_-(\bigtriangleup v'v''v)+\dout_+(\bigtriangleup b'_0b''_0b)
                +\Best(\bigtriangleup b'_0bv')+\Best(\bigtriangleup bb''_0v''))$
}}

\nl \Return $d^*$

\end{algorithm}
\fi

\ifnum\full=0
Our set of reference polygons has two critical features. First, for each convex image there is a nearby reference polygon. It turns out that the empirical error for a region is proportional to the square root of its area. The second key feature of our reference polygons is that, for each of them, the set of considered triangles, $\Tend$, has small $\sum_{T\in\Tend} \sqrt{A(T)},$ where $A(T)$ denotes the area of triangle $T$. The proofs of both features, as well as the analysis of the empirical error, are quite technical and appear in the {\color{black} full version}.\end{proof}

Here, we state and partially prove a lemma that puts together different parts of the analysis. It makes it clear why the empirical error of each region is proportional to the square root of its area which is, as explained in Footnote~\ref{fn:Pick}, a proxy for the number of pixels in it.


\else
Our set of reference polygons has two critical features. First, for each convex image there is a nearby reference polygon. This is proved in Section~\ref{sec:existence-of-nearby-ref-poly}. It turns out that the empirical error for a region is proportional to the square root of its area. The second key feature of our reference polygons is that, for each of them, the set of considered triangles, $\Tend$, has small $\sum_{T\in\Tend} \sqrt{A(T)}.$ The proof of this fact, as well as the analysis of the empirical error appears in Section~\ref{sec:convexity-dist-approx-error-analysis}. Finally, Section~\ref{sec:convexity-dist-approx-wrap-up} completes the analysis of the algorithm, gives details of its implementation and presents the corollary about agnostic PAC learning of convex objects.

\subsection{Existence of a nearby reference polygon}\label{sec:existence-of-nearby-ref-poly}
\begin{lemma}\label{lem:nearby-reference-polygon}
 For every convex image $M$, there exists $M'\in P_\mydelta$ such that $\dis(M,M')\leq\mydelta/6$.
\end{lemma}


\begin{proof}
Consider a convex image $M$. We will show how to construct a nearby reference polygon $M'$ using the recursive process in Definition~\ref{def:reference-polygons}. First, we obtain a reference box (see Definition~\ref{def:reference-box}) for $M$ as follows. Let $(\ell_0,b_0)$ be a line-point pair, where $b_0$ is black in $M$ and $\ell_0$ is the topmost horizontal line that contains such a reference point. Similarly, define $(\ell_2,b_2)$, replacing ``topmost'' with ``bottommost''. Analogously, define the two line-point pairs $(\ell_1,b_1)$, $(\ell_3,b_3)$ with vertical lines. The four line-point pairs $(\ell_i,b_i)$ for $i\in\integerset{4}$ define the reference box for $M$, as shown in Figure~\ref{fig:reference-box}.

\begin{figure}[ht]
\centering
\includegraphics[width=0.5\linewidth]{figure-reference-box.pdf}
\caption{ Reference box for a convex image $M$.}
\label{fig:reference-box}
\end{figure}




Next we construct the set $B$ from the reference box, as in Definition~\ref{def:reference-polygons}.  We also maintain two sets of line segments, $F_1$ and $F_2$, that are used in the analysis. Initially, $F_1=F_2=\emptyset$. The colors of the points in the description below are with respect to the convex image $M$. This is how we make the choices at each step of the recursive process in Definition~\ref{def:reference-polygons} to obtain our reference polygon:
\begin{enumerate}
\item {\sf (Base Change)} Choose $b'_0,b''_0$ to be the furthest from $b'b''$ black reference w.r.t.\ lines $\ell(b',v)$ and $\ell(b'',v)$, respectively. Recall that $h$ is the height of $\bigtriangleup b'_0b''_0v$ w.r.t.\ the base $b'_0b''_0$.

\item {\sf (Subdivision Step)} If $h>6\bigdelta n$, let $B_M$ denote the convex hull of all black pixels in $M$ and points $b'_1,b''_1$ be the intersection points of $B_M$ with $b'_0v$ and $b''_0v$, respectively. Choose a line-point pair $(\ell,b)$ such that $\ell\in L_{\hat\varphi}$ is the furthest from $b'_1b''_1$ line that intersects $b'v$ and $b''v$,  and $b$ is black.  Let $\ell$ intersect $b'v$ and $b''_1v$ at $v'$ and $v''$, respectively and let it intersect $B_M$ at $y'$ and $y'',$ as in Figure~\ref{fig:small-error-ref-poly-1}. Put the line segment $y'y''$ in $F_1$ and $\bigtriangleup v'v''v$ in $\Tcut$. If no line in $L_{\hat\varphi}$ contains a black reference point in $\bigtriangleup b'_1b''_1v$ or if $h\leq 6\bigdelta n,$ go to Step 3.

\item {\sf (End of Processing)} Put the line segment $b'_1b''_1$ in $F_2$ and $\bigtriangleup b'_0b''_0v$ in $\Tfin$. Triangle $\bigtriangleup b'_0b''_0v$ is not subdivided and is called a {\em final} triangle.
\end{enumerate}



Observe that $M$ and $M'$ differ only on three types of regions: outside of the reference box, inside the triangles in $\Tfin$, and inside the triangles in $\Tcut$. To show that $\Dis(M,M')\leq\frac{\mydelta n^2}{6},$ we prove in Claims~\ref{cl:error-in-strips}, \ref{cl:error-in-triangles}, and \ref{cl:small-area-above-line} that the number of disagreements in each of the three regions is small.
For any region $R\subseteq\domain$, let $\myerr{R}=|\{u\in R : M[u]\neq M'[u]\}|$.


Next claim
%\ifnum\full=1
follows from the analysis of the convexity tester in \cite{Ras03}.
%\else is implicit in \cite{Ras03}.
%\fi
\begin{claim}
\label{cl:error-in-strips}
The number of black pixels in $M$
%inside $\cup_{i\in\integerset{4}} W_{\ell_i}$
outside the reference box is at most $12\cdot\bigdelta n^2$.
\end{claim}
\mch{

\begin{claim}\label{cl:error-in-triangles}
Let $\bigtriangleup b'_0b''_0v$ be a final triangle and points $b'_1,b''_1$ be the points of intersection of $B_M$ with $b'_0v$ and $b''_0v$, respectively. Then $\myerr{\bigtriangleup b'_0b''_0v}\leq 4\cdot|b'_1b''_1|\bigdelta n+2$.
\end{claim}


\begin{figure}[ht]
\centering
\includegraphics[width=0.7\linewidth]{small-error-ref-polygon-1.pdf}
\caption{ An illustration to Subdivision Step in $\bigtriangleup b'_0b''_0v$.}
\label{fig:small-error-ref-poly-1}
\end{figure}


\begin{proof}
By Proposition~\ref{prop:area-pixel}, $\myerr{\bigtriangleup b'_0b''_0v}\leq Pix(\bigtriangleup b'_1b''_1v)\leq A(\bigtriangleup b'_1b''_1v)+Perim(\bigtriangleup b'_1b''_1v)/2+1$. Note that $\angle b'_1vb''_1$ is obtuse.
\begin{proposition}
\label{prop:obtuse-height}
Let $T$ be a triangle with sides ${\bf a,b}$ and ${\bf c}$. Let $\alpha$ be the angle opposite to side ${\bf a}$, and ${\bf h_a}$ be the height w.r.t.\ base ${\bf a}$ in $T$. If $\alpha\geq \pi/2$ then ${\bf h_a}\leq {\bf a}/2$.
\end{proposition}
\begin{proof}
By the cosine theorem, ${\bf a^2}={\bf b^2}+{\bf c^2}-2{\bf b}{\bf c}\cdot\cos{\alpha}\geq {\bf b^2}+{\bf c^2}\geq 2{\bf b}{\bf c}\geq4\cdot A(T)=2\cdot{\bf a}\cdot {\bf h_a}$. Thus, ${\bf h_a}\leq {\bf a}/2$, as claimed.
\end{proof}
If $h\leq 6\bigdelta n$ then by Proposition~\ref{prop:obtuse-height}, the area $A(\bigtriangleup b'_1b''_1v)\leq 3\cdot|b'_1b''_1|\bigdelta n$. Since $Perim(\bigtriangleup b'_1b''_1v)\leq 3\cdot|b'_1b''_1|$ we obtain that $A(\bigtriangleup b'_1b''_1v)+Perim(\bigtriangleup b'_1b''_1v)/2+1\leq 3\cdot|b'_1b''_1|\bigdelta n+1.5\cdot|b'_1b''_1|+1\leq 4\cdot|b'_1b''_1|\bigdelta n+2$ and the claim holds (recall that $\eps=\Omega(1/n)$). Now assume that $h>6\bigdelta n$ and no line in $L_{\hat\varphi}$ with a black reference point intersects the line segments $b'_1v$ and $b''_1v$ in $\bigtriangleup b'_0b''_0v$.



\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{small-error-ref-polygon-2.pdf}
\caption{ An illustration of triangle $\bigtriangleup y'y''\hat v$.}
\label{fig:small-error-ref-poly-2}
\end{figure}

\begin{proposition}
\label{prop:small-error-above}
Let $\bigtriangleup b'_0b''_0v$ be a triangle in which $\angle b'_0vb''_0$ is obtuse and $B_M$ intersects the sides $b'_0v$ and $b''_0v$. Let $\ell\in L_{\hat\varphi}$ be a line that intersects $B_M$ at $y'$ and $y''$, and it intersects $b'_0v$ and $b''_0v$ at $v'$ and $v''$, respectively. See Figure~\ref{fig:small-error-ref-poly-2}. Then $\myerr{v'v''v}\leq\frac{|y'y''|^2}{4}+\frac{3|y'y''|}2+1$.
\end{proposition}
\begin{proof}
Let $\hat{v}$ be a point (inside $\bigtriangleup b'_0b''_0v$) such that $\ell(y',\hat{v})$ is parallel to $\ell(b'_0v)$ and $\ell(y'',\hat{v})$ is parallel to $\ell(b''_0v)$. Since $B_M$ is convex, the portion of $B_M$ in $\bigtriangleup v'v''v$ is entirely inside $\bigtriangleup y'y''\hat{v}$. Angle $\angle y'\hat{v}y''$ is obtuse since $\angle y'\hat{v}y''=\angle b'_0vb''_0$. Then by Proposition~\ref{prop:obtuse-height}, $A(\bigtriangleup y'y''\hat{v})\leq\frac{|y'y''|^2}{4}$. Note that $Perim(\bigtriangleup y'y''\hat{v})\leq 3|y'y''|$. Since $\myerr{v'v''v}\leq Pix(\bigtriangleup v'v''v)$ then by Proposition~\ref{prop:area-pixel}, $\myerr{v'v''v}\leq\frac{|y'y''|^2}{4}+\frac{3|y'y''|}2+1$.
\end{proof}

Let $\ell\in L_{\hat\varphi}$ be the line that does not intersect the line segment $b'_1b''_1$ and that is closest to it. Let $\ell$ intersect the line segments $b'_1v$ and $b''_1v$ at $v'$ and $v''$. Then either $\angle v'v''v\leq \angle b'_0b''_0v$ or $\angle v''v'v\leq \angle b''_0b'_0v$. W.l.o.g. assume that $\angle v'v''v\leq \angle b'_0b''_0v$.
Let $\hat{\ell}$ be the line that is parallel to $\ell$ and that passes through point $b''_0$ as shown in Figure~\ref{fig:small-error-ref-poly-3}. Let $v'_1$ be the intersection point of $\hat{\ell}$ and the line segment $b'_0v$. Denote the angle between $\hat{\ell}$ and $\ell(b'_0,b''_0)$ by $\gamma$. The distance between $\ell$ and $\hat{\ell}$ is at  most $2\bigdelta n$. Otherwise there are two distinct lines from $L_{\hat\varphi}$ that pass through the line segment $b''_0b''_1$. Since $|b''_0b''_1|\leq \bigdelta n$ the distance between the two lines is less than $\bigdelta n$, contradiction.

\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{small-error-ref-polygon-3.pdf}
\caption{ An illustration of line $\hat{\ell}$ in $\bigtriangleup b'_0b''_0v$.}
\label{fig:small-error-ref-poly-3}
\end{figure}

Now we find an upper on the number of black pixels in $\bigtriangleup b'_0b''_0v$. Let $B_M$ intersect $\ell$ at $y'$ and $y''$. Then $|y'y''|\leq \bigdelta n$. By Proposition~\ref{prop:small-error-above}, $Pix(\bigtriangleup v'v''v)\leq\frac{(\bigdelta n)^2}4+\frac{3\bigdelta n}2+1.$ The number of black pixels in the rectangle $b'_0b''_0v''v'$ is at most $Pix(b'_0b''_0v''v')$. The area
$$A(b'_0b''_0v''v')=A(v'_1b''_0v''v')+A(\bigtriangleup b'_0b''_0v'_1)\leq 2\bigdelta n|v'_1b''_0|+A(\bigtriangleup b'_0b''_0v'_1)\leq2|b'_0b''_0|\bigdelta n+A(\bigtriangleup b'_0b''_0v'_1).$$
The last inequality holds since $\angle b'_0v'_1b''_0$ is obtuse. Let $d_1$ (resp., $d_2$) denote the distance from the point $v'$ (resp., $v'_1$) to the line $\ell(b'_1,b''_1)$. We find an upper bound on $A(\bigtriangleup b'_0b''_0v'_1)$:

$$A(\bigtriangleup b'_0b''_0v'_1)=\frac{|b'_0b''_0|\cdot d_2}{2}=\frac{|b'_0b''_0|\cdot|b''_0v'_1|\cdot\sin{\gamma}}{2}\leq \frac{|b'_0b''_0|\cdot \sqrt{2}n(\bigdelta/2)}{2}<0.4|b'_0b''_0|\cdot\bigdelta n.$$ Thus, $A(b'_0b''_0v''v')\leq 2.4\cdot|b'_0b''_0|\bigdelta n$. The height $h\leq d_1+\bigdelta n$. By Proposition~\ref{prop:obtuse-height}, if $|b'_1b''_1|\leq10\bigdelta n$ then $d_1\leq5\bigdelta n$. It implies that $h\leq6\bigdelta n$, contradiction. Therefore, $|b'_1b''_1|>10\bigdelta n$. By the triangle inequality $|b'_0b''_0|\leq |b'_1b''_1|+2\bigdelta n$. Thus,
$$A(b'_0b''_0v''v')\leq 2.4\cdot(|b'_1b''_1|+2\bigdelta n)\bigdelta n\leq 3\cdot|b'_1b''_1|\bigdelta n.$$ The last inequality holds since $|b'_1b''_1|>10\bigdelta n$. Note that $$Perim(b'_0b''_0v''v')/2\leq 2\cdot|b'_0b''_0|\leq 2|b'_1b''_1|+4\bigdelta n.$$ Thus, by Proposition~\ref{prop:area-pixel}, $$Pix(b'_0b''_0v''v')\leq 3\cdot|b'_1b''_1|\bigdelta n+2|b'_1b''_1|+4\bigdelta n+1$$
and $$\myerr{\bigtriangleup b'_0b''_0v}\leq Pix(b'_0b''_0v''v')+Pix(\bigtriangleup v'v''v)\leq 3\cdot|b'_1b''_1|\bigdelta n+2|b'_1b''_1|+4\bigdelta n+1+\frac{(\bigdelta n)^2}4+\frac{3\bigdelta n}2+1\leq$$ $$\leq4\cdot|b'_1b''_1|\bigdelta n+2.$$
The last inequality holds since $|b'_1b''_1|>10\bigdelta n$. This completes the proof of Claim~\ref{cl:error-in-triangles}.
\end{proof}
\begin{claim}
\label{cl:small-area-above-line}
Let triangle $\bigtriangleup b'_0b''_0v$ and line $\ell$ be as defined in Step 2 of the recursive construction of $M'$. Let $v'$ and $v''$ denote the points of intersection of $\ell$ and $b'_0v$ and $b''_0v$, respectively. Let $y'$ and $y''$ be the points of intersection of $B_M$ and $\ell$. Then $\myerr{\bigtriangleup v'v''v}\leq 4\cdot|y'y''|\bigdelta n+2$.
\end{claim}
\begin{figure}[ht]
\centering
\includegraphics[width=0.7\linewidth]{figure-error-above-line}
\caption{ An illustration of line $\ell'$ in triangle $\bigtriangleup b'_0b''_0v$.}
\label{fig:error-above-l}
\end{figure}

\begin{proof}
If $|y'y''|\leq \bigdelta n$ then, by Proposition~\ref{prop:small-error-above}, $\myerr{\bigtriangleup v'v''v}\leq \frac{|y'y''|^2}4+\frac{3|y'y''|}2+1\leq 4\cdot|y'y''|\bigdelta n+2.$ Now assume that $|y'y''|>\bigdelta n$. Let $\ell'\in L_{\hat\varphi}$ be the line at distance $\bigdelta n$ from $\ell$ closer to $v$, as in Figure~\ref{fig:error-above-l}. Let $\ell'$ intersect $b'_0v$ and $b''_0v$ at $v'_1$ and $v''_1$, respectively. Then $\myerr{v'v'_1v''_1v''}$ is at most the number of black pixels in $v'v'_1v''_1v''$. Note that all black pixels in $v'v'_1v''_1v''$ are inside a rectangle with length $|y'y''|$. Thus, by Proposition~\ref{prop:area-pixel}, the number of black pixels in $v'v'_1v''_1v''$ is at most $|y'y''|\bigdelta n+2|y'y''|+1$. The distance between the points of intersection of $B_M$ with $\ell'$ is at most $\bigdelta n$. Thus, by Proposition~\ref{prop:small-error-above},
$$\myerr{v'v''v}\leq|y'y''|\bigdelta n+2|y'y''|+1+\frac{(\bigdelta n)^2}{4}+\frac{3\bigdelta n}2+1\leq 4\cdot|y'y''|\bigdelta n+2.$$ The last inequality holds since $|y'y''|>\bigdelta n$. This completes the proof of Claim~\ref{cl:small-area-above-line}.
\end{proof}


Observe that all points in $B$ lie on the boundary of a convex polygon. Images $M$ and $M'$ differ only on pixels outside of the reference box and inside the triangles $\bigtriangleup b'_1b''_1v$ and $\bigtriangleup v'v''v$. %(intuitively ``above'' the line segments in $F_1\cup F_2$).
All the line segments in $F_1\cup F_2$ are the sides of a convex polygon which is inside an $n\times n$ square. Thus, the sum of the lengths of the line segments in $F_1\cup F_2$ is at most $4n$. Now we find an upper bound on $|\Tfin|$. Note that in the process of constructing a reference polygon starting from triangles in $\Tstart$, every triangle is subdivided into at most two new triangles. Fix a triangle $T\in\Tstart$. Consider a binary tree $\mathcal{B}_T$ rooted at $T$, where every node is some triangle obtained during the reference polygon construction and every triangle in $\mathcal{B}_T$ has at most two children triangles obtained after subdivision of their parent (during the construction). Triangles in $\Tfin$ correspond to the leaves of the binary tree. Thus, to upperbound $|\Tfin|$ we need to find the maximum possible height of $\mathcal{B}_T$ and we need to assume that the tree is full. Recall $\bigtriangleup b_0'b_0''v$ and $h$ from the construction of a reference polygon. Triangle $\bigtriangleup b_0'b_0''v$ is not subdivided if $h\leq6\bigdelta n$. By Proposition~\ref{prop:obtuse-height}, if $A(\bigtriangleup b_0'b_0''v)\leq 36(\bigdelta n)^2$ then $h\leq 6\bigdelta n$. Thus, a triangle is not subdivided if its area drops below $36(\bigdelta n)^2$. Note that every triangle in $\Tstart$ has area at most $n^2$. Consider a triangle $T_1$ in $\mathcal{B}_T$ with two children $T'_1$ and $T''_1$. Let $k$ be the height of $\mathcal{B}_T$. By Claim~\ref{claim:sum-of-roots-of-areas}, $\max\{A(T'_1),A(T'_2)\}\leq \frac 2 3 A(T_1)$.
Thus, every triangle in level $i\in[k]$ of $\mathcal{B}_T$ has area at most $(2/3)^i n^2$. The area of every triangle in level $k-1$ of $\mathcal{B}_T$ is at least $36(\bigdelta n)^2$ (otherwise, non of the triangles in this level is subdivided and the height of $\mathcal{B}_T$ cannot be $k$). We obtain that $(2/3)^{k-1} n^2\geq 36(\bigdelta n)^2$ and thus, $k\leq 5\cdot\ln \frac {30} {\eps}$. Therefore, the number of leaves in $\mathcal{B}_T$ is at most $2^k\leq n/4$ (recall that $\eps>n^{-1/5}$) and $|\Tfin|\leq 4\cdot(n/4)=n$. By Claims~\ref{cl:error-in-strips},~\ref{cl:error-in-triangles} and \ref{cl:small-area-above-line},
$$
\Dis(M,M')\leq (\sum\nolimits_{ b'_1b''_1 \in F_2}|b'_1b''_1|+\cdot\sum\nolimits_{ y'y'' \in F_1}|y'y''|)\cdot4\bigdelta n+12\bigdelta n^2+2|\Tfin|\leq 26\bigdelta n^2+2n\leq 27\bigdelta n^2.
$$
This completes the proof of Lemma~\ref{lem:nearby-reference-polygon}. }
\end{proof}

%%%%%%%%%%
%%% End of: Comenting out the proof of the Nearby Ref. Poly Lemma from short version
%%%%%%%%


\subsection{Error analysis}\label{sec:convexity-dist-approx-error-analysis}

\begin{lemma}\label{lem:sum-of-roots-of-areas}
For each set $\Tend$ obtained in the construction of a reference polygon in Definition~\ref{def:reference-polygons},
$$\sum_{T\in\Tend} \sqrt{A(T)}<11n.$$
\end{lemma}
\begin{figure}[ht]
\centering
\includegraphics[width=0.7\linewidth]{figure-sum-of-roots}
\caption{ Triangle $\bigtriangleup b'_0b''_0v$.}
\label{fig:sum-of-roots}
\end{figure}

\begin{proof}
All triangles in $\Tend$ %, except for the first two,
are obtained by partitioning the four initial triangles in $\Tstart$. The following claim analyzes how the area is affected by one step of partitioning.
%relates the areas of newly formed triangles to the area of the subdivided triangle.
\begin{claim}\label{claim:sum-of-roots-of-areas}
Let $T'$ and $T''$ be two gray triangles obtained from a triangle $T$ in Subdivision Step of Definition~\ref{def:reference-polygons}. Then
%
$\sqrt{A(T')}+\sqrt{A(T'')}\leq \sqrt{\frac 2 3 \cdot A(T)}.$
\end{claim}

\begin{proof}
Observe that $\sqrt{A(T')}+\sqrt{A(T'')}$ is maximized when $b'_0=b'$ and $b''_0=b''$. W.l.o.g.\ we prove the lemma for this case. We use notation from Figure~\ref{fig:sum-of-roots}. Recall that a triangle $T$ is partitioned only if its height $h\geq 6\bigdelta n.$ Since the sides of $T$ are of length at most $\sqrt 2 n$, the height is that large only if both angles adjacent to the base $b'_0b''_0$ are greater than $4\bigdelta$. (To see this, consider an angle $\alpha$ between the base and a side of length $a$. We get
$6\bigdelta n\leq h=a\cdot\sin\alpha\leq \sqrt 2 n \cdot \alpha$.
Thus, $\alpha\geq 6\bigdelta/\sqrt 2> 4\bigdelta.$)

First, we find the maximum value of $\sqrt{A(T')}+\sqrt{A(T'')}$ for a fixed line $\ell$ on which position of point $b$ varies. %i.e., $x$, $y$ are constants and $z$ varies.
\mch{Let $\alpha=\angle b''_0b'_0v$, $\beta=\angle b''_0b'_0v$ and $\gamma$ be the angle between lines $\ell$ and $\ell(b'_0,b''_0)$. W.l.o.g.\ assume that $\angle v'v''v\leq \beta$. Then $\angle v''v'v=\alpha+\gamma$ and $\angle v'v''v=\beta-\gamma$. By the construction of triangles in $\Tend$, $\alpha+\beta\leq\frac{\pi}{2}$ and $\gamma\leq\frac \bigdelta 2$. Let $q=|b'_0v|$, $r=|b''_0v|$, $t=|v'v''|$ and $qx=|v'v|$, $ry=|v''v|$, $tz=|bv''|$ ($x,y,z\in [0,1]$).}  Let\mch{
$$
f(z)=\sqrt{A(T')}+\sqrt{A(T'')}=\sqrt{\frac{q(1-x)\cdot t(1-z)\sin(\alpha+\gamma)}{2}}+\sqrt{\frac{r(1-y)\cdot tz\sin(\beta-\gamma)}{2}}.
$$
Thus, $f(z)=\sqrt{C_1\cdot(1-z)}+\sqrt{C_2\cdot z}$, where $C_1=A(\bigtriangleup b'_0v'v'')$, $C_2=A(\bigtriangleup b''_0v''v')$ are constants. By the  Cauchy-Schwarz inequality, $f(z)=\sqrt{C_1\cdot(1-z)}+\sqrt{C_2\cdot z}\leq\sqrt{(C_1+C_2)(1-z+z)}=\sqrt{C_1+C_2}$.

Next, we find the maximum value of $C_1+C_2$ varying position of $\ell$ inside $T$. We use the fact that
$$
C_1=A(\bigtriangleup b'_0v''v)-A(\bigtriangleup v'v''v)=\frac{(q-qx)ry\cdot\sin(\alpha+\beta)}{2},
$$ $$
C_2=A(\bigtriangleup b''_0v'v)-A(\bigtriangleup v'v''v)=\frac{(r-ry)qx\cdot\sin(\alpha+\beta)}{2}
$$ to obtain
$$
C_1+C_2=\frac{(x+y-2xy)qr\cdot\sin(\alpha+\beta)}{2}=(x+y-2xy)A(T).
$$
We need to show that $x+y-2xy\leq 2/3$. Let $\hat c=\frac y x=\frac{\sin\beta\sin(\alpha+\gamma)}{\sin\alpha\sin(\beta-\gamma)}$. Since $\hat c$ is constant and the geometric mean of two numbers is at most their arithmetic mean $$\sqrt{x+y-2xy}=\sqrt{2\hat c} \cdot \sqrt{x(\frac{1+\hat c}{2\hat c}-x)}\leq \sqrt{2\hat c}\cdot \frac 1 2\cdot (x+\frac{1+\hat c}{2\hat c}-x)=\frac{1+\hat c}{\sqrt{8\hat c}}.$$ We prove that $\frac{(1+\hat c)^2}{8\hat c}\leq \frac 2 3$ which is equivalent to $(3\hat c-1)(\hat c-3)\leq0$. The latter inequality holds if $1\leq\hat c\leq3.$ Function $\sin\theta$ is increasing on $[0,\pi/2]$ thus, $1\leq\hat c.$ Now we show that $\hat c\leq3.$ If $\gamma=0$ the inequality holds. Let us assume that $\gamma>0.$
We need to prove that
$$
\frac{\sin\beta\sin(\alpha+\gamma)}{\sin\alpha\sin(\beta-\gamma)}=\frac{\cot\gamma+\cot\alpha}{\cot\gamma-\cot\beta}\leq3.
$$
Function $\cot\theta$ is decreasing on $(0,\pi/2]$ thus,
$$
\frac{\cot\gamma+\cot\alpha}{\cot\gamma-\cot\beta}\leq\frac{\cot\gamma+\cot4\bigdelta}{\cot\gamma-\cot4\bigdelta}\leq\frac{\cot\gamma+\cot\bigdelta}{\cot\gamma-\cot\bigdelta}\leq3.
$$
The last inequality is equivalent to $2\cot\bigdelta\leq\cot\gamma$ which is true since $2\cot\bigdelta\leq\cot\frac \bigdelta 2\leq \cot\gamma$. This completes the proof of Claim~\ref{claim:sum-of-roots-of-areas}}\end{proof}

Let $A_1,\dots,A_4$ be the areas of the first four triangles in $\Tstart$. Then $\sum_{i=1}^4 A_i\leq n^2$.
By construction of triangles in $\Tend$, Claim~\ref{claim:sum-of-roots-of-areas}, and concavity of the square root function,
$$
\sum_{T\in \Tend} \sqrt{A(T)}\leq
%\sqrt{A(\bigtriangleup b_0b_1b_2 )}+\sqrt{A(\bigtriangleup b_0b_3b_2)}+
K\cdot\sum_{j=1}^4 \sqrt{A_j}\leq 2K\sqrt{A_1+A_2+A_3+A_4}\leq 2K\cdot n,
$$
where $K=\sum_{m=0}^{\infty}(\sqrt{2/3})^m=(1-\sqrt{2/3})^{-1}<5.5$.
%
%Since $A(\bigtriangleup b_0b_1b_2 )+A(\bigtriangleup b_0b_3b_2)\leq Z$, by Holder's inequality,
%$$
%\sqrt{A(\bigtriangleup b_0b_1b_2 )}+\sqrt{A(\bigtriangleup b_0b_3b_2)}\leq\sqrt{2Z},
%$$ $$
%K\cdot\sum_{j=1}^4 \sqrt{A(T_j)}\leq \sqrt{4\cdot K^2[A(T_1)+A(T_2)+A(T_3)+A(T_4)}]=\sqrt{4K^2(n^2-Z)}.
%$$
%Let $h(Z)=\sqrt{2Z}+\sqrt{4K^2(n^2-Z)}$. Then,
%$
%\sum_{T\in \Tend} \sqrt{A(T)}\leq h(Z).
%$
%Function $h(Z)$ is concave. It reaches its maximum at $Z_0=\frac{n^2}{2K^2+1}$ and $h(Z_0)=n\sqrt{4K^2+2}<11n$.
This completes the proof of Lemma~\ref{lem:sum-of-roots-of-areas}.
\end{proof}


Let $M$ be an input image, $S$ be the set of samples obtained by the algorithm, and $s$ be the parameter in the algorithm.
For any image $M'$, let $d(M')=\dis(M,M')$ and
$\dout(M')=\frac 1 s \cdot |\{u\in S : M[u]\neq M'[u]\}|.$
Also, for any region $R\subseteq\domain$, let $d(M'|_R)=\frac 1 {n^2} \cdot |\{u\in R : M[u]\neq M'[u]\}|$
and $\dout(M'|_R)=\frac 1 s \cdot |\{u\in S\cup R : M[u]\neq M'[u]\}|.$
\fi

\begin{lemma}\label{lem:accuracy-on-ref-polygons}
With probability at least $2/3$ over the choice of the samples taken by Algorithm~\ref{alg:convexity-dist-approximation},
$|\dout(M')-\dis(M,M')|\leq 5\mydelta/6$ for all reference polygons $M'$.
\end{lemma}
\begin{proof}

Consider a region $R=(R_+,R_-),$ partitioned into two regions $R_+$ and $R_-,$ such that in some step of the algorithm we are checking the assumption that $R_+$ is black and $R_-$ is white, i.e., evaluating $\dout_+(R_+)+\dout_-(R_-).$ Let $\stripset$ be the set of all such regions $R$. We will show that with probability at least 2/3, the estimates $\dout_+(R_+)+\dout_-(R_-)$ are accurate on all regions in $\stripset$.

Fix $R=(R_+,R_-)\in\stripset$. Let $\Gamma$ be the set of misclassified pixels in $R$, i.e., pixels in $R_+$ which are white in $M$ and pixels in $R_-$ which are black in $M$. Define $\gamma=|\Gamma|/n^2$. Algorithm~\ref{alg:convexity-dist-approximation} approximates $\gamma$ by $\dout_+(R_+)+\dout_-(R_-)=\frac 1 s |\Gamma\cap S|.$ Equivalently, it uses the estimate $\frac 1 p |\Gamma\cap S|$ for $|\Gamma|$ (recall that $p=s/n^2$). The error of the estimate is $\err(R)=\frac 1 p |\Gamma\cap S|-|\Gamma|$.

\begin{claim}\label{claim:error-for-R}
$\Pr[|\err(R)|> \sqrt\gamma\cdot c\mydelta n^2]\leq 2\exp(-\frac 3 8 c^2\mydelta^2 s)$, where $c=1/21$.
\end{claim}

\begin{proof}
For each pixel $u,$ we define random variables $\chi_u$ and $X_u$,
where $\chi_u$ is the indicator random variable for the event $u\in S$ (i.e., a Bernoulli variable with the probability parameter $p$), whereas $X_u=\frac{\chi_u}p-1$.
Then our estimate of $|\Gamma|$ is $\frac 1 p |\Gamma\cap S|=\frac 1 p\sum_{u\in\Gamma}\chi_u,$ whereas
$\err(R)=\sum_{u\in\Gamma}X_u$. We use Bernstein inequality
\ifnum\full=1
(Theorem~\ref{thm:bernstein})
\else
(stated in the {\color{black} full version} for completeness)
\fi
with parameters
$m=\gamma n^2$ and $z=\sqrt\gamma\cdot c\mydelta n^2$ to bound $\Pr[\sum_{u\in\Gamma}X_u> \sqrt\gamma\cdot c\mydelta n^2]$.
The variables $X_u$ are identically distributed. The maximum value of $|X_u|$ is $a=\frac{1-p}{p}$. Note that
$\E[X_u^2]=\frac 1 {p^2}\E[(\chi_u -p)^2]=\frac 1 {p^2}\Var[\chi_u]=\frac{1-p}{p}=a$.
We assume w.l.o.g.\ that $z<|\Gamma|.$ (If $z\geq |\Gamma|$ then $\sum_{u\in\Gamma}X_u$ can never exceed $z$, and the probability we are bounding is 0.)
%
By Bernstein inequality,
\begin{eqnarray*}
\Pr\left[\sum_{u\in\Gamma}X_u>z\right]&\le& \exp \left(\frac{-z^2/2}{a|\Gamma|+a\cdot z/3}\right)
<\exp\left(-\,\frac 3 8 \cdot \frac{z^2\cdot p}{|\Gamma|}\right)=\exp\left(-\,\frac 3 8 \cdot \frac{\gamma\cdot c^2\mydelta^2n^4}{\gamma n^2}\cdot \frac s {n^2}\right)\\
&=&\exp(-\frac 3 8 c^2\mydelta^2 s).
%= \exp(c^2C\ln\mydelta/4)=\mydelta^{c^2C/4}\le
%\leq \mydelta^k.
\end{eqnarray*}

The second inequality holds because $a< 1/p$ and $z<|\Gamma|$.
The equalities are obtained by substituting the expressions for $z,|\Gamma|,$ and $p$, and simplifying.
By symmetry, $\Pr[|\err(R)|\geq z]\leq 2\exp(-\frac 3 8 c^2\mydelta^2 s)$.
\end{proof}
\ifnum\full=0
The rest of the proof appears in the {\color{black} full version}.
\end{proof}
\else
\begin{claim}\label{claim:convexity-approx-regions-count}
The number of regions in $\stripset$ is at most $50/\bigdelta^8$.
\end{claim}
\begin{proof}
Let $k=1/\bigdelta$. There are four types of regions in $\stripset$, each corresponding to a different call of the form $\dout_+(R_+)+\dout_-(R_-)$ in the algorithm. The first type is a horizontal double strip of the form $R_+=\emptyset$ and $R_-= W_{\ell_0}\cup W_{\ell_2}$. There are ${k+1}\choose 2$ such strips.
%
The second type is where $R_+$ is a black triangle $\bigtriangleup b_0b_1b_2$ (or $\bigtriangleup b_0b_3b_2$) and $R_-$ is a vertical strip $W_{\ell_1}$ (respectively, $W_{\ell_3}$). For each horizontal double strip, there are $2k-1$ vertical strips. For each of them, there are $k$ ways to choose a reference point on the vertical line that delineates the strip. So, overall, there are $(k+1)k(k-1/2)k$ regions of type 2. Type 1 and 2 together have at most $.5k^8$ regions.
%
%$|\stripset|=(k+1)k(k-1/2)+2k-1<.02/\bigdelta^6.$
%
Regions of type 3 are black quadrilaterals of the form $R_+=b'_0b_0''b'b''.$ Each quadrilateral is defined by two reference lines, $b'b_0'$ and $b''b_0'',$ with two reference points on each. There are ${\pi k} \choose 2$ ways to choose reference directions for the two lines. For each of them, there are at most $\sqrt 2 k\cdot {{\sqrt 2 k}\choose 2}$ ways to choose a reference line and two reference points. Overall, the number of quadrilaterals in $\stripset$ is at most $\pi^2 k^8$.
%
Finally, regions of type 4 are contained in triangles of the form $\bigtriangleup v b'_0 b''_0$; they are of the form either $R_+=\emptyset, R_-=\bigtriangleup v b'_0 b''_0$ or $R_+=\bigtriangleup bb'_0b''_0$, $R_-=\bigtriangleup vv'v''$. In the former case, regions are defined by two line-point pairs $(\ell(b'_0,v),b'_0)$ and $(\ell(b''_0,v),b''_0)$. There are ${\pi k} \choose 2$ pairs of reference directions. For each of them, there are at most $\sqrt 2 k$ choices for each reference line and $\sqrt 2 k$ choices for each reference points. In the latter case, they are defined by three reference line-point pairs: $(\ell(b'_0,v),b'_0),(\ell(b''_0,v),b''_0),$ and $(\ell(v',v''),b),$ but the direction of the line through $v'v''$ is determined by $b'_0,b''_0$. As before, there are ${\pi k} \choose 2$ pairs of reference directions. For each of them, there are at most $\sqrt 2 k$ choices for each reference line and $\sqrt 2k$ choices for each reference points. Overall, the number of regions of type 4 is upper-bounded by $4\pi^2 k^8$.
Overall, $|\stripset|\leq (5\pi^2+.5) k^8<50 k^8=50/\bigdelta^8,$ as claimed.
\end{proof}



By taking a union bound over all regions in $\stripset$ and applying Claims~\ref{claim:error-for-R}--\ref{claim:convexity-approx-regions-count}, we get that the probability that for one or more of them the error is larger than stated in Claim~\ref{claim:error-for-R} is at most $|\stripset|\cdot 2\exp(-\frac 3 8 c^2\mydelta^2 s)
\leq\frac{100}{\bigdelta^8}\cdot\exp(-\frac 3 8 c^2\mydelta^2 s)\leq 1/3$,
where the last inequality holds provided that $s\geq C\frac 1{\mydelta^2}\ln\frac 1\mydelta$ for some sufficiently large constant $C$. We get that
\begin{align}\label{eq:low-error-on-all}
\Pr[|\err(R)|\leq \sqrt\gamma\cdot c\mydelta n^2 \text{ for all $R\in\stripset$}]\geq 2/3.
\end{align}


Now suppose that event in (\ref{eq:low-error-on-all}) holds, that is, the error is low for all regions. Fix a reference polygon $M'$. Consider the partition of $M'$ into regions from $R=(R_+,R_-)\in\stripset$ on which Algorithm~\ref{alg:convexity-dist-approximation} evaluates $\dout_+(R_+)+\dout_-(R_-)$ while implicitly computing $\dout(M')$. Let $\stripset_{M'}\subset \stripset$ be the set of regions in the partition. Recall the four types of regions from the proof of Claim~\ref{claim:convexity-approx-regions-count}. Then  $\stripset_{M'}$ contains one region of type 1 and two regions of type 2, defined by the reference box of $M'$. Denote their areas by $A'_1,A'_2,A'_3$. For each triangle $T\in\Tend$ created during the construction of $M'$ in Definition~\ref{def:reference-polygons}, the set $\stripset_{M'}$ contains at most one region of type 3 and at most one region of type 4. They were implicitly colored, respectively, in Item~\ref{item:ref-poly-definition} and Items~\ref{item:ref-poly-definition-tall}-\ref{item:ref-poly-definition-short} of Definition~\ref{def:reference-polygons}, when triangle $T$ was processed. Let $A_T$ and $A'_T$ denote their respective areas.

Recall that $A(R)$ denotes the area of $R$ and that an approximate (but precise enough for asymptotic analysis) upper bound on the number of misclassified pixels in $R$ is $A(R)$. %(see Footnote~\ref{fn:Pick}).
Since the event in (\ref{eq:low-error-on-all}) holds,
$$\err(M')\leq \sum_{R\in\stripset_{M'}}\err(R)
\leq c\mydelta n \sum_{R\in\stripset_{M'}} \sqrt{A(R)}
\leq c\mydelta n \big(\sum_{j=1}^3\sqrt{A'_j}  + \sum_{T\in\Tend}(\sqrt{A_T}+\sqrt{A'_T})\big).
$$
Since $\sum_{j=1}^3A'_j\leq n^2$ and $A_T+A'_T\leq A(T)$ for all $T\in\Tend$,  by concavity of the square root function,
$$\sum_{j=1}^3\sqrt{A'_j}\leq\sqrt{3\sum_{j=1}^3 A'_j}\leq \sqrt{3} n
\text{ and }
\sqrt{A_T}+\sqrt{A'_T}\leq\sqrt{2(A_T+A'_T)}\leq\sqrt{2A(T)}.$$
We substitute these expressions in the previous inequality, use Lemma~\ref{lem:sum-of-roots-of-areas} and recall that $c=1/21$:
$$\err(M')\leq
%c\mydelta n \big(\sum_{t=1}^3\sqrt{A_t}  + \sum_{T\in\Tend}(\sqrt{A_T}+\sqrt{A'_T})\big)
%\leq
c\mydelta n \big(\sqrt{3} n  + \sqrt 2 \sum_{T\in\Tend}\sqrt{A(T)}\big)
\leq
c\mydelta n^2 (\sqrt{3}  + 11\sqrt 2)\leq \frac 5 6 \mydelta n^2.
$$
This holds for all reference polygons $M'$ as long as the event in (\ref{eq:low-error-on-all}) happens, i.e., with probability at least 2/3. This completes the proof of Lemma~\ref{lem:accuracy-on-ref-polygons}.
\end{proof}

For completeness, we state Bernstein's inequality, which was used in the proof of Lemma~\ref{lem:accuracy-on-ref-polygons}.

\begin{theorem}[Bernstein's inequality]\label{thm:bernstein}
 Let $X_1,\dots,X_m$ be $m$ independent zero-mean random variables, where $|X_i|\leq a$ for all $i\in [m]$. Then for all positive $z$,
$$
\Pr\left[\sum_{i = 1}^m X_i > z\right] \le \exp\left(- \frac{z^2/2 }{\sum_{i = 1}^m \E[X_i^2]+a\cdot z/3}\right) .
$$

\end{theorem}



\subsection{Wrapping up: proof of Theorem~\ref{thm:convexity_dist_appr} and corollary on agnostic learning}\label{sec:convexity-dist-approx-wrap-up}
\subparagraph{Analysis of Algorithm~\ref{alg:convexity-dist-approximation}.}
Let $d_M$ be the distance of $M$ to convexity. Then there exists a convex image $M^*$ such that $\dis(M,M^*)=d_M$.
By Lemma~\ref{lem:nearby-reference-polygon}, there is a reference polygon $\hat M$ such that $\dis(M^*,\hat M)\leq \mydelta/6$, and consequently, $d_M\leq\dis(M,\hat M)\leq d_M+\mydelta/6$.
By Lemma~\ref{lem:accuracy-on-ref-polygons},
with probability at least 2/3 over the choice of the samples taken by Algorithm~\ref{alg:convexity-dist-approximation},
$|\dout(M')-\dis(M,M')|\leq 5\mydelta/6$ for all reference polygons $M'$.
%
Suppose this event happened. Then $\dout\geq d_M-5\mydelta/6$ because $\dis(M,M')\geq d_M$ for all convex images $M'$. Moreover,  $\dout(\hat{M})\leq\dis(M,\hat{M})+5\mydelta/6\leq d_M+\mydelta.$ Thus,
$d_M-5\mydelta/6\leq\dout\leq\dout(\hat{M})\leq d_M+\mydelta.$ That is, $|d_M-\dout|\leq \mydelta$ with probability at least 2/3, as required.

\subparagraph{Sample and time complexity of Algorithm~\ref{alg:convexity-dist-approximation}.} The number of samples taken by the algorithm is $s=O(\mydelta^{-2}\log \mydelta^{-1})$.

Next we explain how to implement it to run in time $O(\mydelta^{-8})$. Refer to Figure~\ref{fig:tolerant-reducing-area}.
Each instance triangle $\bigtriangleup b'b''v$ of the dynamic programming in subroutine \Best is specified by two line-point pairs: $(\ell(b',v),b'),(\ell(b'',v),b'')$. The number of line-point pairs is $O(\mydelta^{-3})$ because for each we select
the reference direction, the shift of the line, and the reference point, each
in $O(\mydelta^{-1})$ ways.  Hence, we have $O(\mydelta^{-6})$ entries in the dynamic
programming table for \Best.

In the process of solving an instance of  \Best, we consider $O(\mydelta^{-2})$ possibilities for points $b_0',b_0''$, that is, $O(\mydelta^{-8})$ possibilities over all instances. We show how to evaluate each of the possibilities in amortized time $O(1)$.
For that, we count white and black sample pixels in each sub-area in Figure~\ref{fig:tolerant-reducing-area} in amortized time $O(1)$.

First, we show how to do it for the entire triangle $\bigtriangleup b'b''v$.  We have $O(\mydelta^{-6})$
triangles that can be partitioned into $O(\mydelta^{-5})$ groups by specifying
the first line-point pair $(\ell(b',v),b')$ and the second line (through $b''$ and $v$). That is, within each group, we vary
only point $b''$ on the second line.  We sort all sample points $p\in S$
according to the angle of the segment $pb'$. Similarly, we sort
the reference points $b''$ on the second line according to the angle of the segment $b''b'$.  After sorting, a single scan can establish the counts of white and black pixels in the triangles. Clearly,
we can sort in time $o(\mydelta^{-3})$. Thus, we
compute white/black counts for all instance triangles of \Best in time $o(\mydelta^{-8})$.

When we consider a possibility in \Best, the triangle
$\bigtriangleup b'_0b''_0v$ is also an instance triangle, so we can find the
white/black counts for the quadrilateral $b'b_0'b_0''b''$ by computing the difference between the counts for entire triangle $\bigtriangleup b'b''v$ and triangle $\bigtriangleup b_0'b_0''v$, that is, in time $O(1)$.

When we consider a possibility in subroutine \BestFixed, we need the
counts for the four parts of $\bigtriangleup b'_0b''_0v$. Since we already calculated the counts for $\bigtriangleup b'_0b''_0v$ and because we can perform subtractions, it is
enough to do it for three parts.  Two of them,
$\bigtriangleup b'_0bv'$ and
$\bigtriangleup b''_0bv''$, are instance triangles for \Best, so we already calculated their counts. The third we choose is the triangle $\bigtriangleup v'v''v$.  Note that this triangle is specified by three reference lines, so
there are $O(\mydelta^{-6})$ such triangles. We make a table for all of them.
%
To fill the table, we consider $O(\mydelta^{-5})$ groups:  we group together triangles for which line $\ell$ has
a common direction. By sorting samples in $S$, we can compute the counts for
each group in time $o(\mydelta^{-3})$. Thus, the time for filling the second table is $o(\mydelta^{-8})$. To summarize, Algorithm~\ref{alg:convexity-dist-approximation} runs in time $O(\mydelta^{-8})$. This completes the proof of Theorem~\ref{thm:convexity_dist_appr}.
\end{proof}



\begin{corollary}\label{cor:convexity-agnostic-learner}
The class of convex images is properly agnostically PAC-learnable with sample complexity  $O(\frac{1}{\mydelta^2}\log\frac{1}{\mydelta})$ and time complexity $O(\frac{1}{\mydelta^8})$ under the uniform distribution.
\end{corollary}
\begin{proof}
We can modify Algorithm~\ref{alg:convexity-dist-approximation} to output, along with $\dout$, a reference polygon $\hat{M}$ with $\dout(\hat{M})=\dout$. With an additional DP table, we can compute which points became its vertices. By the analysis of Algorithm~\ref{alg:convexity-dist-approximation}, with probability at least 2/3, the output $\hat{M}$ satisfies $\dis(M,\hat{M})\leq d_M+\mydelta.$
\end{proof}
\fi




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Connectedness Sections
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Distance Approximation to the Nearest Connected Image}\label{sec:connectedness}
To define {\em connectedness}, we consider {\em the  image graph $G_M$} of an image $M$. The vertices of $G_M$ are
$\{(i,j)\mid M[i,j]=1\}$, and two vertices $(i,j)$ and $(i',j')$ are connected by an edge if $|i-i'|+|j-j'|=1$.
In other words, the image
graph consists of black pixels connected by the grid lines. The image is
{\em connected} if its image graph is connected.

\begin{theorem}\label{thm:connectedness_dist_appr}
There is a block-uniform $\mydelta$-additive distance approximation algorithm for connectedness with sample complexity $O(\frac{1}{\mydelta^{4}})$ and running time $\exp\left(O\left(\frac 1 \mydelta \right)\right)$.
\end{theorem}

\ifnum\full=1
\subsection{Border Connectedness}\label{sec:border_connectedness}
\fi

The first idea in our algorithms for connectedness is that we can modify an image
\ifnum\full=1
in a relatively few places by superimposing a grid on it
(as shown in Figures~\ref{fig:Hawaii} and~\ref{fig:Hawaii-grided}),
and as a result obtain an image whose distance to connectedness is determined by the properties of individual squares into which the grid lines partition the image. The squares and the relevant property of the squares  are defined next.
\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-FranzLand.pdf}
\caption{An image $M$.}
\label{fig:Hawaii}
\end{minipage}
\hspace{0.1\linewidth}
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{figure-FranzLand-grided.pdf}
\caption{A gridded image obtained from~$M$.}
\label{fig:Hawaii-grided}
\end{minipage}
\end{figure}
\else
by superimposing a grid on it
(see figures in the {\color{black} full version}),
and as a result obtain a nearby image whose distance to connectedness is determined by the properties of individual squares into which the grid lines partition the image. The squares and the relevant property of the squares  are defined next.
\fi

For a set $S\subset \integerset{n}^2$ and $(i,j)\in \integerset{n}^2$, we define
$S+(i,j)=\{(x+i,y+j):~(x,y)\in S\}$.

\begin{definition}[Squares and grid pixels]\label{def:squares} Fix a side length $n\equiv 1\pmod r$.
For all integers $i,j\in\integerset{n-r}$, where $i$ and $j$ are divisible by $r$, the $(r-1)\times (r-1)$ image that
consists of all pixels in $[r-1]^{2}+(i,j)$ is called an {\em $r$-square} of $M$. The set of all $r$-squares of $M$ is denoted $S_r$.

The pixels that do not lie in any squares of $S_r$, i.e., pixels $(i,j)$ where $i$ or $j$ is divisible by $r,$ are called {\em grid pixels}. The set of all grid pixels is denoted by $\gp_r$.
 \end{definition}

\begin{claim}\label{claim:GP-size}
$|\gp_r|\leq 2n^2/r$.
\end{claim}
\ifnum\full=1
\begin{proof}
$|\gp_r|=2(\frac{n-1}r +1)n-(\frac{n-1}r +1)^2
\leq 2n^2/r$.
\end{proof}
\fi
Note that a square consists of pixels of an \rblock, with the pixels of the first row and column removed. Therefore, a block-uniform algorithm can obtain a uniformly random $r$-square.

Recall the definition of the border of an image from Section~\ref{sec:defintions_notation}.
\begin{definition}[Border connectedness]\label{def:border_connectedness}
A (sub)image $S$ is {\em border-connected} if for every black pixel $(i,j)$ of $S$, the image graph $G_S$ contains a path from $(i,j)$ to a pixel on the border. The property
\emph{border connectedness,} denoted $\C'$, is the set of all border-connected images.
\end{definition}


%In this section, we give an algorithm that approximates the distance of an image to being connected with an additive error. Its performance is summarized in the following theorem.

\ifnum\full=1
\subsection{Proof of Theorem~\ref{thm:connectedness_dist_appr}}\label{sec:proof_of_thm}
\fi
The main idea behind Algorithm~\ref{alg:connectedness}, used to prove Theorem~\ref{thm:connectedness_dist_appr}, is to relate the distance to connectedness to the distance to another property, which we call {\em grid connectedness}. The latter distance is the average over squares of the distances of these squares to {\em border connectedness}. The average can be easily estimated by looking at a sample of the squares.

%We start by giving a high level description of the algorithm (Algorithm~\ref{alg:connectedness}). Given $\mydelta,$ the algorithm that approximates the distance of an image $M$ to connectedness constructs a set  $S_{4/\mydelta}$ of \emph{square subimages} of $M$ and samples $1/\mydelta^2$ subimages from this set uniformly at random. Within each sampled subimage it evaluates the distance to a related property, called \emph{border connectedness}, and outputs the average of computed distances multiplied by $1-\mydelta/4$.
%In the analysis of our algorithm we introduce a new image $M'$ and one more property called \emph{special connectedness}. $M'$ is an image that differs from $M$ only on predefined pixels. We show that the distance of $M'$ to special connectedness and the distance of $M$ to connectedness are close to each other and use this fact to prove the correctness of the algorithm.


W.l.o.g.\ assume that $n \equiv 1 \pmod {4/\mydelta}$. (Otherwise, we can pad the image with white pixels without changing whether it is connected and adjust the accuracy parameter.)

\begin{algorithm}\caption{Distance approximation to connectedness.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\label{alg:connectedness}
\Input{$n\in\mathbb{N}$ and $\mydelta\in(0,1/4)$; block-sample access to an $n\times n$ binary matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl Sample $s= 4/\mydelta^2$ squares uniformly and independently from $S_{4/\mydelta}$ (see Definition~\ref{def:squares}).\;
\tcp{This can be done by drawing random blocks from the $4/\mydelta$-partition of $\domain$.}
\nl\label{step:ave-dist-border-conn} For each such square $S$,
%query all pixels inside $S$ and
compute $\dis(S,\C')$ (see \ifnum\full=1 Section~\ref{sec:border-con}\else the {\color{black} full version}\fi \ for details), where $\C'$ is border connectedness (see Definition~\ref{def:border_connectedness}). Let $\dhatsquares$ be the average of computed distances $\dis(S,\C')$.\;
\nl \Return $\dout = \left((1-\frac \mydelta 4) (1-\frac 1n)\right)^2\cdot\dhatsquares$.
\end{algorithm}

\begin{definition}\label{def:grid_pixels} Fix $\mydelta\in(0,1/4)$. Let image $M_\mydelta$ be a {\em gridded image} obtained from image $M$ as follows:
\ifnum\full=0
\begin{center}
$M_\mydelta[i,j]=
\begin{cases}
1 &\text{ if } (i,j)$ is a grid pixel from $\gp_{4/\mydelta};\\
M[i,j] & \text{ otherwise.}
\end{cases}
$
\end{center}
\else
$$M_\mydelta[i,j]=
\begin{cases}
1 &\text{ if } (i,j)$ is a grid pixel from $\gp_{4/\mydelta};\\
M[i,j] & \text{ otherwise.}
\end{cases}
$$
\fi
%
Let $\C$ be the set of all connected images. For $\mydelta\in(0,1/4),$ define \emph{grid connectedness}
$\C_{\mydelta}=\{ M \mid  M \in\C  \text{, and $M[i,j]=1$ for all $(i,j)\in \gp_{4/\mydelta}$}\}.$
\end{definition}
\begin{lemma}\label{lem:distance_relation}
 Let $d_M=\dis(M,\C)$ and  $d_\mydelta=\dis(M_\mydelta,\C_{\mydelta})$. Then $d_M-\frac{\mydelta}{2}\leq d_\mydelta\leq d_M$. Moreover,
$$d_\mydelta=\Bigl(\bigl(1-\frac \mydelta 4\bigr) \bigl(1-\frac 1n\bigr)\Bigr)^2\cdot\frac 1 {|S_{4/\mydelta}|}\sum_{S\in S_{4/\mydelta}}\dis(S,\C').$$
\end{lemma}
\begin{proof}
First, we prove that $d_\mydelta\leq d_M.$
Let $M'$ be a connected image such that $\dis(M,M')=d_M$. Then $M'_\mydelta$, the gridded image obtained from $M'$, satisfies $\C_{\mydelta}$. Since $\dis(M_\mydelta,M'_\mydelta)\leq d_M$, it follows that $d_\mydelta\leq d_M.$

Now we show that $d_M-\frac{\mydelta}{2}\leq d_\mydelta$. Let $M''_\mydelta\in \C_\mydelta$ be such that $\dis(M_\mydelta,M''_\mydelta)=d_\mydelta$. Then $M''_\mydelta\in \C$ and, by Claim~\ref{claim:GP-size}, $\dis(M,M''_\mydelta)\leq |\gp_{4/\mydelta}|/n^2 +d_\mydelta\leq \mydelta/2+d_\mydelta$, implying $ d_M\leq \mydelta/2+d_\mydelta$, as required.

Finally, observe that to make $M_\mydelta$ satisfy $\C_\mydelta$, it is necessary and sufficient to ensure that each square satisfies $\C'$. In other words,
$$d_\mydelta n^2=\sum_{S\in S_{4/\mydelta}}\Dis(S,\C')= (4/\mydelta-1)^2\sum_{S\in S_{4/\mydelta}}\dis(S,\C').$$
Since $|S_{4/\mydelta}|=(\frac{n-1}{4/\mydelta})^2$, the desired expression for $d_\mydelta$ follows.
\end{proof}

\ifnum\full=1

\subparagraph{Analysis of Algorithm~\ref{alg:connectedness}.}
Let $\dsquares =\frac 1 {|S_{4/\mydelta}|}\sum_{S\in S_{4/\mydelta}}\dis(S,\C')$. Recall that $\dhatsquares$ is the empirical average computed by the algorithm.
By the Chernoff-Hoeffding bound, $\Pr[|\dhatsquares-\dsquares|>\mydelta/2]\leq 2\exp(-2\mydelta^{2}s)\leq 1/3$. So, with probability at least 2/3, we have $|\dhatsquares-\dsquares|\leq \mydelta/2$. If this event happens then
$|\dout-d_\mydelta|\leq \mydelta/2$ because by Algorithm~\ref{alg:connectedness} and Lemma~\ref{lem:distance_relation}, respectively, $\dout=A\cdot\dhatsquares$ and $d_\mydelta= A\cdot\dsquares$, where $A=\left((1-\frac \mydelta 4) (1-\frac 1n)\right)^2 \leq 1$. By Lemma~\ref{lem:distance_relation}, $|d_\mydelta-\eps|\leq \mydelta/2$. Thus,
$|\dout-\eps|
\leq |\dout-d_\mydelta|+ |d_\mydelta-\eps|
\leq \mydelta/2+\mydelta/2=\mydelta$ holds with probability at least 2/3, as required.

\subparagraph{Query and time complexity.}
Algorithm~\ref{alg:connectedness} samples $O(1/\mydelta^2)$ squares containing $O(1/\mydelta^2)$ pixels each. Thus, the sample complexity is $O(1/\mydelta^4)$.

The most expensive step in Algorithm~\ref{alg:connectedness} is Step~\ref{step:ave-dist-border-conn} where the distance of a square $S$ to border connectedness is calculated. By Theorem~\ref{thm:border-con} (see section \ref{sec:border-con}), the running time of this step for one square is $\exp\left(O\left(\frac 1 \mydelta \right)\right)$ and it is called $O(1/\eps^2)$ times. Therefore, the running time of Algorithm~\ref{alg:connectedness} is $\exp\left(O\left(\frac 1 \mydelta \right)\right)$, as claimed.
\else
The rest of the analysis is completed in the {\color{black} full version of this paper} using the Chernoff-Hoeffding bound.
\fi

\subsection{Algorithm for Border Connectedness}
\label{sec:border-con}

\begin{theorem}
\label{thm:border-con}
Let $S$ be a $k\times k$ image. There is an algorithm that computes $\dis(S,\C')$ (i.e., distance of $S$ to border connectedness) in time $\exp \left (O(k)\right)$.
\end{theorem}

\begin{proof}{\color{black}
To prove the theorem we give a dynamic programming algorithm that computes $\dis(S,\C')$ in the following way: starting from row 1 of $S$, it processes a row and proceeds to the next one. The algorithm stops after processing row $k$. The information the algorithm computes and stores for each row is explained later in this section.

\begin{definition}
\label{def:block}
Let $\overline{cl}\in\{0,1\}^k$ be a vector. Call maximal consecutive runs of $1$'s in $\overline{cl}$ {\em 1-blocks} and let $n(\overline{cl})$ denote the number of 1-blocks in $\overline{cl}$. Let $\bold{1}^t$ (respectively, $\bold{0}^t$) denote the string of $t$ ones (respectively, zeros) and let $\Sigma=\{0,1,<,\times,>\}$.
\end{definition}
}

Consider a $k\times k$ image $S$. Recall that $G_{S}$ denotes the image graph of $S$. For every $i\in[k]$, denote the subgraph of $G_{S}$, induced by the first $i$ rows in $S$, by $G^i_{S}$. Index 1-blocks in row $i$ of $S$ in the increasing order of indices of pixels they contain. For example, a row $001110011$ contains two 1-blocks; the 1-block with three $1$'s  has index 1, the 1-block with two $1$'s has index 2. Each 1-block in row $i$ has one of the following 5 statuses w.r.t.\ $G^i_{S}$:
\begin{itemize}
\item{connected to the border of $S$ (denoted by 1);}
\item{isolated, i.e., not connected to the border and to any other 1-block in its row (denoted by 0);}
\item{first 1-block in its connected component, i.e., it is in the connected component with other 1-blocks of row $i$ and has the smallest index among them (denoted by $<$);}
\item{intermediate 1-block in its connected component, i.e., has neither largest nor smallest index in its connected component (denoted by $\times$);}
\item{last 1-block in its connected component, i.e., it is in the connected component with other 1-blocks of row $i$ and has the largest index among them (denoted by $>$).}
\end{itemize}

{\color{black}
\begin{definition}\label{def:config}
Let $\overline{cl}$ denote the coloring of $S$ in row $i$, for some $i\in[k]$ (i.e., $\overline{cl}=S[i]$). Statuses of 1-blocks of $\overline{cl}$ w.r.t. $G^i_S$ are captured by a {\em status vector} $\overline{st}\in\Sigma^{n(\overline{cl})}$. The pair $(\overline{cl},\overline{st})$ is called the {\em configuration w.r.t.\ $G^i_{S}$.}
\end{definition}

\begin{definition}\label{def:bc-sets}
For all $i\in[k]$, $\overline{cl}\in\{0,1\}^k$, and vectors $\overline{st}$ over $\Sigma$ of length at most $k$, define $B(i,\overline{cl},\overline{st})=\{S'\mid S' \text{ is a }k\times k \text{ border-connected image with configuration }(\overline{cl},\overline{st}) \text{ w.r.t.\ } G^i_{S'}\}.$
\end{definition}

For all $i\in[k]$ and $k\times k$ images $S'$, let $cost_i(S,S')$ denote the number of pixels on which the first $i$ rows of $S$ and $S'$ differ. For all $i\in[k], \overline{cl}\in\{0,1\}^k$, and $\overline{st}\in\Sigma^k$ define
$$
{cost}(i,\overline{col},\overline{st})=
\begin{cases}
\min_{S'\in B(i,\overline{cl},\overline{st})}(cost_i(S,S')) & \text{ if } B(i,\overline{col},\overline{st})\neq\emptyset,\\
\infty & \text{ otherwise.}
\end{cases}
$$
Note that the number of all possible configurations for a row is at most $2^k\cdot 5^k=\exp(k)$. We show that if for some $i\in[k-1]$, the value of ${cost}(i,\overline{cl},\overline{st})$ is known for every configuration $(\overline{cl},\overline{st})$ in row $i$, then for every configuration $(\overline{cl'},\overline{st'})$ in row $i+1$, the cost ${cost}(i+1,\overline{cl'},\overline{st'})$ can be computed in time exponential in $k$. This is a crucial ingredient that helps us to show that the running time of our algorithm is exponential in $k$.

For a fixed $i\in[k-1]$, consider an image $S'\in B(i,\overline{cl},\overline{st})$. Let $S''$ be an image which has the same $j\in[i]$ rows as $S'$. Let $\overline{cl'}$ denote the coloring of row $i+1$ in $S''$. If $S''$ is border-connected then configuration $(\overline{cl},\overline{st})$ is {\em consistent} with coloring $\overline{cl'}$, i.e., every 1-block in $\overline{cl}$ that has status other than 1 w.r.t.\ $G^{i}_{S''}$ is connected to a 1-block in $\overline{cl'}$ w.r.t.\ $G^{i+1}_{S''}$. Moreover, for some status vector $\overline{st'}\in\Sigma^{n(\overline{cl'})}$, image $S''\in B(i+1,\overline{cl'},\overline{st'})$ and $\overline{st'}$ can be determined from $\overline{cl},\overline{cl'}$, and $\overline{st}$. Observe that if ${cost}(i,\overline{cl},\overline{st})$ is known for every configuration $(\overline{cl},\overline{st})$, then $cost(i+1,\overline{cl'},\overline{st'})$ can be computed. After computing costs for all configurations in each row, $\dis(S,\C')=\min_{\overline{cl},\overline{st}}cost(k,\overline{cl},\overline{st})$ can be found. In order to find $\overline{st'}$, our algorithm uses subroutine \Compst. \Compst uses subroutine \Constgr that creates a graph whose nodes are 1-blocks of $\overline{cl}$ and edges are defined according to the information provided by $\overline{st}$. Now we explain how $\overline{st'}$ is found. }
%Our algorithm that computes $\dis(S,\C')$ as described and satisfies Theorem~\ref{thm:border-con} is Algorithm~\ref{alg:dist}. In Lemma~\ref{lm:correct}, we show that it correctly computes ${cost}(i,\overline{cl},\overline{st})$ for each $i\in[k]$ and each pair $\{\overline{cl},\overline{st}\}$. The algorithm uses subroutine


Now we show how subroutine \Compst computes $\overline{st'}$ from colorings $\overline{col}$,$\overline{col'}$, and the status vector $\overline{st}\in\Sigma^{num(\overline{col})}$ of $\overline{col}$ w.r.t\ $G^i_{I}$, where $I$ is an image from $B(i,\overline{col},\overline{st})$ for $i\in[k-1]$. Let $n_1=num(\overline{col})$ and $n_2=num(\overline{col'})$. Index 1-blocks in $\overline{col}$ in the nondecreasing order of indices of pixels they contain. Let $I'$ be an image obtained from $I$ by recoloring its row $i+1$ to $\overline{col'}$. Index 1-blocks in $\overline{col'}$ in the nondecreasing order of indices of pixels they contain and add $n_1$ to each index. Consider graph $G=(V,E)$ where $V=[n_1+n_2]$ and $E$ has every edge of the following two types:
\begin{enumerate}
\item edges $(i,j)$, where $i,j\in[n_1]$, $i<j$, and $i$ is not connected to any $j'<j$ in  $G^{i}_{I'}$.
\item $(i,n_1+j)$, where $i\in[n_1], j\in[n_2]$, and $i$ is connected to $n_1+j$ in $G^{i+1}_{I'}$.
\end{enumerate}

\Compst uses subroutine \Constgr to construct graph $G$. (\Constgr computes set $E$.)
After graph $G$ is constructed, \Compst checks whether configuration  $(\overline{col},\overline{st})$ and $\overline{col'}$ are consistent w.r.t.\ $G^{i+1}_{I'}$. If they are not consistent it outputs a $\perp$ symbol. If they are consistent then $B(i+1,\overline{col'},\overline{st'})\neq\emptyset$ (rows $i+1,\ldots, k$ in $I'$ can be recolored to all black rows and the resulting image is in $B(i+1,\overline{col'},\overline{st'})$). \Compst finds vector $\overline{st'}$ based on the connectivity information of graph $G$ and information provided by vector $\overline{st}$.


To check whether $\overline{cl'}$ is consistent with $(\overline{col},\overline{st})$ our algorithm uses subroutine \Compst (Algorithm~\ref{alg:status}). If it is consistent, to
find the status vector $\overline{st'}$. Subroutine \Compst uses subroutine \Constgr that constructs a graph from $\overline{cl}$ and $\overline{st}$ that helps to compute $\overline{st'}$. The nodes in this graph are 1-blocks of $\overline{cl}$ and edges are defined according to the information provided by $\overline{st}$. \Constgr is explained next.

For each $i\in[k]$, every image $S$ has some configuration $(\overline{cl},\overline{st})$ in its $i$'th row w.r.t.\ $G^i_S$. Vector $\overline{st}$ in this  configuration has the information about which 1-blocks in $\overline{cl}$ are in the same connected component in $G^i_S$ and which are connected to the border. Thus, if $(\overline{cl},\overline{st})$ is given we can construct a graph $G$ whose nodes are all 1-blocks of $\overline{cl}$ and the status vector of $\overline{cl}$ w.r.t.\ $G$ is $\overline{st}$. Subroutine \Constgr (Algorithm~\ref{alg:graph}) constructs graph $G$.

\begin{algorithm}\label{alg:graph}
\caption{Subroutine \Constgr used in Algorithm~\ref{alg:status}.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{vector $\overline{cl}\in\{0,1\}^k$, and $\overline{st}\in\Sigma^{n(\overline{cl})}$.}
\DontPrintSemicolon
\BlankLine
\nl Index 1-blocks in $\overline{cl}$ in the nondecreasing order of indices of pixels they contain. \\
\tcp{Let $n_1=num(\overline{cl}), V=[n_1], E=\emptyset,$ and $stack=\emptyset$ (we maintain a stack)}

\nl \ForAll {indices $j=1,2,\ldots,n_1$} {
\nl\textbf{if} $stack\neq\emptyset$ and $\overline{st}[j]=1$ \textbf{then} \Return $\perp$\\
\nl\textbf{if} $stack=\emptyset$ and $\overline{st}[j]\in\{\boldsymbol{\times},\boldsymbol{>}\}$ \textbf{then} \Return $\perp$\\

\nl\textbf{if} $\overline{st}[j]\in\{\boldsymbol{<},\boldsymbol{\times}\}$ \textbf{then} $push(j)$\\
\nl\textbf{if} $\overline{st}[j]=\ \boldsymbol{>}$ \textbf{then} \textbf{do} $p=pop(stack)$; add $\{p,j\}$ to $E$ \textbf{until} $p=\ \boldsymbol{<}$\\
}
\nl \Return $G=(V,E)$\\
\end{algorithm}



\begin{comment}
Let $\overline{col'}$ denote the coloring of row $i+1$ in an image $I\in B(i,\overline{col},\overline{st})$. Then configuration $(\overline{col},\overline{st})$ is {\em consistent} with coloring $\overline{col'}$, i.e., every 1-block in $\overline{col}$ that has status other than 1 is connected to a 1-block in $\overline{col'}$ w.r.t.\ $G^{i+1}_{I}$. Moreover, $\overline{col'}$ has a status vector $\overline{st'}$ w.r.t.\ $G^{i+1}_{I}$ that can be determined from $\overline{col},\overline{col'}$, and $\overline{st}$. Suppose ${cost}(i,\overline{col},\overline{st})$ is known for every configuration $(\overline{col},\overline{st})$. Then if we find status vector $\overline{st'}$ for all colorings $\overline{col'}$ consistent with $(\overline{col},\overline{st})$, we can compute $cost(i+1,\overline{col'},\overline{st'})$. {\color{black}After computing costs for all configurations in each row}, we find $\dis(S,\C')$ which is equal to $\min_{\overline{col},\overline{st}}cost(k,\overline{col},\overline{st})$. Our algorithm that computes $\dis(S,\C')$ as described and satisfies Theorem~\ref{thm:border-con} is Algorithm~\ref{alg:dist}. In Lemma~\ref{lm:correct}, we show that it correctly computes ${cost}(i,\overline{col},\overline{st})$ for each $i\in[k]$. The algorithm uses subroutine \Compst (Algorithm~\ref{alg:conf}, analyzed at the end of this section) to find the status vector $\overline{st'}$ of $\overline{col'}$ w.r.t.\ $G^{i+1}_I$.
\end{comment}
\begin{algorithm}
\caption{Distance to border connectedness of a square $S$.}
\label{alg:dist}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{access to a $k\times k$ square $S$.}
\DontPrintSemicolon
\BlankLine
\nl\label{st:init}\ForAll  {indices $i\in[k]$, vectors $\overline{col}\in\{0,1\}^k$, and $\overline{st}\in \Sigma^{num(\overline{col})}$} \do{
\tcp{For $i\in[k]$, let $\overline{r}_{i}\in\{0,1\}^{k}$ be a vector that corresponds to the $i^{th}$ row of $S$.}
\nl\quad$cost(i,\overline{col}, \overline{st})=
\begin{cases} |\overline{r}_{1}-\overline{col}|_1, & \mbox{if } i=1\mbox{ and }\overline{st}=\bold{1}^{num(\overline{col})};\\
\infty, & \mbox{otherwise.}\end{cases}$\\}

\nl\label{st:subsequent}\ForAll {indices $i=2,3,...,k$, vectors $\overline{col},\overline{col'}\in\{0,1\}^k$ and $\overline{st}\in\Sigma^{num(\overline{col})}$}
   \do{
\nl\quad \textbf{if} $cost(i-1,\overline{col},\overline{st})\neq\infty$ \textbf{then} $\overline{st'}=\Compst(i,\overline{col},\overline{st},\overline{col'})$\\
\nl\quad\textbf{if} $\overline{st'}\neq\perp$ \textbf{then} $cost(i,\overline{col'},\overline{st'})=\min\{cost(i,\overline{col'},\overline{st'}), cost(i-1,\overline{col},\overline{st})+|\overline{r}_{i}-\overline{col'}|_1\}$

}
\nl \label{st:actual-min}\Return $(\min_{\overline{col}\in\{0,1\}^k, \overline{st}\in\Sigma^{num(\overline{col})}}cost(k,\overline{col}, \overline{st}))\cdot k^{-2}$
\end{algorithm}

\subparagraph{Analysis of Algorithm~\ref{alg:dist}.}
The following lemma shows that Algorithm~\ref{alg:dist} is correct.
\begin{lemma}
\label{lm:correct}
For all $i\in[k]$, $\overline{col}\in\{0,1\}^k$, and $\overline{st}\in\Sigma^{k}$, Algorithm~\ref{alg:dist} correctly computes ${cost}(i,\overline{col}, \overline{st})$.
\end{lemma}
\begin{proof} We prove the lemma inductively. For the first row, Algorithm~\ref{alg:dist} indeed computes the cost of every configuration. (Note that every 1-block in the first row is connected to the border and thus, every such 1-block has status $1$. Therefore, $cost(1,\overline{col},\overline{st})=|r_1-\overline{col}|_1$ if $\overline{st}=1^{num(\overline{col})}$, and $cost(1,\overline{col},\overline{st})=\infty$, otherwise). Assume that the statement in the lemma holds for some row $i\in[k-1]$. We prove the statement for row $i+1$. Note that if $B(i+1,\overline{col'},\overline{st'})=\emptyset$ for some $\overline{col'},\overline{st'}$, then $cost(i+1,\overline{col'},\overline{st'})=\infty$. The algorithm correctly sets $cost(i+1,\overline{col'},\overline{st'})$ to $\infty$ and never changes it. If $B(i+1,\overline{col'},\overline{st'})\neq\emptyset$ consider an image $I^*\in B(i+1,\overline{col'},\overline{st'})$ such that $cost(i+1,\overline{col'},\overline{st'})=cost_{i+1}(S,I^*)$. Let $\overline{col}$ be the coloring of row $i$ in $I^*$ and $\overline{st}$ be the status vector of $\overline{col}$ w.r.t.\ $G^i_{I^*}$. Then $\overline{col'}$ and the configuration $(\overline{col},\overline{st})$
are consistent w.r.t. $G^{i+1}_{I^*}$. Note that $I^*\in B(i,\overline{col},\overline{st})$ and $cost_{i+1}(S,I^*)=cost_i(S,I^*)+|r_{i+1}-\overline{col'}|_1$. Moreover, for every image $I_1\in B(i,\overline{col},\overline{st})$, there is an image $I_2\in B(i+1,\overline{col'},\overline{st'})$ such that $cost_i(S,I_1)=cost_i(S,I_2)$. (In $I_2$, recolor row $i+1$ to $\overline{col'}$ and all rows $i+2,\ldots, k$ to all black rows and obtain image $I_2$. In image $I_2$, $\overline{col'}$ and $(\overline{col},\overline{st})$ are consistent w.r.t.\ $G^{i+1}_{I_2}$ and every 1-block in its rows $i+1,\ldots,k$ is border-connected.  Thus, image $I_2$ is border-connected and $I_2\in B(i+1,\overline{col'},\overline{st'})$.) Therefore, $cost_i(S,I^*)=\min_{I\in B(i,\overline{col},\overline{st})}cost_i(S,I)=cost(i,\overline{col},\overline{st})$. At some point, the algorithm considers the configuration $(\overline{col},\overline{st})$ for row $i$ and the coloring $\overline{col'}$ for row $i+1$. By the inductive assumption, the algorithm correctly computes $cost(i,\overline{col},\overline{st})$ which is equal to $cost_i(S,I^*)$. The output of \Compst for the triple $i,\overline{col},\overline{st}$ will be the vector $\overline{st'}$ and the algorithm sets $cost(i+1,\overline{col'},\overline{st'})$ to $cost(i,\overline{col},\overline{st})+|r_{i+1}-\overline{col'}|_1=cost_i(S,I^*)+|r_{i+1}-\overline{col'}|_1$ which is the correct value. This completes the proof.
\end{proof}

By Lemma~\ref{lm:correct}, Algorithm~\ref{alg:dist} computes the cost of every configuration in row $k$. The algorithm outputs the minimum one among these costs. Let $\hat{S}$ be an image such that $\dis(S,\C')=\dis(S,\hat{S})$. Note that configurations of row $k$ that are not possible for a border-connected image have unbounded costs (i.e., $\infty$). Thus, row $k$ in $\hat{S}$ has some configuration which has the minimum cost among all configuration costs for the row. Note that the cost of a configuration in row $k$ is equal to the cost of recoloring of $S$ to some border connected square. Therefore, the output of Algorithm~\ref{alg:dist} is equal to $\dis(S,\C')$.

\begin{algorithm}\label{alg:status}
\caption{Subroutine \Compst used in Algorithm~\ref{alg:dist}.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{index $i$; vectors $\overline{col},\overline{col'}\in\{0,1\}^k$, and $\overline{st}\in\Sigma^{num(\overline{col})}$.}
\DontPrintSemicolon
\BlankLine
\nl Construct graph $G=\Constgr(\overline{col},\overline{col'},\overline{st})$\tcp{Let $G=(V,E)$.}
\nl \textbf{if} $E=\emptyset$ \textbf{then} \Return $\perp$\\
\tcp{Let $n_1=num(\overline{col}), n_2=num(\overline{col'})$}
\nl Let $\overline{col}[0]=\overline{col'}[0]=row_1=row_2=0$\\
\nl For every $j=1,2,\ldots,n_1$\\
\nl\quad \textbf{if} $\overline{col}[j-1]=0$ and $\overline{col}[j]=1$ \textbf{then} increment $row_1$ by 1\\
\nl\quad \textbf{if} $\overline{col'}[j-1]=0$ and $\overline{col'}[j]=1$ \textbf{then} increment $row_2$ by 1\\
\nl\quad \textbf{if} $\overline{col}[j]\cdot \overline{col'}[j]=1$ and $\{row_1,row_2\}\notin E$ \textbf{then} add $\{row_1,row_2\}$ to $E$\\

\nl \textbf{if} $\exists j\in[n_1]$ with $\overline{st}[j]\neq 1$ such that $(j,n_1+j')\notin E$ for all $j'\in[n_2]$ \textbf{then} \Return $\perp$

\nl \textbf{if} $i=k$ \textbf{then} $\overline{st'}=\bold{1}^{n_2}$\\
\nl \textbf{else}\\ %\tcp{Set $\overline{st'}=\bold{0}^{\overline{col'}}$, $n_1=num(\overline{col})$, and $n_2=num(\overline{col'})$}
\nl\quad Let $\overline{st'}=\bold{0}^{n_2}$. Update $\overline{st'}[1]=\overline{col'}[1]$ and $\overline{st'}[n_2]=\overline{col'}[k]$

\nl\quad For each edge $(j,n_1+j')\in E$, $j\in[n_1],j'\in[n_2]$, \textbf{if} $\overline{st}[j]=1$ \textbf{then} $\overline{st}[n_1+j']=1$.

\nl\quad {Run BFS to find connected components in $G$. For each pair $(n_1+j,n_1+j')$, where \\ \quad $j,j'\in[n_2]$, \textbf{if} $j$ and $j'$ are connected and $\overline{st'}[j]=1$ \textbf{then} $\overline{st'}[n_1+j']=1$.}

\nl\quad{For each connected component of vertices $n_1+j$ not marked by 1, where $j\in[n_2]$, update \\ \quad the corresponding entries of $\overline{st'}$ with the corresponding symbols in $\Sigma$ (i.e., $\overline{st'}[j]=\ \boldsymbol{<}$ if it is\\ \quad the vertex with the smallest index in the component, $\overline{st'}[j]=\ \boldsymbol{>}$ if it is the vertex with the \\ \quad largest index in the component, and $\overline{st'}[j]= \boldsymbol{\times}$, otherwise).}

\nl \Return $\overline{st'}$

\end{algorithm}


\subparagraph{Query and Time Complexity of Algorithm~\ref{alg:dist}.}
The most expensive step in Algorithm~\ref{alg:dist} is Step 3. Note that there are at most $k\cdot2^k\cdot5^k$ sets $B(\cdot,\cdot,\cdot)$ for which subroutine \Compst is called in this step. \Compst uses subroutine \Constgr to construct graph $G=(V,E)$. To construct type 1 and type 2 edges in $E$ subroutine \Constgr performs $O(n_1)+O(n_1)=O(k)$ operations. Thus, the running time of \Constgr is $O(k)$ (recall that $n_1=num(\overline{col})$, $n_2=num(\overline{col'})$). Therefore, Steps 1-5 of \Compst run in time $O(k)$. Among the remaining steps (Steps 6-10) of \Compst the most expensive ones are Steps 8 and 9. Each of them runs in time $O(n_1\cdot n_2)=O(k^2)$ time. Thus, the running time of \Compst is $O(k^2)$ and Algorithm~\ref{alg:dist} runs in time $O( k^2\cdot k2^k5^k)=\exp \left (O(k)\right)$, as claimed.
\end{proof}

\bibliographystyle{abbrvnat}%plainnat}
\bibliography{visual-properties}

\iffalse
\section{Property Testers for Connectedness}\label{tester_for_connectedness}
In this section we give two $\eps$-testers
for connectedness of an image: nonadaptive and adaptive. The latter has better
query and time complexity. Both algorithms work as follows: at each step they
partition the image into subimages of the same size, sample one of these
subimages and test it for  border connectedness (see Definition~
\ref{def:border_connectedness}). The nonadaptive algorithm uses subroutine \emph{Exhaustive-Square-Tester}
(Algorithm~\ref{alg:exhaustive_square_tester}) to test for border connectedness, whereas the adaptive algorithm uses \emph{Diagonal-Square-Tester} (Algorithm~\ref{alg:diagonal_square_tester}) for that task.

 \begin{theorem}\label{thm:connectedness_tester}
Given a proximity parameter $\eps\in(0,1)$, connectedness of $n\times n$ images, where  $n>\eps^{-2}\cdot 256$, can be $\eps$-tested nonadaptively and with 1-sided error with query and time complexity $O(\frac{1}{\eps^{2}})$.
It can be $\eps$-tested adaptively and with 1-sided error with query and time complexity $O(\frac{1}{\eps^{3/2}} \sqrt{\log\frac{1}{\eps}})$.
\end{theorem}

Our $\ste$ samples pixels uniformly at random and
then constructs sets of subimages of different sizes, such that subimages of the
same size belong to the same set.
It then samples subimages from each set and within every sampled subimage
it uses one of the two subroutines to test for $\C'$ (border
connectedness). If it finds a subimage that violates $\C'$ and a black
pixel outside that subimage it reports that the image is $\eps$-far from
connectedness. It reports that the image is connected otherwise. For simplicity
of the analysis of the algorithm we assume\footnote {This assumption can be made
w.l.o.g.\ because if $n\in(2^{i-1}+1,2^{i}+1)$ for some $\lind$ , instead of the original image $M$ we can consider a $(2^{i}+1)\times (2^{i}+1)$ image $M'$, which is equal to $M$ on the corresponding coordinates and has white pixels everywhere else. Let
$\eps'=\eps n^{2}/(2^{i}+1)^{2}$.
To $\eps$-test $M$ for connectedness, it suffices to $\eps'$-test $M'$ for connectedness.
%Since $M$ is $\eps$-far from
%connectedness iff $M'$ is $\eps'$-from connectedness, we can
%solve the problem for $M'$ with parameter $\eps'$ and accept $M$ if $M'$ has been accepted and reject %it otherwise.
The resulting tester for $M$ has the desired query complexity because $\eps'=\Theta(\eps)$. If $\eps\in(1/2^{j},1/2^{j-1})$ for
some $j$, to $\eps$-test a property ${\cal P}$, it suffices to run an $\eps''$-test for ${\cal P}$ with  $\eps^{\prime\prime}=1/2^{j}<\eps$.} that $n-1$ and $1/\eps$ are powers of
$2$.

\begin{definition}[Grid pixels and squares of different levels]
\label{def:Grid_pixels_squares_of_different_levels}
For $i\in\integerset{\log\frac{1}{\eps}}$ let $k_{i}=\frac{4}{\eps}\cdot
2^{-i}-1$.
Pixels of the set $G_{i}=\{(x,y)\mid (k_{i}+1)|x$ or $(k_{i}+1)|y\}$ are called
\emph{grid pixels of level $\lind$ .} For all coordinates $u,v$, which are divisible by $r_\lind+1$,
the $k_{i}\times k_{i}$ subimage that consists of pixels $[k_{i}]^{2}+(u,v)$ is
called a \emph{square of level} $\lind$ . The set of all squares of level $\lind$  is denoted $S_{i}$.
{\em Boundary pixels} of a square of level $\lind$  are the pixels of the square which are adjacent to the grid pixels of level $\lind$ . A square of level $\lind$  that violates property $\C'$ (see Definition~\ref{def:border_connectedness}) is called a \emph{witness}.
\end{definition}

\begin{algorithm}\label{alg:connectedness_tester}
\caption{$\ste$ for connectedness.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameter $\eps\in(0,1)$ ; access to a $n\times n$ binary
matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl
Query $\frac{4}{\eps}$ pixels uniformly at random.
\;
\nl For $i=0$ to  $\log\frac{1}{\eps}$

 (a) Sample $2^{i+1}$ squares of level $\lind$  (see Definition~\ref{def:Grid_pixels_and_squares_of_different_levels})
    uniformly at random with replacement.

 (b) For every sampled square $s$ from Step 1a, let
     $[k_{i}]^{2}+(u,v)$ be the set of its pixels.
Run a border-connectedness subroutine (e.g.,
Algorithm~\ref{alg:exhaustive_square_tester} or
Algorithm~\ref{alg:diagonal_square_tester}) with inputs $i,u,v$. If the
subroutine rejects and Step 1 detects a black pixel outside $s$, \reject.
\;
\nl
\Accept.
\;
\end{algorithm}
\begin{algorithm}\label{alg:exhaustive_square_tester}
\caption{Border-connectedness subroutine \emph{Exhaustive-Square-Tester}.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameters $i$, $u$ and $v$; access to
 an $n\times n$ matrix $M$.}
\DontPrintSemicolon
\BlankLine
Let $s$ be a square of level $i$ that consists of pixels $[k_{i}]^{2}+(u,v)$
\;
\nl
 Query all the pixels of $s$.
 \;
\nl
Using breadth-first search (BFS) find all connected components of black pixels
in $s$.
 \;
\nl
 If $s$ violates $\C'$, i.e., if there is a connected component of black
 pixels that does not have a pixel on the border, \reject; otherwise,
 \accept.
 \;
\end{algorithm}
Algorithm~\ref{alg:connectedness_tester} always accepts connected images
since it will see no violation of $\C'$ in Step 1b. Assume that $M$ is an image that is $\eps$-far from connectedness. To prove that the
algorithm rejects $M$ with probability at least $2/3$ and that it has the
desired query and time complexity we use
Lemmas~\ref{lm:sum_of_local_costs} and~\ref{lm:success_probability}. The
main idea behind Lemma~\ref{lm:sum_of_local_costs} is as follows: if $M$ is
$\eps$-far from connectedness there will be enough witnesses (i.e., squares
that violate $\C'$) for Algorithm~\ref{alg:connectedness_tester} to
detect at least one of them in Step 2b. In order to prove this lemma we use Claim~\ref{cl:parent_children_cost_relation} and
Claim~\ref{cl:max_dist_to_border_connectedness}.

\begin{definition}[Local cost and effective local cost]
For a fixed value of $i$ consider a square $s\in S_{i}$.
The \emph{local cost} of $s$ is $\lc(s)=\Dis(s,\C')$. The \emph{effective local cost} of $s$ is
$\elc(s)=\min(2k_{i},\lc(s))$.
\end{definition}
\begin{claim}
\label{cl:parent_children_cost_relation}
For any square $s$ of level $i\in \integerset{\log\frac{1}{\eps}-1}$, let $ch(s)$ denote the set of its $4$ children (i.e.,
squares of level $i+1$ inside it).
Then $\lc(s)\leq \elc(s)+\sum\nolimits_{q\in ch(s)} \lc(q)$.
\end{claim}
\begin{proof}
If $\lc(s)\leq 2k_{i}$ then $\elc(s)=\lc(s)$ and since all costs are nonnegative
the inequality above becomes trivial.

Now assume that $\lc(s)>2k_{i}$. Then $\elc(s)=2k_{i}$. We can modify
$\sum\nolimits_{q\in ch(s)} \lc(q)$ pixels in $s$ such that all its children
satisfy property $\C'$. Then we can make black all pixels of $s$ that
partition it into its children, i.e., pixels $\{(x,y)\mid
x=\frac{k_{i}+1}{2}$ or $y=\frac{k_{i}+1}{2}\}$. There are at most $2k_{i}$ such
pixels and after this modification $s$ will satisfy $\C'$. Hence,
$\lc(s)\leq \elc(s)+\sum\nolimits_{q\in ch(s)} \lc(q)$.
\end{proof}
\begin{claim}
\label{cl:max_dist_to_border_connectedness}
Let $s$ be a $k\times k$ square. Then $\Dis(M,\C')\leq
\frac{k^{2}+3k}{4}$.
\end{claim}
\begin{proof}
 If $M$ contains at most $\frac{k^{2}+3k}{4}$ black pixels, we can make all of them white, i.e.,
 modify less than $\frac{k^{2}+3k}{4}$ pixels, and obtain an image that satisfies $\C'$.
 Assume that there are more than  $\frac{k^{2}+3k}{4}$ black pixels in $M$. We partition all
 pixels of $M$ into $3$ groups such that group $i\in\{0,1,2\}$ contains all pixels $(x,y)$, where $y\equiv i\pmod 3$. Each group has at most $\frac{k^{2}}{3}+k$ elements and making black all the elements of one group produces an image that satisfies $\C'$. By the pigeonhole principle one group has at least $\frac{k^{2}+3k}{12}$ black pixels which means it has at most $\frac{k^{2}}{3}+k-\frac{k^{2}+3k}{12}=\frac{k^{2}+3k}{4}$ white pixels. After making all these white pixels black we obtain an image that satisfies $\C'$ and this completes the proof.
\end{proof}


\begin{lemma}
\label{lm:sum_of_local_costs}
Let $M$ be an $n\times n$ image that is $\eps$-far from $\C$. Then the sum of
effective local costs of squares of all levels inside $M$ is at least $\frac{\eps n^{2}}{2}$.
\end{lemma}
\begin{proof}
We obtain a connected image if we make all the grid pixels of level $0$ black and modify pixels inside every square of $S_{0}$ to satisfy property $\C'$
 (inside every square of that level).
Thus, $\sum\nolimits_{s\in S_{0}} \lc(s)\geq \Dis(M,\C)-\frac{\eps
n^{2}}{2}\geq\frac{\eps n^{2}}{2}$. Thus,
it is enough to show that
$\sum\nolimits_{i=0}^{\log\frac{1}{\eps}}\sum\nolimits_{s\in S_{i}}
\elc(s)\geq\sum\nolimits_{s\in S_{0}} \lc(s)$. Let $s$ be a square of level $i$. We will prove by induction that for any integer $j\in
[i,\log\frac{1}{\eps}-1],$


$$\lc(s)\leq\sum_{h=i}^{j}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,j+1)}\lc(q),$$ where
$desc(s,j)$ denotes the set of all
squares of level $j\geq i$ inside $s$ ($i$-$desc(s)$ contains
only $s$).

For $j=i$ (base case) the statement above is true since it is equivalent to the
statement in Claim~\ref{cl:parent_children_cost_relation}. Assume
that the statement above is true for $j=m$. We will prove its correctness for
$j=m+1$.
By the induction hypothesis $$\lc(s)\leq\sum_{h=i}^{m}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,m+1)}\lc(q).
$$
By Claim~\ref{cl:parent_children_cost_relation}
$$\lc(q)\leq
\elc(q)+\sum\nolimits_{f\in ch(q)}\lc(f).$$ Thus,
$$\sum\nolimits_{q\in
desc(s,m+1)}\lc(q)\leq \sum\nolimits_{q\in
desc(s,m+1)}\elc(q)+\sum\nolimits_{q\in desc(s,m+2)}\lc(q)$$ and
$$\lc(s)\leq\sum_{h=i}^{m}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,m+1)}\lc(q)\leq
$$
$$
\leq
\sum_{h=i}^{m+1}\sum\nolimits_{q\in desc(s,h)}\elc(q)+\sum\nolimits_{q\in
desc(s,m+2)}\lc(q).
$$
We showed that for any square $s$ of level $i$
$$
\lc(s)\leq\sum_{h=i}^{\log \frac{1}{\eps}-1}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,\log\frac{1}{\eps})}\lc(q).
$$
By Claim~\ref{cl:max_dist_to_border_connectedness} in every square of the last
level the local cost is at most $\frac{4^2+3\cdot 4}{4}<2\cdot 4$, i.e., it is equal to the effective local cost of that square. Hence,
$$\lc(s)\leq\sum_{h=i}^{\log \frac{1}{\eps}-1}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in
desc(s,\log\frac{1}{\eps})}\lc(q)=\sum_{h=i}^{\log\frac{1}{\eps}}\sum\nolimits_{q\in desc(s,h)}\elc(q)$$ and
$$\sum\nolimits_{s\in S_{0}}\lc(s)\leq
\sum\nolimits_{s\in
S_{0}}\sum\nolimits_{h=i}^{\log\frac{1}{\eps}}\sum\nolimits_{q\in
desc(s,h)}\elc(q)=\sum\nolimits_{h=i}^{\log\frac{1}{\eps}}\sum\nolimits_{s\in
S_{i}}\elc(s).$$
\end{proof}

\begin{definition}[Diagonal lattice pixels, diamonds and fences]
\label{def:diagonal_lattice_pixels_and_regions}
For a fixed value of $i$ consider a square in $S_{i}$ and let
$m_{i}=\lceil\sqrt{k_{i}/\log k_{i}}\rceil$. \emph{Diagonal lattice pixels} of
the square is the set of pixels $L=\{(x,y)\mid m_{i}|(x+y)$ or $m_{i}|(x-y)\}$. Let
$D$ be a $k_{i}\times k_{i}$ image whose pixels with coordinates from $[k_{i}]^{2}-L$ are black and the remaining pixels are white.
A set of pixels of the square whose corresponding pixels
in $D$ form a connected component is called a \emph{diamond} of the square.
A set of all diagonal lattice pixels that have some neighboring
pixel(s) from a particular diamond is called \emph{fence} of that diamond.
\end{definition}


\begin{algorithm}
\label{alg:diagonal_square_tester}
\caption{Border-connectedness subroutine \emph{Diagonal-Square-Tester}.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameters $k_{i}$, $u$ and $v$; access to
 an $n\times n$ matrix $M$.}
\DontPrintSemicolon
\BlankLine
Let $s$ be a square of level $i$ that consists of pixels $[k_{i}]^{2}+(u,v)$ and
$m_{i}=\lceil\sqrt{k_{i}/\log k_{i}}\rceil$.\;
\nl Query all the pixels from $L$ (see
Definition~\ref{def:diagonal_lattice_pixels_and_regions}) in $s$.\;
\nl
Initialize sets $A$ and $B$. Put all diamonds of $s$ that contain
a border pixel in $B$. Put the remaining diamonds in $B$.
\;
\nl
While $\exists d_{1}\in B$ and $\exists d_{2}\in A$ such that $d_{1}$ and
$d_{2}$ have a common portion on their fences with a black pixel, remove $d_{2}$
from $A$ and put it in $B$\;
  \nl
Query $\frac{1}{2}k_{i}(m_{i}-1)$ pixels in $s$ uniformly at random

  (a) If a black pixel from a region in $A$ is discovered, \reject.

  (b) If a black pixel from a region in $B$ is discovered, let $x\leq \frac{k^{2}}{3}$ be a natural
  number chosen from a distribution whose probability
  density function is $f(j)=\frac{1}{j(j+1)}$, $j\in \mathbb{N}$ (i.e.,
  $Pr(x\geq j)=\frac{1}{j}$).
  Perform a BFS starting from the black pixel.
  If the search is completed within $x$ steps, \reject. Else if $x+1$ black pixels
  were found for this component, stop the search and proceed with the remaining
  queried pixels.
\;
\nl
\Accept.
\end{algorithm}
\begin{lemma}
\label{lm:success_probability}
Fix $i$ and let $s\in S_{i}$ be a witness that consists of pixels
$[k_{i}]^{2}+(u,v)$.
A border-connectedness subroutine of
Algorithm~\ref{alg:connectedness_tester} rejects $s$ with
probability $\geq \frac{\elc(s)\cdot\alpha}{2k_{i}}$, where $\alpha=1$ for \emph{Exhaustive-Square-Tester} and $\alpha=1-e^{-1}$ for \emph{Diagonal-Square-Tester}.
\end{lemma}
\begin{proof}
\emph{Exhaustive-Square-Tester} will determine that $s$ is a witness with
probability $1\geq \frac{\elc(s)}{2k_{i}}\cdot 1$. Now we prove the claim
for \emph{Diagonal-Square-Tester}. Let $a$ denote the number of connected components
in all the regions of the set $A$ (see Steps 2 and 3 of
Algorithm~\ref{alg:diagonal_square_tester}) and $b$ be the number
of black pixels in all the regions of the set $B$ after Step 3 of the subroutine.
The probability that a pixel is selected by the subroutine in Step 4 is
$\frac{k_{i}(m_{i}-1)/2}{k_{i}^{2}}=\frac{m_{i}-1}{2k_{i}}$.
Consider one of the $a$ connected components above and let $p$ be the number of
pixels in it.
The probability that \emph{Diagonal-Square-Tester} finds this component completely equals
$\frac{1}{p}\cdot\frac{m_{i}-1}{2k_{i}}\cdot p$, i.e., one of the $p$ pixels
from this component was selected in Step 4 of the subroutine and $x\geq p$ was
chosen in Step 4b. Each of the $a$ connected components above can be
connected to the diagonal grid pixels by modifying at most $(m_{i}-1)$ pixels
and we can make all the $b$ pixels above white and the square will satisfy
$\C'$. Thus, $a(m_{i}-1)+b\geq \lc(s)\geq \elc(s)$.

The subroutine determines that $s$ is a witness if it finds one of the $a$ connected components or one of the $b$ black pixels above.
Thus, the sum of the probabilities of determining that $s$ is a witness  is
 $\frac{(a+b)(m_{i}-1)}{2k_{i}}\geq\frac{a(m_{i}-1)+b}{2k_{i}}\geq\frac{\elc(s)}{2k_{i}}$.
 Since $1-e^{-x}\geq x(1-e^{-1})$ for $x\in[0,1]$, it follows that the
 probability of determining that $s$ is a witness is at least $1-e^{-\frac{\elc(s)}{2k_{i}}}\geq\frac{\elc(s)(1-e^{-1})}{2k_{i}}$.
\end{proof}


Now we complete the proof of the theorem. For any $i$ there are
$\frac{n^{2}}{k_{i}^{2}}$ squares in $S_{i}$. Let $s$ be a witness in $S_{i}$.
The probability that the algorithm chooses $s$ in Step~1b is
$\frac{k_{i}^{2}}{n^{2}}\cdot 2^{i+1}$.
By Lemma~\ref{lm:success_probability} the probability that the algorithm rejects
$s$ is at least $\alpha\cdot \elc(s)/2k_{i}$. Since at least an $\eps$
fraction of pixels in $M$ are black and any square contains at most
$\frac{16}{\eps^{2}}<\frac{\eps n^{2}}{2}$ pixels, the probability that the
algorithm will detect a black pixel outside $s$ in Step 2 is at least
$1-(1-\frac{\eps}{2})^{\frac{4}{\eps}}>1-e^{-2}$.
Thus, the probability that the algorithm finds a witness of level $i$ in Step 1b
is at least $P_{i}=\frac{2^{i+1}k_{i}\cdot\alpha\cdot
\elc(s)}{2}=\frac{4\cdot \elc(s)\cdot\alpha}{\eps n^{2}}$.
By Lemma~\ref{lm:sum_of_local_costs} $\sum\nolimits_{i\in
\{0\}\cup[\log(1/\eps)]}P_{i}\geq \frac{4\alpha}{\eps n^{2}}\cdot \frac{\eps
n^{2}}{2}=2\alpha$. Therefore, the probability that the algorithm detects at
least one witness of any level $\geq 1-e^{-2\alpha}$, and the probability
that the algorithm rejects $M$ is at least $(1-e^{-2})(1-e^{-2\alpha})\geq 2/3$
(this holds for both values of $\alpha$).


Now we prove that the algorithm has query
complexity $O(\frac{1}{\eps^{2}})$ if it uses \emph{Exhaustive-Square-Tester}
as a subroutine.
The algorithm samples $2^{i+1}$ squares of level
$i\in\{0\}\cup[\log\frac{1}{\eps}]$ and for each sampled square it calls
\emph{Exhaustive-Square-Tester} which makes
$(\frac{4}{\eps}\cdot2^{-i}-1)(\frac{4}{\eps}\cdot2^{-i}-1)<\frac{16}{\eps^{2}2^{2i}}$ queries in each sampled square of level $i$.
Thus, the query complexity of the algorithm is $\sum\nolimits_{i=0}^{\log\frac{1}{\eps}} 2^{i+1}\cdot \frac{16}{\eps^{2}2^{2i}}<\sum\nolimits_{i=0}^{\log\frac{1}{\eps}}\frac{32}{\eps^{2}2^{i}}=O(\frac{1}{\eps^{2}})$.
When the algorithm uses \emph{Diagonal-Square-Tester} it queries
$\frac{2k_{i}^2}{m_{i}}$ inside each square of
level $i$. Then it selects $\frac{k_{i}(m_{i}-1)}{2}$ pixels and a number
$x\leq \frac{k_{i}^{2}}{3}$ such that $\Pr(x\geq j)=1/j$ and then queries at
most $4x$ pixels for each of the selected pixel. Since $\E(x)=O(\log k_{i})$ the
expected number of queries inside a square of level $i$ is at most
$\frac{2k_{i}^2}{F_{i}}+\frac{k_{i}(F_{i}-1)}{2}\cdot 4\log
k_{i}=O(k_{i}^{3/2}\sqrt{\log k_{i}})$. The expected total number of queries is
$\sum\nolimits_{i=0}^{\log(1/\eps)}k_{i}^{3/2}\sqrt{\log
k_{i}}\cdot 2^{i+1}=O(\eps^{-3/2}\sqrt{\log \frac{1}{\eps}})$. The time
complexity of Step 1a and Step 2 of the algorithm is $O(\frac{1}{\eps})$.
Therefore, the total time complexity of the algorithm is
$O(\frac{1}{\eps})$+time complexity of Step 1b. In Step 1b the algorithm
uses either \emph{Exhaustive-Square-Tester} or \emph{Diagonal-Square-Tester}. Both of them perform a breadth first search within each sampled square.
Breadth first search is linear in the sum of the number of edges and the number of nodes of the graph.
Every pixel of a sampled square has at most $4$ neighbouring pixels.
Thus, the number of edges in the image graph of every sampled square is linear in the number of pixels inside it and the time complexity of
Step 1b is linear in the number of all queried pixels, i.e.,
$O(\frac{1}{\eps^{2}})$ for \emph{Exhaustive-Square-Tester} and
$O(\eps^{-3/2}\sqrt{\log (1/\eps)})$ for
\emph{Diagonal-Square-Tester}. This completes the proof of the theorem.
\section{Property Tester for Convexity}\label{sec:convexity-tester}
\begin{theorem}\label{thm:convexity-tester}
Given $\eps\in(0,1/2)$, convexity of $n\times n$ images can be $\eps$-tested
(adaptively) with $O(1/\eps)$ queries and 1-sided error in time
$O(\frac{1}{\eps} \log
\frac{1}{\eps})$.
\end{theorem}
Our $\eps$-tester for convexity (Algorithm~\ref{alg:convexity-tester})
samples pixels uniformly at random and constructs a rectangle $R$ that with high probability contains nearly all black pixels and whose sides include sampled black pixels.
Then it adaptively queries pixels of $R$ in order to partition it into regions $B$, $W$
and $F$. The ``fence'' region $F$ has a small area. If the image is convex, $B$ contains only black pixels and $W$ contains
only white pixels.  The algorithm queries a small number of random pixels in $B\cup W$ and rejects
if it finds a misclassified pixel (i.e., a white pixel in $B$ or
a black pixel in $W$), otherwise it accepts.

Since the number of black pixels outside $R$ and the number of
pixels in $F$ are small, if the image is $\eps$-far from
convexity then there will be enough misclassified pixels in $B\cup W$, and the algorithm
will detect at least one of them with high probability.

\begin{algorithm}\label{alg:convexity-tester}
\caption{$\ste$ for convexity.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameter $\eps\in(0,1)$ ; access to a $n\times n$ binary
matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl\label{step:convexity-init}
Query $\frac{64}{\eps}$ pixels uniformly at random.
%\;
%\nl
If all sampled pixels are white, \accept.
\;
\nl \label{step:convexity-test-construction_of_R}
Let $R$ be the minimum axis-parallel rectangle that contains all sampled black
pixels. Let $p_0$ (resp., $p_1,p_2,p_3$) be a sampled black pixel on the
top (resp., left, bottom, right) side of $R$.
\;
\nl\label{step:convexity-test-walk}
\For {$i=0$ \textbf{ \em{to} } $3$}{
    \nl\label{step:start-walk} Let $(x,y)=p_i$ and $W_i=\emptyset$.\tcp{Investigate the upper right corner
of $R$.}
    \nl \While {$(x,y)$ is in $R$}{
        \nl\lIf{$(x,y)$ is black or below the line through $p_{i}$ and $p_{(i+3)\bmod4}$}
            {$x=x+\left\lceil\eps n/12\right\rceil$.} %Sofya: leaves an extra line for me if you put \; here
        \nl  \lElse{$W_i=W_i\cup\{(x,y)\}$; \ \ $y=y-\left\lceil\eps n/12\right\rceil$.
    }}
    \nl\label{step:finish-walk} Let $W'_i=\{(u,v)\text{ inside $R$} \mid \exists (u',v')\in W_i \text{ such
that } u\geq u',v\geq v' \text{ with respect to}$ the rotated
coordinates$\}.$ Rotate $R$ clockwise by 90 degrees. \tcp{We rotate $R$  to reuse lines \ref{step:start-walk}-\ref{step:finish-walk} of the pseudocode for investigating all four corners.}
}
\nl\label{step:convexity-test-B-and-W}
Let $B$ be the convex hull of all black pixels discovered so far, and
$W=\cup_{i=0}^{3} W_{i}'$.\;
\nl\label{step:misclassified} Query $\frac{8}{\eps}$ pixels in $B\cup W$. If a white pixel in $B$ or a
black pixel in $W$ was detected, \reject; otherwise, \accept.\;
\end{algorithm}

\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{enclosing-box.pdf}
\caption{An illustration to Step~\ref{step:convexity-test-construction_of_R} of Algorithm~\ref{alg:convexity-tester}.}
\label{fig:enclosing-box}
\end{minipage}
\hspace{0.1\linewidth}
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{walk-on-the-box.pdf}
\caption{An illustration to Steps~\ref{step:convexity-test-walk}--\ref{step:convexity-test-B-and-W} of Algorithm~\ref{alg:convexity-tester}.}
\label{fig:walk-on-the-box}
\end{minipage}
\end{figure}

\begin{proof}
We prove that Algorithm~\ref{alg:convexity-tester} satisfies
Theorem~\ref{thm:convexity-tester}. (Some steps of the algorithm are illustrated in Figures~\ref{fig:enclosing-box} and~\ref{fig:walk-on-the-box}).
First, we prove that Algorithm~\ref{alg:convexity-tester} always accepts if its input is a convex image $M$. If $M$ has no black pixels, Step~\ref{step:convexity-init} always accepts. Otherwise, all pixels in $B$ are black by convexity of $M$.
We will show that all pixels in $W$ are
white.
%Let $H$ be the convex hull of $p_0,p_1, p_2$ and $p_3$ and $T$ be the
%upper right corner triangle of the region $R-H$.
For the sake of contradiction, suppose there is a black pixel $b=(x',y')$ in $W_0$. By definition of $W_0$, there is a white pixel $w=(x,y)$ in $W'_0$ such that $x'\geq x$ and $y'\geq y$. Thus, white pixel $w$ is inside the
triangle $p_0 b p_3$, formed by three black pixels, contradicting convexity of $M$. Analogously, there are no black pixels in $W_1,W_2$ and $W_3$. Since there are no white pixels in $B$ and no black pixels in $W=\cup_{i=0}^{3} W'_i$,
Step~\ref{step:misclassified} of Algorithm~\ref{alg:convexity-tester} always $M$.

Now assume that $M$ is $\eps$-far from convexity. First, we prove the two
lemmas below:

\begin{lemma}\label{lem:black-pixels-outside-R}
The probability that there are more than $\frac{\eps n^2}4$ black pixels outside
$R$ after Step~\ref{step:convexity-test-construction_of_R} of Algorithm~\ref{alg:convexity-tester}
is at most $1/9$.
\end{lemma}
\begin{proof}
Let $L$ be a horizontal line with the largest $y$-coordinate such that the image
$M$ contains at least $\frac{\eps n^2}{16}$ black pixels on or above $L$. The
probability that none of these pixels are sampled in Step~1 of Algorithm~\ref{alg:convexity-tester}
(and, consequently $R$ lies below $L$) is at most
$(1-\frac{\eps}{16})^{64/\eps}\leq e^{-4}<1/36$. Thus, the probability that
there are more than $\frac{\eps n^2}{16}$ of black pixels in the half-plane
above $R$ is at most $1/36$. The same bound holds for the half-planes to the left, to the right and below $R$.
By a union bound the probability that there are more than $\frac{\eps
n^2}{16}\cdot 4=\frac{\eps n^2}{4}$ black pixels outside $R$ is at most
$(1/36)\cdot 4=1/9$.
\end{proof}
\begin{lemma}\label{lem:total_number_of_pixels_in_F}
Let $F=R-(B\cup W)$. Then $F$ contains at most $\frac{\eps n^{2}}{2}$ pixels.
\begin{proof}
Let $m=\lceil\eps n/12\rceil$ and $(x_i,y_i)=p_i$ (see Step~\ref{step:convexity-test-construction_of_R} of
Algorithm~\ref{alg:convexity-tester}) for $i\in\{0\}\cup[3]$.
Call a subimage that consists of pixels $(x,y)+[m]^{2}$, where $m|(x-x_i+1)$ and
$m|(y-y_i+1)$, a \emph{square}. Call squares that contain pixels from $F$
\emph{fence squares}. Let $q=(x_3,y_0)$ be the third vertex of the triangle T.
We will find an upper bound on the number of fence squares inside $T$.
Each pixel that Algorithm~\ref{alg:convexity-tester}
queries in Step 5 discovers at most one (new) square in $T$. The
number of fence squares is at most the number of all discovered squares in the
triangle. The algorithm queries at most $\frac{x_3-x_0+y_0-y_3}{\eps n/12}+2$
pixels in the triangle (thus, it discovers at most that many squares), since every time it either increases the $x$-coordinate or decreases the $y$-coordinate of the queried pixel.
Therefore, there are at most $\frac{x_3-x_0+y_0-y_3}{\eps n/12}+2$
fence squares in this triangle. Similarly, we can
find an upper bound on the number of discovered squares in the remaining
triangles. Since the perimeter of $R$ is at most $4n$, the sum of the upper bounds is at most
$\frac{4n}{\eps n/12}+8=\frac{48}{\eps}+8\leq \frac{56}{\eps}$.
The number of pixels from $F$ in a single
fence square is at most $(\frac{\eps n}{12})^{2}=\frac{\eps^{2} n^{2}}{144}$ and
the total number of pixels from $F$ in all
fence squares is at most $\frac{(\eps n)^{2}}{144}\cdot
\frac{56}{\eps}\leq\frac{\eps n^{2}}{2}$.
\end{proof}
\end{lemma}

We call a pixel {\em misclassified} if it is black and is in $W$ or if it is white and in $B$.
If we make all pixels in $B$ black and all pixels outside of $B$ white, we obtain a
convex image. Thus, by Lemma~\ref{lem:total_number_of_pixels_in_F},
$B\cup W$ contains at least $\frac{\eps n^{2}}{4}$ misclassified pixels if there are
at most $\frac{\eps n^{2}}{4}$ black pixels outside of $R$. If the latter is the
case, the probability that the algorithm will not detect a violated pixel
is at most $(1-\frac{\eps}{4})^{\frac{8}{\eps}}<e^{-2}<2/9$. By
Lemma~\ref{lem:black-pixels-outside-R} the probability that $B\cup W$
contains less than $\frac{\eps n^{2}}{4}$ misclassified pixels is at most
$1/9$.
Therefore, the probability Algorithm~\ref{alg:convexity-tester} accepts is at most
$2/9+1/9=1/3$, as desired.
\subparagraph{Query complexity.} The algorithm queries pixels in Steps 1,5 and 9.
In Steps 1 and 9, the algorithm makes $O(\frac{1}{\eps})$ queries. As we mentioned earlier, the
algorithm queries $O(\frac{1}{\eps})$ pixels in Step~5. Thus, the overall query
complexity of the algorithm is $O(\frac{1}{\eps})$.

\subparagraph{Running time.} The running time of the algorithm in Steps 1 through
7 and Step 9 is $O(\frac{1}{\eps})$. In Step 8, one can
obtain the convex hull of $B$ represented by a set of
$O(\frac{1}{\eps})$ points lexicographically sorted by their coordinates
in time $O(\frac{1}{\eps}\log \frac{1}{\eps})$. In Step 10, $W$ is represented
by at most 4 sets of $O(\frac{1}{\eps})$ points. In each set points are sorted
by their $y$-coordinates (either in decreasing or increasing order) and by
their $x$-coordinates (either in decreasing or increasing order).
We need to check whether a point is inside $B$ or $W$ in this step. For a single point we can do
this in time $O(\log \frac{1}{\eps})$ by a
binary search. Since we query $O(\frac{1}{\eps})$ points the running
time of Step 10 is $O(\frac{1}{\eps}\log \frac{1}{\eps})$. Therefore, the running time
of the algorithm is $O(\frac{1}{\eps})+O(\frac{1}{\eps}\log \frac{1}{\eps})=O(\frac{1}{\eps}\log \frac{1}{\eps})$.
\end{proof}
\begin{theorem}\label{thm:border-con}
The distance of a $k\times k$ image $S$ to border connectedness can be computed
in time $O(9^k)$.
\end{theorem}
\begin{proof}
\newcommand{\cG}{{\mathcal G}}
\newcommand{\col}{\chi}
\newcommand{\cc}{CC-partition}
To prove the theorem, we reduce the computation of the distance of $S$ to border connectedness (see Definition~\ref{def:border_connectedness}), to the computation of a shortest path in a directed acyclic graph (DAG). More precisely, we construct a DAG $\cG_k$ with two special nodes $s$ and $t$ such that there is a bijection between paths from $s$ to $t$ and $k\times k$ border-connected images. In addition to nodes $s$ and $t$, graph $\cG_k$ will have at most $k4^k$ other (non-special) nodes. The out-degree of every node in $\cG_k$ will be at most $2^k$. We also define a node cost function $\kappa$ such that for
every $s$-$t$ path $P$ in $\cG_k$, there is a border connected image $S_P$ with $\sum_{u\in P}\kappa(u)=\dis(S,S_P)\cdot k^2$. In graph $\cG_k$, the cost of the shortest path from $s$ to $t$ is equal to $\dis(S,\C')$ (recall that $\C'$ denotes border connectedness). Our algorithm for computing $\dis(S,\C')$ is Algorithm~\ref{alg:bord-con} which relies on the construction of $\cG_k$.

We give an intuition behind the graph $\cG_k$. Consider the following recoloring process of $S$: Starting from the first row we recolor the current row in $S$ and proceed to the next row. For every $i\in[k]$, let $S^i$ denote the image that we obtain after recoloring row $i$. If the subimage of $S^i$, induced by its first $i$ rows, can be extended to a border-connected image, by appropriately recoloring the remaining rows of $S^i$, we say that $S^i$ is {\em BC-extendable}. Observe that $S^i$ is BC-extendable for all rows $i\in[k]$ iff the final image $S^k$ is border-connected. We explain how a border-connected image corresponds to an $s$-$t$ path in $\cG_k$ in more details. The graph $\cG_k$ is a layered graph with $k+2$ layers of nodes and $k+1$ layers of edges. Nodes $s$ and $t$ are in layers $0$ and $k+1$, respectively. All the remaining nodes of $\cG_k$ are in layers $1,2,\ldots,k$. For every row $i\in[k]$ of a $k\times k$ image $S'$, there is a corresponding node $u_i$ in layer $i$ of $\cG_k$. Directed edges are of the form $(s,u_1)$ (edges in layer 0), $(u_k,t)$ (edges in layer $k$), and $(u_i,u_{i+1})$ (edges in layer $i$), for $i\in[k-1]$. Moreover, $S'$ is border-connected iff the sequence $(s,u_1,u_2,\ldots,u_k,t)$ forms a path in $\cG_k$.

Now we explain the construction of $\cG_k$. For every $i\in[k]$, consider the image graph $G_{S^i}$ of $S^i$. We obtain a modified (undirected) image graph $G'_{S^i}$ from $G_{S^i}$ by the addition of a new node $\Out$ is adjacent to every node $(i,j)$ of $G_{S^i}$ such that $\{i,j\}\cap\{1,k\}\not=\emptyset$. Note that $S^k$ is border-connected iff the graph $G'_{S^k}$ is connected. Let $G_i$ denote the subgraph of $G'_{S^i}$ induced by its nodes in the set $([i]\times[k])\cup\{\Out\}$. Let $\col\subseteq\{i\}\times[k]$ denote the set of black pixels in row $i$ of $S^i$. Set $\col$ is a {\em coloring} of row $i$ in $S^i$ ($\col$ shows how each pixel of row $i$ is colored). Consider the partition of the set $\{Out\}\cup\col$ that corresponds to the connected components of $G_i$. Call this partition a {\em connected components partition (\cc)} of $\{Out\}\cup\col$. For each $i\in[k]$, we define the set of non-special nodes of layer $i$ in $\cG_k$. These nodes are triples of the form $(i,\col,\pi)$, where
\begin{itemize}
\item
$i\in[k]$ is a {\em row number};
\item
$\col\subseteq \{i\}\times[k]$ is a coloring of row $i$;
\item
$\pi$ encodes the \cc\ of $\{\Out\}\cup\col$. We describe $\pi$ in more details later.
\end{itemize}

The cost of node $(i,\col,\pi)$ is $\kappa(i,\col,\pi)=|\{j\in[k]:~(S[i,j]=0\Leftrightarrow(i,j)\in\col) \text{ is true}\}|$, whereas
$\kappa(s)=\kappa(t)=0$.
%\text{ and }(i,j)\in\col \text{ or }S[i,j]=1\text{ and }(i,j)\notin\col

Recall that $\col$ is the coloring of row $i$ in $S^i$ and $\pi$ encodes the \cc\ of $\{Out\}\cup\col$. Let $\col'\subseteq\{i+1\}\times[k]$ be the coloring of row $i+1$ in $S^{i+1}$ and let $\pi'$ be the encoding of the \cc\ of $\{Out\}\cup\col'$. If both $S^i$ and $S^{i+1}$ are BC-extendable then the pair of nodes $\{(i,\col,\pi),(i+1,\col',\pi')\}$ is {\em good} and $\col'$ is {\em consistent} with $\col$. To ensure a bijection between the set of $k\times k$ images and the set of $s$-$t$ paths in $\cG_k$, we only create edges for pairs of nodes in $\cG_k$ that are good. A key observation is that $\col,\col'$, and the \cc\ of $\{Out\}\cup\col$ define the \cc\ of $\{Out\}\cup\col'$. Thus, for every node $(i,\col,\pi)$ in layer $i\in[k-1]$, we can consider all colorings $\col'$, that are consistent with $\col$, and find $\pi'$ such that the pair $\{(i,\col,\pi),(i+1,\col,\pi')\}$ is good. Therefore, we can create all the edges of layer $i$. Note that for every coloring $\col_1$ of the first row, the \cc\ of $\{\Out\}\cup\col_1$ contains only the set $\{\Out\}\cup\col_1$. The encoding of such \cc\ is $\bf 1^{n(1,\col)}$. We construct the edges of $\cG_k$, layer by layer, starting from layer 1. When we process a node $(i,\col,\pi)$ in layer $i\in[k-1]$, we use subroutine \Compart in order to check whether a coloring $\col'\subseteq\{i+1\}\times[k]$ is consistent with $\col$. This is done by checking whether every node in $\col$ is connected either to $Out$ or to a node in $\col'$ in the graph $G_{i+1}$. If $\col$ and $\col'$ are consistent, the subroutine returns $\pi'$, the encoding of the \cc\ of $\{Out\}\cup\col'$. If they are not consistent, it returns the $\perp$ symbol (i.e., edge is not created). We analyze subroutine \Compart later. After some preliminary discussion, we define directed edges of $\cG_k$. There are three types of edges in $\cG_k$:
\begin{itemize}
\item
edges $(s,(1,\col,\pi))$, for every $(1,\col,\pi)$ (edges of layer 0);
\item
edges $((k,\col,\pi),t)$, for every $(k,\col,\pi)$ (edges of layer $k$);
\item
edges $((i,\col,\pi),(i+1,\col', \Compart(\col,\col',\pi)))$, for every $i\in[k-1]$ (edges of layer $i$).
\end{itemize}

Observe that, indeed, every $k\times k$ image $S'$ has a corresponding sequence of nodes $(s,u_1,\ldots,u_k,t)$, where $u_i=(i,\col_i,\pi_i)$ is a node in layer $i$. The way we created edges assures that this sequence of nodes is a path iff $S'$ is border-connected. Moreover, the sum $\sum_{i=1}^k\kappa(u_j)=\dis(S,{S'})$.

Now describe the encoding $\pi$ of a \cc\ .
\begin{definition}\label{def:block}
For $i\in[k]$, let $\col$ be the coloring of row $i$ in $S^i$. Define graph $G^{\col}_i$ as the subgraph of $G_i$ induced by the nodes in $\col$. Call every connected component in $G^{\col}_i$ {\em block}. Let $n(i,\col)$ denote the number of blocks in $G^{\col}_i$.
\end{definition}
\begin{claim}\label{cl:part}
For $i\in[k]$, let $\col$ be the coloring of row $i$ in $S^i$. Then every possible \cc\ of $\{\Out\}\cup\col$ can be encoded as a binary string of length at most $k$.
\end{claim}

Assume that Claim~\ref{cl:part} holds (we give its proof later) and that \Compart works correctly, we are ready to give the algorithm that compute the distance to border connectedness of the image $S$ (Algorithm~\ref{alg:bord-con}).

\begin{algorithm}
\caption{Computing the distance to border connectedness.}
\label{alg:bord-con}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{a $k\times k$ image $S$.}
\DontPrintSemicolon
\BlankLine
\tcp{Construct graph $\cG_k=(V,E)$, where $V=\cup^{k+1}_{i=0}V_i$ and $E=\cup^{k}_{i=0}E_i$.
Initially $V_0=\{s\}$, $V_{k+1}=\{t\}$, $E_0=\emptyset$, and $V_i=E_i=\emptyset$, for all $i\in[k]$.}

\nl $\kappa(s)=\kappa(t)=0$\ \tcp{$\kappa$ is the cost function of a node in $\cG_k$}
\nl \ForAll {sets $\col\subseteq\{1\}\times[k]$ and strings $\pi=\bf{1}^{n(1,\col)}$}
 \do{\nl\quad Put node $(1,\col,\pi)$ in $V_1$ and edge $(s,(1,\col,\pi))$ in $E_0$\\
       \tcp{and compute the cost of node $(1,\col,\pi)$}
       \nl\quad $\kappa(1,\col,\pi)=|\{j\in[k]:~(S[1,j]=0\Leftrightarrow(1,j)\in\col) \text{ is true}\}|$\\

 }
\nl \ForAll {$i\in[k-1]$, $\col\subseteq \{i\}\times[k]$, $\col'\subseteq \{i+1\}\times[k]$, and $\pi\in\{0,1\}^{n(i,\col)}$}
   \do {\nl\quad $\pi'=\Compart(\col,\col'\pi)$\\
          \nl\quad\textbf{if} $\pi'\neq\perp$ \textbf{then}\\
          \nl\quad\quad put $(i+1,\col', \pi')$ in $V_{i+1}$ and $((i,\col,\pi),(i+1,\col', \pi'))$ in $E_i$\\
           \tcp{and compute the cost of node $(i+1,\col',\pi')$}
           \nl\quad\quad $\kappa(i+1,\col',\pi')=|\{j\in[k]:~(S[i+1,j]=0\Leftrightarrow(i+1,j)\in\col) \text{ is true}\}|$\\
}
\nl \ForAll {sets $\col\subseteq\{k\}\times[k]$ and strings $\pi\subseteq\{0,1\}^{n(k,\col)}$}
\do{\nl\quad Put $((k,\col,\pi),t)$ in $E_k$\\}
\nl Run Dijkstra's algorithm to find the cost of the shortest path from $s$ to $t$ in $\cG_k$ and output that cost divided by $k^2$.\\
\end{algorithm}

\begin{algorithm}
\caption{Subroutine \Compart.}
\label{alg:encode}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{row number $i\in[k]$, sets $\col\subseteq \{i\}\times[k]$, $\col'\subseteq \{i+1\}\times[k]$, and $\pi\in\{0,1\}^{n(i,\col)}$ .}
\DontPrintSemicolon
\BlankLine

\end{algorithm}






For $i\in[k]$, consider a connectivity partition $\pi_i$. Recall the graph $G^i_{S^i}$. Then nodes $v$ and $v'$ of $G^i_{S^i}$, that correspond to some black pixels in row $i$ of $S^i$, are in the same part of $\pi_i$ iff they are in the same connected component of $G^i_{S^i}$. To count all possible connectivity partitions $\pi_i$ for node $u_i$ of some $s$-$t$ path, we observe that each such partition can be described as connected components of an outer-planar graph $G_{\pi_i}$ that we define next:
The nodes of $G_{\pi_i}$ are $\{\Out\}\cup\chi$ and the edges are formed by the following rules:
\begin{enumerate}
\item for all $j\in[k]\cup\{0\}$, if $(i,j)$ and $(i,j+1)$ are both in $\chi$ then there is an edge between them in $G_{\pi_i}$, where $(i,k+1)=(i,0)=Out$.
\item for all $j_1,j_2\in[k]$, there is an edge between $(i,j_1)$ and $(i,j_2)$ in $G_{\pi_i}$ if the nodes are in the same connected component in $G^i_{S^i}$, where $j_1<j_2$. Moreover, for any $j_3$, such that $j_1<j_3<j_2$ nodes $(i,j_1)$ and $(i,j_3)$ are not in the same connected component in $G^i_{S^i}$.

Observe that graph $G_{\pi_i}$ is outer-planar.


$(i,j_1)$ and $(i,j_3)$ are in the same component in $G^i_{S^i}$, whereas $(i,j_1)$ and $(i,j_3)$
\end{enumerate}
cycle edges that form the cycle $(\Out,(i,1),\ldots,(i,k))$ and
$S'$-{\it connections} which are
pairs $\{v,v'\}$ such that in $G^i_{S'}$ there is a path from $v$ to $v'$.
To assure that $G$ is planar we will properly select $S'$-connections
that span a connected component, so they never form
"crossing pairs" of $S'$-connections of the form
$\{(i,j_0),(i,j_2)\}$ and
$\{(i,j_1),(i,j_3)\}$ where $j_0<j_1<j_2<j_3$.  For example, we can pick
a representative of a connected component and use connections of every
other member to the representative.
Note that if we have such a "crossing pair", the four nodes in this edge
pair are in the same component because these two edges correspond to
paths in $G^i_{S'}$ that have a node in common.

There are $k$ row numbers and $2^k$ possible colorings $\chi$. It remains to count all possible partitions $\pi_i$ for node $u_i$ of some sequence



This graph has these types of edges:
(a) $\{\Out,(i+1,j)$ such that $j\in\{1,k\}$ and $(i+1,j)\in\sigma'$, (b)
$e=\{(i,j),(i+1,j)\}$ such that $e\subseteq \sigma\cup\sigma'$,
(c) $\{\Out,(i,j)\}$
such that $Out$ and $j$ are in the same part of $\pi$, (d) $\{(i,j),(i,j')\}$
such that $j$ and $j'$ are in the same part of $\pi$.  Then partition $\pi'$
of $Out,1,\ldots,k$ must
correspond to the partition of $\Out,(i+1,1),\ldots,(i+1,k)$ that is induced by
the connected components of $G_{i,\sigma,\sigma'}$. We add a condition on $\sigma'$ to enforce that paths correspond to border
connected sets.  In the graph $G_{i,\sigma,\sigma'}$, every $(i,j)\in
\sigma$ must be in the same connected component either with $\Out$ or with
a node from $\sigma'$. In the case of edge $(s,(1,\sigma,\pi))$, partition $\pi$ has one set that
contains $Out$ and every $j$ such that $\sigma(j)=1$. Finally, edges $((k,\sigma,\pi),t)$ have
no restriction. Note that $G_{i,\sigma,\sigma'}$ can be constructed in time $O(k)$.

Now it remains to verify the size of $\cG_k$.  The number of possible values
of $\sigma$ is clearly $2^k$.  In directed edges $(s,(1,\sigma,\pi))$ and
$((i,\sigma,\pi),(i+1,\sigma',\pi')$ the partition $\pi$ is determined, hence
each node of $\cG_k$ has at most $2^k$ out-going edges.  It remains to count
the number of possible partitions $\pi$ for a node of the form $(i,\sigma,\pi)$.

We observe that those partitions can be described as connected components
in an outer-planar graph with $k'\le\lceil k/2\rceil$ nodes in which we
remove the edges of the outer face.  The lemma below shows that there
are at most $2^k$ such partitions, which concludes the proof of the theorem.

% Only $0$ and $j$'s such that $\sigma(j)=1$ can belong to non-singleton parts.
% Moreover, if we take into account the connections that are forced by $\sigma$,
% we have some $k'\le\lceil k/2\rceil$ parts, so we need to consider the number
% of ways that $k'$ parts can be connected into larger parts with an
% outer-planar graph.  Thus to conclude the proof, it suffices to show
% that any such set of connections can be
% encoded with $2k'-2\le k$ bits.

\begin{lemma} Consider outer-planar graphs with node set $[{k'}]$ and with the
outer face being the cycle $(1,2,\ldots,{k'})$.  There are at most $2^{2{k'}-2}$
distinct partitions of the nodes of those graphs into connected components
made by the edges that are not on the outer face.\end{lemma}

\begin{proof}
For every node $i$ we define two bits: $f_i=1$ if this node is the first one
(has the minimal number) in its component, and $\ell_i=1$ if this node is the
last one in its component.  Note that $f_1=\ell_{k'}=1$.  We can use those bits
and a stack to determine the partition.  The stack contains representatives of
the parts that contain at least one node that was not examined yet.  We process
bits in order $f_1,\ell_1,f_2,\ldots,f_{k'},\ell_{k'}$; if $f_i=1$ we push $i$ onto
the stack, otherwise we include it in the same component as the top of the
stac{k'}; if $\ell_i=1$ we pop the stack.  Because we cannot pop empty stac{k'} this
clearly imposes further limitation on the encoding, for example, $f_{k'}=0$ iff
the stack is empty after processing of $\ell_{{k'}-1}$.
\end{proof}



{\bf Analysis of Algorithm~\ref{alg:bord-con}}. There are $k$ rows and the number of all possible colorings is $2^k$. By Claim~\ref{cl:part}, there are at most $2^k$ encodings for a coloring of a row. Thus, the number of nodes in $\cG_k$ is at most $k\cdot4^k$. Each node has out-degree at most $2^k$ and thus, the number of edges in $\cG_k$ is at most $k\cdot8^k$. Construction of $\cG_k$ is done in $O(k^28^k)$ time. Since $\cG_k$ is a DAG on at most $k4^k$ nodes and at most $k8^k$ edges the running time of the algorithm is $O(k^28^k)+O(k4^k+k8^k)=O(9^k)$, as claimed.
\end{proof}



\fi


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Commented out unfinished section with improved dist approx to connectedness
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\subsection{Improved Approximation for Distance to Connectedness}\label{sec:improved-approximation-for-connectedness}
\begin{theorem}
Fix parameters $\alpha\in(0,1/2)$ and $\mydelta>0$. There exists an algorithm ...
with query complexity $O(\frac{1}{\alpha^{2}\mydelta^{2}})$.
\end{theorem}
At a high level, the algorithm partitions the image into smaller images of size $\frac{4}{\alpha\mydelta}\times\frac{4}{\alpha\mydelta}$ and samples $c$ of them uniformly at random. Then the algorithm proceeds as the following: at each level $i=1,2,3,...,\log\frac{1}{8\mydelta}$ the algorithm partitions each square image of the previous level ($i-1$) into four equal sub-squares of the current level ($i$) and samples $c\cdot2^{i}$ of all squares of the current level uniformly at random. For each sampled image the algorithm evaluates the \emph{net-cost}. Based on the net-cost and a \emph{threshold value} that is evaluated at each level the algorithm computes the \emph{reported-cost} of each sampled square and takes the average. Both the net-cost and reported-cost of the sampled image are evaluated recursively from bottom to up by considering all the images in it starting from the smallest ones. The algorithm outputs the sum of all values(averages) that were computed at each level.

To compute the net-cost and reported-cost of a square we use a black box that takes   image, \emph{super pixels} and \emph{super pixels' cost} of the image as an input and outputs the distance to property $C'$. To evaluate the net-cost of each smallest square the black box takes only the square as an input. The reported-cost of each such square is $0$ if its net-cost$ < \frac{2f}{\alpha}$, where $f$ is the perimeter of the image, and it is equal to the net-cost otherwise.
%For squares at level $i=\log\frac{1}{8\mydelta}-1,...,2,1$
\fi

\begin{comment}
\subsection{Tester for Connectedness}\label{sec:connectedness-tester}
\begin{theorem}\label{thm:connectedness_tester}
There is a block-uniform (1-sided error) $\eps$-tester for connectedness with sample and time complexity $O(\frac{1}{\eps^{2}})$.
\end{theorem}
\begin{proof}
Observe that a tester can safely reject if it finds a small connected component and a black pixel outside it.
Our tester (Algorithm~\ref{alg:connectedness_tester-na}) looks for squares that contain small connected components, that is, are not border-connected, which we call witnesses. To find a witness, it samples $r$-squares for $\log\frac 1 \eps+1$ values of $r,$ which we call levels. In each subsequent level, the number of samples is doubled, but the side length of the squares is halved, i.e., the number of pixels in them is divided by 4.
%Consequently, the number of examined pixels is dominated by the number of pixels...
If it finds a witness, it samples pixels to look for black pixels outside the witness.

\ifnum\full=1
For simplicity
of the analysis of the algorithm we assume\footnote {This assumption can be made
w.l.o.g.\ because if $n\in(2^{i-1}+1,2^{i}+1)$ for some $i$, instead of the original image $M$ we can consider a $(2^{i}+1)\times (2^{i}+1)$ image $M'$, which is equal to $M$ on the corresponding coordinates and has white pixels everywhere else. Let
$\eps'=\eps n^{2}/(2^{i}+1)^{2}$.
To $\eps$-test $M$ for connectedness, it suffices to $\eps'$-test $M'$ for connectedness.
%Since $M$ is $\eps$-far from
%connectedness iff $M'$ is $\eps'$-from connectedness, we can
%solve the problem for $M'$ with parameter $\eps'$ and accept $M$ if $M'$ has been accepted and reject %it otherwise.
The resulting tester for $M$ has the desired query complexity because $\eps'=\Theta(\eps)$. If $\eps\in(1/2^{j},1/2^{j-1})$ for
some $j$, to $\eps$-test a property ${\cal P}$, it is sufficient to run an $\eps''$-test for ${\cal P}$ with  $\eps^{\prime\prime}=1/2^{j}<\eps$.}
\else
We can assume w.l.o.g.\
\fi
that $n-1$
and $1/\eps$ are powers of
$2$.
\begin{definition}[Levels, witnesses]
\label{def:Grid_pixels_and_squares_of_different_levels}
For $\lind \in\integerset{\log\frac{1}{\eps}+1},$ let $r_\lind=\frac{4}{\eps}\cdot
2^{-\lind}$ denote the length of level $\lind$.
Pixels of the set $\gp_{r_\lind}$ are called
\emph{grid pixels of level $\lind$}, and squares in the set $S_{r_\lind}$  are called \emph{squares of level} $\lind$.
A square of level $\lind$ which is not border-connected (see Definition~\ref{def:border_connectedness}) is called a \emph{witness}.
\end{definition}

\begin{algorithm}\label{alg:connectedness_tester-na}
\caption{$\ste$ for connectedness.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{$n\in\mathbb{N}$ and $\eps\in(0,1/2)$; block-sample access to an $n\times n$ binary matrix $M$.}

\DontPrintSemicolon
\BlankLine
\nl\label{step:border-connectedness-violation}
 For $\lind =0$ to  $\log\frac{1}{\eps}$

 (a) Sample $2^{\lind +1}$ squares of level $\lind$ (see Definition~\ref{def:Grid_pixels_and_squares_of_different_levels})
    uniformly at random with replacement.

 (b) For every sampled square $S$ from
 Step~\ref{step:border-connectedness-violation}a,
%let $[k_{i}-1]^{2}+(u,v)$ be the set of its pixels.
% (c) Query all pixels of $S$. Using
use a breadth-first search (BFS)  to find all connected components of the image graph $G_S$. If there is a connected component that does not have a pixel on the border of $S$, mark $S$ is a witness, and proceed to Step~\ref{step:conn-tester-pixel-sampling}.

\nl\label{step:conn-tester-pixel-sampling}
Sample $\frac{4}{\eps}$ pixels uniformly at random. If a witness is found in Step~\ref{step:border-connectedness-violation} and the sample contains a black pixel outside the witness, \reject; otherwise, \accept.
\;
\end{algorithm}

We start the analysis of Algorithm~\ref{alg:connectedness_tester-na} by relating the distance of an image to connectedness to the fraction of witnesses it contains at different levels.
 %Lemmas~\ref{lm:repair_witnesses}
\begin{lemma}
\label{lm:repair_witnesses}
Consider an $n\times n$ image $M,$ and let $w_\lind$ denote the fraction of witnesses among all squares in $S_{r_\lind} $ for all  $\lind \in\integerset{\log\frac{1}{\eps}+1}$. Then
$\dis(M,\C)\leq \frac{\eps}{2}+\frac \eps 4 \sum\nolimits_{\lind =0}^{\log\frac{1}{\eps}}  2^{\lind +1} w_\lind$.
\end{lemma}
\begin{proof}
We will show how to make $M$ connected by changing the required fraction of pixels.
First, we make all pixels in $\gp_{r_0}$ black. By Claim~\ref{claim:GP-size}, there are at most $2n^2/r_0=\eps n^2/2$ of them.
Then we recursively ``repair'' the witnesses, starting from the witnesses in $S_{r_0}$, as follows. Inside each witness  $S\in S_{r_\lind},$ we make the pixels in $\gp_{r_{\lind+1}}$ black, and call the set of modified pixels the \emph{cross} of $S$. Then we call the repair procedure on all witnesses in $S_{r_{\lind+1}}$ which are inside $S$. At each level, all pixels that belong to the central cross of a witness are connected to the grid pixels of level $0$. After processing witnesses of level $\log\frac{1}{\eps}$, which  are $3\times3$ squares, the image is connected.
% Inside each such witness there are either at most $4$ white pixels or at most $4$ black pixels. Thus, we can connect black pixels inside every such witness to the grid pixels of level $\log\frac{1}{\eps}$ or remove all these black pixels by modifying at most $4<2\cdot3=6$ pixels (i.e., we ``repair'' this witness in either case). Therefore, we modify at most $2r_\lind$ pixels inside each witness of level $\lind$  and obtain a connected image.
There are $(\frac{n-1}{r_\lind})^2$ squares in $S_{r_\lind}$.
 In each witness of level $\lind$  we modify at most $2r_\lind$ pixels.
All together, at level $\lind$  we modify at most $2r_\lind \cdot w_\lind \cdot(\frac{n-1}{r_\lind})^2\leq \frac{2w_\lind  n^2}{r_\lind}=\frac{\eps n^2\cdot 2^{\lind+1}w_\lind}{4}$ pixels. Overall, at most $\frac{\eps}{2}+\frac \eps 4 \sum\nolimits_{i=0}^{\log\frac{1}{\eps}}  2^{\lind+1} w_\lind$ fraction of pixels is modified in $M$ to obtain a connected image, as claimed.
\end{proof}

\paragraph{Analysis of Algorithm~\ref{alg:connectedness_tester-na}.}
If the input image $M$ is connected, the algorithm always accepts because there are no witnesses.

Consider an image $M$ that is $\eps$-far from connected, i.e., $\dis(M,\C)\geq \eps$. Then by Lemma~\ref{lm:repair_witnesses}, $\sum\nolimits_{i=0}^{\log\frac{1}{\eps}} 2^{\lind+1}w_\lind \geq 2$.
%
For fixed $\lind\in\integerset{\log\frac{1}{\eps}+1},$  the probability that Algorithm~\ref{alg:connectedness_tester-na} fails to detect a witness of level $\lind$  is
$(1-w_\lind )^{2^{\lind+1}}\leq e^{-w_\lind 2^{\lind+1}}$. Thus, the overall probability that it fails to detect a witness is at most
$\Pi_{i=0}^{\log \frac 1\eps}e^{-w_\lind 2^{\lind+1}} = \exp(-\sum\nolimits_{i=0}^{\log\frac{1}{\eps}} 2^{\lind+1}w_\lind )\leq e^{-2}\leq 1/6.$

Assume that the algorithm detects a witness $S$. There are at most $\frac{16}{\eps^2}<\frac{\eps n^2}{2}$ pixels  in $S$. Since $\dis(M,\C)\geq \eps$, there are at least $\eps n^2$ black pixels in $M$, and at least $\frac{\eps n^2}{2}$  of them are outside $S$.  The probability that Algorithm~\ref{alg:connectedness_tester-na} fails to detect at least one of these black pixels in Step~\ref{step:conn-tester-pixel-sampling} is at most $(1-\frac{\eps}{2})^{\frac{4}{\eps}}<e^{-2}<1/6$. Thus, the algorithm detects a witness and a black pixel outside it with probability at least $1-(1/6+1/6)=2/3,$ as required.




\paragraph{Query and time complexity.}
The algorithm samples $2^{\lind+1}$ squares of $S_{r_\lind}$, for
$\lind\in\integerset{\log\frac{1}{\eps}}$, and inside each square queries
$(\frac{4}{\eps}\cdot2^{-\lind}-1)(\frac{4}{\eps}\cdot2^{-\lind}-1)<\frac{16}{\eps^{2}2^{2\lind}}$ pixels.
Thus, the query complexity of the algorithm is
$$\sum\nolimits_{\lind=0}^{\log\frac{1}{\eps}} 2^{\lind+1}\cdot \frac{16}{\eps^{2}2^{2\lind}}<\sum\nolimits_{\lind=0}^{\log\frac{1}{\eps}}\frac{32}{\eps^{2}2^{\lind}}=O\Big(\frac{1}{\eps^{2}}\Big).$$
The time complexity is linear in the number of samples, since BFS takes time linear in the number of vertices on bounded-degree graphs, and the remaining steps can be easily implemented to run in the time proportional to the number of sampled pixels.
%
%of Step~\ref{step:sample-connectedness-tester} is $O(\frac{1}{\eps})$.
%Therefore, the total time complexity of the algorithm is
%$O(\frac{1}{\eps})$+time complexity of Step~\ref{step:border-connectedness-violation}c. In Step~\ref{step:border-connectedness-violation}c the algorithm performs a BFS within each sampled square. If it finds a witness it checks if there is a black pixel from the sample (outside the witness) which takes $O(\frac{1}{\eps})$ time.
%Breadth first search is linear in the sum of the number of edges and the number of nodes of the graph.
%Every pixel of a sampled square has at most $4$ neighbouring pixels.
%This implies that the number of edges in the image graph of every sampled square is linear in the number of pixels inside it and thus, the time complexity of
%Step~\ref{step:border-connectedness-violation}c is $O(\frac{1}{\eps^{2}})$. This completes the proof of the theorem.
\end{proof}
\end{comment}

\iffalse
\appendix

\section{Algorithm for Border Connectedness}
\label{sec:border-con}
\newcommand{\Out}{\mbox{\it Out}}
\newcommand{\cMb}{\overline{{\mathcal M}}}
\newcommand{\Be}{{\bf B}}

This section contains the proof of the following lemma.

\begin{lemma}
\label{thm:border-con}
Let $S$ be a $k\times k$ image. There is an algorithm that computes $\dis(S,\C')$ in time $\exp \left (O(k)\right)$.
\end{lemma}

\begin{proof}
To prove the theorem we give a dynamic programming algorithm that computes $\dis(S,\C')$ in the following way: Starting from row 1 of $S$, it processes a row and proceeds to the next one. The algorithm stops after processing row $k$. For each $i\in[k]$, it computes the cost of every recoloring of the first $i$ rows of $S$ according to the first $i$ rows of every $k\times k$ border-connected image. Among the costs that it finds while processing the last row $k$, the algorithm outputs the minimum one.

\begin{definition}
\label{def:block}
For $i\in[k]$, let $\overline{r}_{i}\in\{0,1\}^{k}$ be a vector that corresponds to the $i^{th}$ row of $S$. Let $\overline{col}\in\{0,1\}^k$ denote a recoloring for a row in $S$. Call maximal consecutive runs of $1$'s in $\overline{col}$ {\em 1-blocks} and let $num(\overline{col})$ denote the number of 1-blocks in $\overline{col}$. Let $\Sigma=\{0,1,<,\times,>\}$.
\end{definition}

Consider a $k\times k$ image $S'$. Recall that $G_{S'}$ denotes the image graph of $S'$. For every $i\in[k]$, denote the subgraph of $G_{S'}$, induced by the first $i$ rows in $S'$, by $G^i_{S'}$. Index 1-blocks in row $i$ of $S'$ in the nondecreasing order of indices of pixels they contain. For example, a row $001110011$ contains two 1-blocks; the 1-block with three $1$'s  has index 1, the 1-block with two $1$'s has index 2. Each 1-block in row $i$ has one of the following 5 statuses w.r.t.\ $G^i_{S'}$:
\begin{itemize}
\item{connected to the border of $S'$ (denoted by 1);}
\item{isolated, i.e., connected neither to the border nor to any other 1-block in its row (denoted by 0);}
\item{first 1-block in its connected component, i.e., it is in the same connected component with other 1-blocks of row $i$ and has the smallest index among them (denoted by $<$);}
\item{intermediate 1-block in its connected component, i.e., has neither largest nor smallest index in its connected component (denoted by ``$\times$'');}
\item{last 1-block in its connected component, i.e., it is in the same connected component with other 1-blocks of row $i$ and has the largest index among them (denoted by $>$).}
\end{itemize}

The algorithm that we give is Algorithm~\ref{alg:dist}. The reader may look at its pseudocode at this point. Statuses of 1-blocks in $\overline{col}$ are captured by a {\em status vector} $\overline{st}\in\Sigma^{num(\overline{col})}$. Call the pair $(\overline{col},\overline{st})$ {\em configuration}. Let $\overline{col'}$ denote the coloring of row $i+1$ in $S'$. Define $B(i,\overline{col},\overline{st})=\{k\times k \text{ border-connected images with configuration } (\overline{col},\overline{st}) \text{ in row }i\}$, for $i\in[k]$, $\overline{col}\in\{0,1\}^k$, and $\overline{st}\in\Sigma^{num(\overline{col})}$. Let $cost_{i,S'}$ denote the fraction of pixels modified in $S$ after recoloring its first $i$ rows according to the first $i$ rows of $S'$. Define ${cost}(B(i,\overline{col},\overline{st}))=\min_{S'\in B(i,\overline{col},\overline{st})}(cost_{i,S'})$. Let $\overline{col'}$ denote the coloring of row $i+1$ in $S'\in B(i,\overline{col},\overline{st})$. Configuration $(\overline{col},\overline{st})$ is {\em consistent} with coloring $\overline{col'}$, i.e., every 1-block in $\overline{col}$ that has status other than 1 is connected to a 1-block in $\overline{col'}$ w.r.t.\ $G^{i+1}_{S'}$. Moreover, $\overline{col'}$ has a status vector $\overline{st'}$ that can be determined from $\overline{col},\overline{col'}$, and $\overline{st}$. Suppose ${cost}(B(i,\overline{col},\overline{st}))$ is known for every configuration $(\overline{col},\overline{st})$. Thus, if we find status vector $\overline{st'}$ for all colorings $\overline{col'}$ consistent with $(\overline{col},\overline{st})$, we can compute $cost(B(i+1,\overline{col'},\overline{st'}))$. After computing costs for all sets $B(\cdot,\cdot,\cdot)$, we find $\dis(S,\C')$ which will be equal to $\min_{\overline{col},\overline{st}}cost(B(k,\overline{col},\overline{st}))$.

\begin{algorithm}
\caption{Distance to border connectedness of a square $S$.}
\label{alg:dist}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{access to a $k\times k$ square $S$.}
\DontPrintSemicolon
\BlankLine
\nl\label{st:init}\ForAll  {indices $i\in[k]$, vectors $\overline{col}\in\{0,1\}^k$, and $\overline{st}\in \Sigma^{num(\overline{col})}$} \do{
\tcp{Let $\bold{1}^t$ denote the string of $t$ 1's.}
\nl\quad$cost(B(i,\overline{col}, \overline{st}))=
\begin{cases} |\overline{r}_{1}-\overline{col}|_1, & \mbox{if } i=1\mbox{ and }\overline{st}=\bold{1}^{num(\overline{col})};\\
\infty, & \mbox{otherwise.}\end{cases}$\\}

\nl \label{st:subsequent} \ForAll {indices $i=2,3,...,k$, vectors $\overline{col},\overline{col'}\in\{0,1\}^k$ and $\overline{st}\in\Sigma^{num(\overline{col})}$}
   \do{
\nl\quad \textbf{if} $cost(B(i-1,\overline{col},\overline{st}))\neq\infty$ \textbf{then}

\nl\quad\quad$\overline{st'}=\Compst(i,\overline{col},\overline{st},\overline{col'})$\\
\nl\quad\textbf{if} $\overline{st'}\neq\perp$ \textbf{then}

\nl\quad\quad$cost(B(i,\overline{col'},\overline{st'}))=\min\{cost(B(i,\overline{col'},\overline{st'})), cost(B(i-1,\overline{col},\overline{st}))+|\overline{r}_{i}-\overline{col'}|_1\}$

%\tcp{}
}


\nl \label{st:actual-min}\Return $(\min_{\overline{col}\in\{0,1\}^k, \overline{st}\in\Sigma^{num(\overline{col})}}cost(B(k,\overline{col}, \overline{st})))\cdot k^{-2}$


\end{algorithm}

\subparagraph{Analysis of Algorithm~\ref{alg:dist}.}
We prove the following statement that shows correctness of the algorithm: For each $i\in[k]$, Algorithm~\ref{alg:dist} computes the minimum cost of each configuration in row $i$. We prove this statement inductively. For the first row, the algorithm indeed computes minimum costs for every possible configuration. (Note that every 1-block in the first row is connected to the border and thus, every such 1-block has status $1$.) Let us assume that the statement is true for some row $i\in[k]$. We prove the statement for row $i+1$. Note that each 1-block of a coloring in row $i+1$ has one of the 5 statuses that we introduced. Let $(\overline{col},\overline{st})$ denote the configuration in row $i$. The algorithm considers all consistent colorings $\overline{col'}$ of row $i+1$ and finds its status vector $\overline{st'}$ by using subroutine \Compst. The algorithm updates the cost of $(\overline{col'},\overline{st'})$ to $\min$\{cost of $(\overline{col'},\overline{st'})$, cost of $(\overline{col},\overline{st})+|\overline{r_{i+1}}-\overline{col'}|$\}. Thus, for each configuration of row $i+1$, the algorithm will eventually find the minimum cost. The algorithm computes the cost of every configuration in row $k$ and outputs the minimum one among these costs. Let $\hat{S}$ be an image such that $\dis(S,\C')=\dis(S,\hat{S})$. Row $k$ in $\hat{S}$ has some configuration which has the minimum cost among all configuration costs for the row. Note that the cost of a configuration in row $k$ is equal to the cost of recoloring of $S$ to some border connected square. Therefore, the output of the algorithm is equal to $\dis(S,\C')$. This completes the correctness proof.

We show how subroutine \Compst computes $\overline{st'}$. For each $i\in[k-1]$ and every pair of colorings $\overline{col}$,$\overline{col'}$, let $S(i,\overline{col},\overline{col'})$ denote the image obtained from $S$ after recoloring its row $i$ and row $i+1$ to $\overline{col}$ and $\overline{col'}$, respectively. Let $\overline{st}$ be the status vector of $\overline{col}$. Note that $\overline{st}$ provides information about which 1-blocks in $\overline{col}$ are connected. Let $n_1=num(\overline{col})$ and $n_2=num(\overline{col'})$. Index 1-blocks in $\overline{col}$ in the nondecreasing order of indices of pixels they contain. Index 1-blocks in $\overline{col'}$ in the nondecreasing order of indices of pixels they contain and add $n_1$ to each index. Construct graph $G=(V,E)$ such that $V=[n_1+n_2]$ and $E$ has every edge of the following two types:
\begin{enumerate}
\item edges $(i,j)$, where $i,j\in[n_1]$, $i<j$, and $i$ is not connected to any $j'<j$
\item $(i,n_1+j)$, where $i\in[n_1], j\in[n_2]$, and $i$ is connected to $n_1+j$ in $G^{i+1}_{S(i,\overline{col},\overline{col'})}$.
\end{enumerate}

We say that $G$ {\em corresponds to} $\overline{col}$, $\overline{col'}$, and $\overline{st}$. Graph $G$ can be constructed in $O(k)$ time.

\begin{algorithm}\label{alg:conf}
\caption{Subroutine \Compst used in Algorithm~\ref{alg:dist}.}
\label{alg:conf}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{index $i$; vectors $\overline{col},\overline{col'}\in\{0,1\}^k$, and $\overline{st}\in\Sigma^{num(\overline{col})}$.}
\DontPrintSemicolon
\BlankLine
%\tcp{Construct graph $G=(V,E)$.}

\nl Construct graph $G=(V,E)$ that corresponds to $\overline{col}$, $\overline{col'}$, and $\overline{st}$. Let $n_1=num(\overline{col})$ and $n_2=num(\overline{col'})$\\
\tcp{Let $\bold{1}^t$ (resp, $\bold{0}^t$) denote the strings of $t$ 1's (resp, 0's). }
\nl \textbf{if} $i\neq k$ let $\overline{st'}=\bold{0}^{\overline{col'}}$. Update $\overline{st'}[1]=\overline{col'}[1]$ and $\overline{st'}[n_2]=\overline{col'}[k]$ \textbf{else} $\overline{st'}=\bold{1}^{\overline{col'}}$

\nl For every pair $(j,n_1+j')$, $j\in[n_1],j'\in[n_2]$, \textbf{if} $\overline{st}[j]=1$ \text{then} $\overline{st}[n_1+j']=1$.

\nl Run BFS to determine connected components in $G$. For every pair $(n_1+j,n_1+j')$, $j,j'\in[n_2]$, \textbf{if} $j$ and $j'$ are connected and $\overline{st'}[j]=1$ \textbf{then} $\overline{st'}[n_1+j']=1$.

\nl \textbf{if} $i\neq k$ \textbf{then} for every connected component of vertices $n_1+j$, where $j\in[n_2]$, that are not marked by 1, update the corresponding entries of $\overline{st'}$ with the corresponding symbols in $\Sigma$ (i.e., $\overline{st'}[j]=<$ if it is the vertex with the smallest index in the component, $\overline{st'}[j]=>$ if it is the vertex with the largest index in the component, and $\overline{st'}[j]=\times$, otherwise).

\nl \textbf{if} each $j\in[n_1]$ such that $\overline{st'}[j]\neq 1$ is connected to a 1-block in row $i+1$, \textbf{then} \Return $\overline{st'}$

\nl \textbf{else} \Return $\perp$

\end{algorithm}
The most expensive step in Algorithm~\ref{alg:dist} is Step 3. Note that there are at most $k\cdot2^k\cdot5^k$ sets $B(\cdot,\cdot,\cdot)$. Thus, Step 3 of the algorithm runs in time $O( k\cdot k2^k5^k)=\exp \left (O(k)\right)$ (subroutine \Compst runs in time $O(k)$). Thus, the running time of the algorithm is $\exp \left (O(k)\right)$, as claimed.


\subsection{Improved Approximation for Distance to Connectedness}\label{sec:improved-approximation-for-connectedness}
\begin{theorem}
Fix parameters $\alpha\in(0,1/2)$ and $\mydelta>0$. There exists an algorithm ...
with query complexity $O(\frac{1}{\alpha^{2}\mydelta^{2}})$.
\end{theorem}
At a high level, the algorithm partitions the image into smaller images of size $\frac{4}{\alpha\mydelta}\times\frac{4}{\alpha\mydelta}$ and samples $c$ of them uniformly at random. Then the algorithm proceeds as the following: at each level $i=1,2,3,...,\log\frac{1}{8\mydelta}$ the algorithm partitions each square image of the previous level ($i-1$) into four equal sub-squares of the current level ($i$) and samples $c\cdot2^{i}$ of all squares of the current level uniformly at random. For each sampled image the algorithm evaluates the \emph{net-cost}. Based on the net-cost and a \emph{threshold value} that is evaluated at each level the algorithm computes the \emph{reported-cost} of each sampled square and takes the average. Both the net-cost and reported-cost of the sampled image are evaluated recursively from bottom to up by considering all the images in it starting from the smallest ones. The algorithm outputs the sum of all values(averages) that were computed at each level.

To compute the net-cost and reported-cost of a square we use a black box that takes   image, \emph{super pixels} and \emph{super pixels' cost} of the image as an input and outputs the distance to property $C'$. To evaluate the net-cost of each smallest square the black box takes only the square as an input. The reported-cost of each such square is $0$ if its net-cost$ < \frac{2f}{\alpha}$, where $f$ is the perimeter of the image, and it is equal to the net-cost otherwise.
%For squares at level $i=\log\frac{1}{8\mydelta}-1,...,2,1$


\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Commented out unfinished section with improved dist approx to connectedness
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\subsection{Improved Approximation for Distance to Connectedness}\label{sec:improved-approximation-for-connectedness}
\begin{theorem}
Fix parameters $\alpha\in(0,1/2)$ and $\mydelta>0$. There exists an algorithm ...
with query complexity $O(\frac{1}{\alpha^{2}\mydelta^{2}})$.
\end{theorem}
At a high level, the algorithm partitions the image into smaller images of size $\frac{4}{\alpha\mydelta}\times\frac{4}{\alpha\mydelta}$ and samples $c$ of them uniformly at random. Then the algorithm proceeds as the following: at each level $i=1,2,3,...,\log\frac{1}{8\mydelta}$ the algorithm partitions each square image of the previous level ($i-1$) into four equal sub-squares of the current level ($i$) and samples $c\cdot2^{i}$ of all squares of the current level uniformly at random. For each sampled image the algorithm evaluates the \emph{net-cost}. Based on the net-cost and a \emph{threshold value} that is evaluated at each level the algorithm computes the \emph{reported-cost} of each sampled square and takes the average. Both the net-cost and reported-cost of the sampled image are evaluated recursively from bottom to up by considering all the images in it starting from the smallest ones. The algorithm outputs the sum of all values(averages) that were computed at each level.

To compute the net-cost and reported-cost of a square we use a black box that takes   image, \emph{super pixels} and \emph{super pixels' cost} of the image as an input and outputs the distance to property $C'$. To evaluate the net-cost of each smallest square the black box takes only the square as an input. The reported-cost of each such square is $0$ if its net-cost$ < \frac{2f}{\alpha}$, where $f$ is the perimeter of the image, and it is equal to the net-cost otherwise.
%For squares at level $i=\log\frac{1}{8\mydelta}-1,...,2,1$
\fi


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Postponed results
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
\section{Property Testers for Connectedness}\label{tester_for_connectedness}
In this section we give two $\eps$-testers
for connectedness of an image: nonadaptive and adaptive. The latter has better
query and time complexity. Both algorithms work as follows: at each step they
partition the image into subimages of the same size, sample one of these
subimages and test it for  border connectedness (see Definition~
\ref{def:border_connectedness}). The nonadaptive algorithm uses subroutine \emph{Exhaustive-Square-Tester}
(Algorithm~\ref{alg:exhaustive_square_tester}) to test for border connectedness, whereas the adaptive algorithm uses \emph{Diagonal-Square-Tester} (Algorithm~\ref{alg:diagonal_square_tester}) for that task.

 \begin{theorem}\label{thm:connectedness_tester}
Given a proximity parameter $\eps\in(0,1)$, connectedness of $n\times n$ images, where  $n>\eps^{-2}\cdot 256$, can be $\eps$-tested nonadaptively and with 1-sided error with query and time complexity $O(\frac{1}{\eps^{2}})$.
It can be $\eps$-tested adaptively and with 1-sided error with query and time complexity $O(\frac{1}{\eps^{3/2}} \sqrt{\log\frac{1}{\eps}})$.
\end{theorem}

Our $\ste$ samples pixels uniformly at random and
then constructs sets of subimages of different sizes, such that subimages of the
same size belong to the same set.
It then samples subimages from each set and within every sampled subimage
it uses one of the two subroutines to test for $\C'$ (border
connectedness). If it finds a subimage that violates $\C'$ and a black
pixel outside that subimage it reports that the image is $\eps$-far from
connectedness. It reports that the image is connected otherwise. For simplicity
of the analysis of the algorithm we assume\footnote {This assumption can be made
w.l.o.g.\ because if $n\in(2^{i-1}+1,2^{i}+1)$ for some $\lind$ , instead of the original image $M$ we can consider a $(2^{i}+1)\times (2^{i}+1)$ image $M'$, which is equal to $M$ on the corresponding coordinates and has white pixels everywhere else. Let
$\eps'=\eps n^{2}/(2^{i}+1)^{2}$.
To $\eps$-test $M$ for connectedness, it suffices to $\eps'$-test $M'$ for connectedness.
%Since $M$ is $\eps$-far from
%connectedness iff $M'$ is $\eps'$-from connectedness, we can
%solve the problem for $M'$ with parameter $\eps'$ and accept $M$ if $M'$ has been accepted and reject %it otherwise.
The resulting tester for $M$ has the desired query complexity because $\eps'=\Theta(\eps)$. If $\eps\in(1/2^{j},1/2^{j-1})$ for
some $j$, to $\eps$-test a property ${\cal P}$, it suffices to run an $\eps''$-test for ${\cal P}$ with  $\eps^{\prime\prime}=1/2^{j}<\eps$.} that $n-1$ and $1/\eps$ are powers of
$2$.

\begin{definition}[Grid pixels and squares of different levels]
\label{def:Grid_pixels_squares_of_different_levels}
For $i\in\integerset{\log\frac{1}{\eps}}$ let $k_{i}=\frac{4}{\eps}\cdot
2^{-i}-1$.
Pixels of the set $G_{i}=\{(x,y)\mid (k_{i}+1)|x$ or $(k_{i}+1)|y\}$ are called
\emph{grid pixels of level $\lind$ .} For all coordinates $u,v$, which are divisible by $r_\lind+1$,
the $k_{i}\times k_{i}$ subimage that consists of pixels $[k_{i}]^{2}+(u,v)$ is
called a \emph{square of level} $\lind$ . The set of all squares of level $\lind$  is denoted $S_{i}$.
{\em Boundary pixels} of a square of level $\lind$  are the pixels of the square which are adjacent to the grid pixels of level $\lind$ . A square of level $\lind$  that violates property $\C'$ (see Definition~\ref{def:border_connectedness}) is called a \emph{witness}.
\end{definition}

\begin{algorithm}\label{alg:connectedness_tester}
\caption{$\ste$ for connectedness.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameter $\eps\in(0,1)$ ; access to a $n\times n$ binary
matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl
Query $\frac{4}{\eps}$ pixels uniformly at random.
\;
\nl For $i=0$ to  $\log\frac{1}{\eps}$

 (a) Sample $2^{i+1}$ squares of level $\lind$  (see Definition~\ref{def:Grid_pixels_and_squares_of_different_levels})
    uniformly at random with replacement.

 (b) For every sampled square $s$ from Step 1a, let
     $[k_{i}]^{2}+(u,v)$ be the set of its pixels.
Run a border-connectedness subroutine (e.g.,
Algorithm~\ref{alg:exhaustive_square_tester} or
Algorithm~\ref{alg:diagonal_square_tester}) with inputs $i,u,v$. If the
subroutine rejects and Step 1 detects a black pixel outside $s$, \reject.
\;
\nl
\Accept.
\;
\end{algorithm}
\begin{algorithm}\label{alg:exhaustive_square_tester}
\caption{Border-connectedness subroutine \emph{Exhaustive-Square-Tester}.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameters $i$, $u$ and $v$; access to
 an $n\times n$ matrix $M$.}
\DontPrintSemicolon
\BlankLine
Let $s$ be a square of level $i$ that consists of pixels $[k_{i}]^{2}+(u,v)$
\;
\nl
 Query all the pixels of $s$.
 \;
\nl
Using breadth-first search (BFS) find all connected components of black pixels
in $s$.
 \;
\nl
 If $s$ violates $\C'$, i.e., if there is a connected component of black
 pixels that does not have a pixel on the border, \reject; otherwise,
 \accept.
 \;
\end{algorithm}
Algorithm~\ref{alg:connectedness_tester} always accepts connected images
since it will see no violation of $\C'$ in Step 1b. Assume that $M$ is an image that is $\eps$-far from connectedness. To prove that the
algorithm rejects $M$ with probability at least $2/3$ and that it has the
desired query and time complexity we use
Lemmas~\ref{lm:sum_of_local_costs} and~\ref{lm:success_probability}. The
main idea behind Lemma~\ref{lm:sum_of_local_costs} is as follows: if $M$ is
$\eps$-far from connectedness there will be enough witnesses (i.e., squares
that violate $\C'$) for Algorithm~\ref{alg:connectedness_tester} to
detect at least one of them in Step 2b. In order to prove this lemma we use Claim~\ref{cl:parent_children_cost_relation} and
Claim~\ref{cl:max_dist_to_border_connectedness}.

\begin{definition}[Local cost and effective local cost]
For a fixed value of $i$ consider a square $s\in S_{i}$.
The \emph{local cost} of $s$ is $\lc(s)=\Dis(s,\C')$. The \emph{effective local cost} of $s$ is
$\elc(s)=\min(2k_{i},\lc(s))$.
\end{definition}
\begin{claim}
\label{cl:parent_children_cost_relation}
For any square $s$ of level $i\in \integerset{\log\frac{1}{\eps}-1}$, let $ch(s)$ denote the set of its $4$ children (i.e.,
squares of level $i+1$ inside it).
Then $\lc(s)\leq \elc(s)+\sum\nolimits_{q\in ch(s)} \lc(q)$.
\end{claim}
\begin{proof}
If $\lc(s)\leq 2k_{i}$ then $\elc(s)=\lc(s)$ and since all costs are nonnegative
the inequality above becomes trivial.

Now assume that $\lc(s)>2k_{i}$. Then $\elc(s)=2k_{i}$. We can modify
$\sum\nolimits_{q\in ch(s)} \lc(q)$ pixels in $s$ such that all its children
satisfy property $\C'$. Then we can make black all pixels of $s$ that
partition it into its children, i.e., pixels $\{(x,y)\mid
x=\frac{k_{i}+1}{2}$ or $y=\frac{k_{i}+1}{2}\}$. There are at most $2k_{i}$ such
pixels and after this modification $s$ will satisfy $\C'$. Hence,
$\lc(s)\leq \elc(s)+\sum\nolimits_{q\in ch(s)} \lc(q)$.
\end{proof}
\begin{claim}
\label{cl:max_dist_to_border_connectedness}
Let $s$ be a $k\times k$ square. Then $\Dis(M,\C')\leq
\frac{k^{2}+3k}{4}$.
\end{claim}
\begin{proof}
 If $M$ contains at most $\frac{k^{2}+3k}{4}$ black pixels, we can make all of them white, i.e.,
 modify less than $\frac{k^{2}+3k}{4}$ pixels, and obtain an image that satisfies $\C'$.
 Assume that there are more than  $\frac{k^{2}+3k}{4}$ black pixels in $M$. We partition all
 pixels of $M$ into $3$ groups such that group $i\in\{0,1,2\}$ contains all pixels $(x,y)$, where $y\equiv i\pmod 3$. Each group has at most $\frac{k^{2}}{3}+k$ elements and making black all the elements of one group produces an image that satisfies $\C'$. By the pigeonhole principle one group has at least $\frac{k^{2}+3k}{12}$ black pixels which means it has at most $\frac{k^{2}}{3}+k-\frac{k^{2}+3k}{12}=\frac{k^{2}+3k}{4}$ white pixels. After making all these white pixels black we obtain an image that satisfies $\C'$ and this completes the proof.
\end{proof}


\begin{lemma}
\label{lm:sum_of_local_costs}
Let $M$ be an $n\times n$ image that is $\eps$-far from $\C$. Then the sum of
effective local costs of squares of all levels inside $M$ is at least $\frac{\eps n^{2}}{2}$.
\end{lemma}
\begin{proof}
We obtain a connected image if we make all the grid pixels of level $0$ black and modify pixels inside every square of $S_{0}$ to satisfy property $\C'$
 (inside every square of that level).
Thus, $\sum\nolimits_{s\in S_{0}} \lc(s)\geq \Dis(M,\C)-\frac{\eps
n^{2}}{2}\geq\frac{\eps n^{2}}{2}$. Thus,
it is enough to show that
$\sum\nolimits_{i=0}^{\log\frac{1}{\eps}}\sum\nolimits_{s\in S_{i}}
\elc(s)\geq\sum\nolimits_{s\in S_{0}} \lc(s)$. Let $s$ be a square of level $i$. We will prove by induction that for any integer $j\in
[i,\log\frac{1}{\eps}-1],$


$$\lc(s)\leq\sum_{h=i}^{j}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,j+1)}\lc(q),$$ where
$desc(s,j)$ denotes the set of all
squares of level $j\geq i$ inside $s$ ($i$-$desc(s)$ contains
only $s$).

For $j=i$ (base case) the statement above is true since it is equivalent to the
statement in Claim~\ref{cl:parent_children_cost_relation}. Assume
that the statement above is true for $j=m$. We will prove its correctness for
$j=m+1$.
By the induction hypothesis $$\lc(s)\leq\sum_{h=i}^{m}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,m+1)}\lc(q).
$$
By Claim~\ref{cl:parent_children_cost_relation}
$$\lc(q)\leq
\elc(q)+\sum\nolimits_{f\in ch(q)}\lc(f).$$ Thus,
$$\sum\nolimits_{q\in
desc(s,m+1)}\lc(q)\leq \sum\nolimits_{q\in
desc(s,m+1)}\elc(q)+\sum\nolimits_{q\in desc(s,m+2)}\lc(q)$$ and
$$\lc(s)\leq\sum_{h=i}^{m}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,m+1)}\lc(q)\leq
$$
$$
\leq
\sum_{h=i}^{m+1}\sum\nolimits_{q\in desc(s,h)}\elc(q)+\sum\nolimits_{q\in
desc(s,m+2)}\lc(q).
$$
We showed that for any square $s$ of level $i$
$$
\lc(s)\leq\sum_{h=i}^{\log \frac{1}{\eps}-1}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in desc(s,\log\frac{1}{\eps})}\lc(q).
$$
By Claim~\ref{cl:max_dist_to_border_connectedness} in every square of the last
level the local cost is at most $\frac{4^2+3\cdot 4}{4}<2\cdot 4$, i.e., it is equal to the effective local cost of that square. Hence,
$$\lc(s)\leq\sum_{h=i}^{\log \frac{1}{\eps}-1}\sum\nolimits_{q\in
desc(s,h)}\elc(q)+\sum\nolimits_{q\in
desc(s,\log\frac{1}{\eps})}\lc(q)=\sum_{h=i}^{\log\frac{1}{\eps}}\sum\nolimits_{q\in desc(s,h)}\elc(q)$$ and
$$\sum\nolimits_{s\in S_{0}}\lc(s)\leq
\sum\nolimits_{s\in
S_{0}}\sum\nolimits_{h=i}^{\log\frac{1}{\eps}}\sum\nolimits_{q\in
desc(s,h)}\elc(q)=\sum\nolimits_{h=i}^{\log\frac{1}{\eps}}\sum\nolimits_{s\in
S_{i}}\elc(s).$$
\end{proof}

\begin{definition}[Diagonal lattice pixels, diamonds and fences]
\label{def:diagonal_lattice_pixels_and_regions}
For a fixed value of $i$ consider a square in $S_{i}$ and let
$m_{i}=\lceil\sqrt{k_{i}/\log k_{i}}\rceil$. \emph{Diagonal lattice pixels} of
the square is the set of pixels $L=\{(x,y)\mid m_{i}|(x+y)$ or $m_{i}|(x-y)\}$. Let
$D$ be a $k_{i}\times k_{i}$ image whose pixels with coordinates from $[k_{i}]^{2}-L$ are black and the remaining pixels are white.
A set of pixels of the square whose corresponding pixels
in $D$ form a connected component is called a \emph{diamond} of the square.
A set of all diagonal lattice pixels that have some neighbouring
pixel(s) from a particular diamond is called \emph{fence} of that diamond.
\end{definition}


\begin{algorithm}
\label{alg:diagonal_square_tester}
\caption{Border-connectedness subroutine \emph{Diagonal-Square-Tester}.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameters $k_{i}$, $u$ and $v$; access to
 an $n\times n$ matrix $M$.}
\DontPrintSemicolon
\BlankLine
Let $s$ be a square of level $i$ that consists of pixels $[k_{i}]^{2}+(u,v)$ and
$m_{i}=\lceil\sqrt{k_{i}/\log k_{i}}\rceil$.\;
\nl Query all the pixels from $L$ (see
Definition~\ref{def:diagonal_lattice_pixels_and_regions}) in $s$.\;
\nl
Initialize sets $A$ and $B$. Put all diamonds of $s$ that contain
a border pixel in $B$. Put the remaining diamonds in $B$.
\;
\nl
While $\exists d_{1}\in B$ and $\exists d_{2}\in A$ such that $d_{1}$ and
$d_{2}$ have a common portion on their fences with a black pixel, remove $d_{2}$
from $A$ and put it in $B$\;
  \nl
Query $\frac{1}{2}k_{i}(m_{i}-1)$ pixels in $s$ uniformly at random

  (a) If a black pixel from a region in $A$ is discovered, \reject.

  (b) If a black pixel from a region in $B$ is discovered, let $x\leq \frac{k^{2}}{3}$ be a natural
  number chosen from a distribution whose probability
  density function is $f(j)=\frac{1}{j(j+1)}$, $j\in \mathbb{N}$ (i.e.,
  $Pr(x\geq j)=\frac{1}{j}$).
  Perform a BFS starting from the black pixel.
  If the search is completed within $x$ steps, \reject. Else if $x+1$ black pixels
  were found for this component, stop the search and proceed with the remaining
  queried pixels.
\;
\nl
\Accept.
\end{algorithm}
\begin{lemma}
\label{lm:success_probability}
Fix $i$ and let $s\in S_{i}$ be a witness that consists of pixels
$[k_{i}]^{2}+(u,v)$.
A border-connectedness subroutine of
Algorithm~\ref{alg:connectedness_tester} rejects $s$ with
probability $\geq \frac{\elc(s)\cdot\alpha}{2k_{i}}$, where $\alpha=1$ for \emph{Exhaustive-Square-Tester} and $\alpha=1-e^{-1}$ for \emph{Diagonal-Square-Tester}.
\end{lemma}
\begin{proof}
\emph{Exhaustive-Square-Tester} will determine that $s$ is a witness with
probability $1\geq \frac{\elc(s)}{2k_{i}}\cdot 1$. Now we prove the claim
for \emph{Diagonal-Square-Tester}. Let $a$ denote the number of connected components
in all the regions of the set $A$ (see Steps 2 and 3 of
Algorithm~\ref{alg:diagonal_square_tester}) and $b$ be the number
of black pixels in all the regions of the set $B$ after Step 3 of the subroutine.
The probability that a pixel is selected by the subroutine in Step 4 is
$\frac{k_{i}(m_{i}-1)/2}{k_{i}^{2}}=\frac{m_{i}-1}{2k_{i}}$.
Consider one of the $a$ connected components above and let $p$ be the number of
pixels in it.
The probability that \emph{Diagonal-Square-Tester} finds this component completely equals
$\frac{1}{p}\cdot\frac{m_{i}-1}{2k_{i}}\cdot p$, i.e., one of the $p$ pixels
from this component was selected in Step 4 of the subroutine and $x\geq p$ was
chosen in Step 4b. Each of the $a$ connected components above can be
connected to the diagonal grid pixels by modifying at most $(m_{i}-1)$ pixels
and we can make all the $b$ pixels above white and the square will satisfy
$\C'$. Thus, $a(m_{i}-1)+b\geq \lc(s)\geq \elc(s)$.

The subroutine determines that $s$ is a witness if it finds one of the $a$ connected components or one of the $b$ black pixels above.
Thus, the sum of the probabilities of determining that $s$ is a witness  is
 $\frac{(a+b)(m_{i}-1)}{2k_{i}}\geq\frac{a(m_{i}-1)+b}{2k_{i}}\geq\frac{\elc(s)}{2k_{i}}$.
 Since $1-e^{-x}\geq x(1-e^{-1})$ for $x\in[0,1]$, it follows that the
 probability of determining that $s$ is a witness is at least $1-e^{-\frac{\elc(s)}{2k_{i}}}\geq\frac{\elc(s)(1-e^{-1})}{2k_{i}}$.
\end{proof}


Now we complete the proof of the theorem. For any $i$ there are
$\frac{n^{2}}{k_{i}^{2}}$ squares in $S_{i}$. Let $s$ be a witness in $S_{i}$.
The probability that the algorithm chooses $s$ in Step~1b is
$\frac{k_{i}^{2}}{n^{2}}\cdot 2^{i+1}$.
By Lemma~\ref{lm:success_probability} the probability that the algorithm rejects
$s$ is at least $\alpha\cdot \elc(s)/2k_{i}$. Since at least an $\eps$
fraction of pixels in $M$ are black and any square contains at most
$\frac{16}{\eps^{2}}<\frac{\eps n^{2}}{2}$ pixels, the probability that the
algorithm will detect a black pixel outside $s$ in Step 2 is at least
$1-(1-\frac{\eps}{2})^{\frac{4}{\eps}}>1-e^{-2}$.
Thus, the probability that the algorithm finds a witness of level $i$ in Step 1b
is at least $P_{i}=\frac{2^{i+1}k_{i}\cdot\alpha\cdot
\elc(s)}{2}=\frac{4\cdot \elc(s)\cdot\alpha}{\eps n^{2}}$.
By Lemma~\ref{lm:sum_of_local_costs} $\sum\nolimits_{i\in
\{0\}\cup[\log(1/\eps)]}P_{i}\geq \frac{4\alpha}{\eps n^{2}}\cdot \frac{\eps
n^{2}}{2}=2\alpha$. Therefore, the probability that the algorithm detects at
least one witness of any level $\geq 1-e^{-2\alpha}$, and the probability
that the algorithm rejects $M$ is at least $(1-e^{-2})(1-e^{-2\alpha})\geq 2/3$
(this holds for both values of $\alpha$).


Now we prove that the algorithm has query
complexity $O(\frac{1}{\eps^{2}})$ if it uses \emph{Exhaustive-Square-Tester}
as a subroutine.
The algorithm samples $2^{i+1}$ squares of level
$i\in\{0\}\cup[\log\frac{1}{\eps}]$ and for each sampled square it calls
\emph{Exhaustive-Square-Tester} which makes
$(\frac{4}{\eps}\cdot2^{-i}-1)(\frac{4}{\eps}\cdot2^{-i}-1)<\frac{16}{\eps^{2}2^{2i}}$ queries in each sampled square of level $i$.
Thus, the query complexity of the algorithm is $\sum\nolimits_{i=0}^{\log\frac{1}{\eps}} 2^{i+1}\cdot \frac{16}{\eps^{2}2^{2i}}<\sum\nolimits_{i=0}^{\log\frac{1}{\eps}}\frac{32}{\eps^{2}2^{i}}=O(\frac{1}{\eps^{2}})$.
When the algorithm uses \emph{Diagonal-Square-Tester} it queries
$\frac{2k_{i}^2}{m_{i}}$ inside each square of
level $i$. Then it selects $\frac{k_{i}(m_{i}-1)}{2}$ pixels and a number
$x\leq \frac{k_{i}^{2}}{3}$ such that $\Pr(x\geq j)=1/j$ and then queries at
most $4x$ pixels for each of the selected pixel. Since $\E(x)=O(\log k_{i})$ the
expected number of queries inside a square of level $i$ is at most
$\frac{2k_{i}^2}{F_{i}}+\frac{k_{i}(F_{i}-1)}{2}\cdot 4\log
k_{i}=O(k_{i}^{3/2}\sqrt{\log k_{i}})$. The expected total number of queries is
$\sum\nolimits_{i=0}^{\log(1/\eps)}k_{i}^{3/2}\sqrt{\log
k_{i}}\cdot 2^{i+1}=O(\eps^{-3/2}\sqrt{\log \frac{1}{\eps}})$. The time
complexity of Step 1a and Step 2 of the algorithm is $O(\frac{1}{\eps})$.
Therefore, the total time complexity of the algorithm is
$O(\frac{1}{\eps})$+time complexity of Step 1b. In Step 1b the algorithm
uses either \emph{Exhaustive-Square-Tester} or \emph{Diagonal-Square-Tester}. Both of them perform a breadth first search within each sampled square.
Breadth first search is linear in the sum of the number of edges and the number of nodes of the graph.
Every pixel of a sampled square has at most $4$ neighbouring pixels.
Thus, the number of edges in the image graph of every sampled square is linear in the number of pixels inside it and the time complexity of
Step 1b is linear in the number of all queried pixels, i.e.,
$O(\frac{1}{\eps^{2}})$ for \emph{Exhaustive-Square-Tester} and
$O(\eps^{-3/2}\sqrt{\log (1/\eps)})$ for
\emph{Diagonal-Square-Tester}. This completes the proof of the theorem.
\section{Property Tester for Convexity}\label{sec:convexity-tester}
\begin{theorem}\label{thm:convexity-tester}
Given $\eps\in(0,1/2)$, convexity of $n\times n$ images can be $\eps$-tested
(adaptively) with $O(1/\eps)$ queries and 1-sided error in time
$O(\frac{1}{\eps} \log
\frac{1}{\eps})$.
\end{theorem}
Our $\eps$-tester for convexity (Algorithm~\ref{alg:convexity-tester})
samples pixels uniformly at random and constructs a rectangle $R$ that with high probability contains nearly all black pixels and whose sides include sampled black pixels.
Then it adaptively queries pixels of $R$ in order to partition it into regions $B$, $W$
and $F$. The ``fence'' region $F$ has a small area. If the image is convex, $B$ contains only black pixels and $W$ contains
only white pixels.  The algorithm queries a small number of random pixels in $B\cup W$ and rejects
if it finds a misclassified pixel (i.e., a white pixel in $B$ or
a black pixel in $W$), otherwise it accepts.

Since the number of black pixels outside $R$ and the number of
pixels in $F$ are small, if the image is $\eps$-far from
convexity then there will be enough misclassified pixels in $B\cup W$, and the algorithm
will detect at least one of them with high probability.

\begin{algorithm}\label{alg:convexity-tester}
\caption{$\ste$ for convexity.}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{parameter $\eps\in(0,1)$ ; access to a $n\times n$ binary
matrix $M$.}
\DontPrintSemicolon
\BlankLine
\nl\label{step:convexity-init}
Query $\frac{64}{\eps}$ pixels uniformly at random.
%\;
%\nl
If all sampled pixels are white, \accept.
\;
\nl \label{step:convexity-test-construction_of_R}
Let $R$ be the minimum axis-parallel rectangle that contains all sampled black
pixels. Let $p_0$ (resp., $p_1,p_2,p_3$) be a sampled black pixel on the
top (resp., left, bottom, right) side of $R$.
\;
\nl\label{step:convexity-test-walk}
\For {$i=0$ \textbf{ \em{to} } $3$}{
    \nl\label{step:start-walk} Let $(x,y)=p_i$ and $W_i=\emptyset$.\tcp{Investigate the upper right corner
of $R$.}
    \nl \While {$(x,y)$ is in $R$}{
        \nl\lIf{$(x,y)$ is black or below the line through $p_{i}$ and $p_{(i+3)\bmod4}$}
            {$x=x+\left\lceil\eps n/12\right\rceil$.} %Sofya: leaves an extra line for me if you put \; here
        \nl  \lElse{$W_i=W_i\cup\{(x,y)\}$; \ \ $y=y-\left\lceil\eps n/12\right\rceil$.
    }}
    \nl\label{step:finish-walk} Let $W'_i=\{(u,v)\text{ inside $R$} \mid \exists (u',v')\in W_i \text{ such
that } u\geq u',v\geq v' \text{ with respect to}$ the rotated
coordinates$\}.$ Rotate $R$ clockwise by 90 degrees. \tcp{We rotate $R$  to reuse lines \ref{step:start-walk}-\ref{step:finish-walk} of the pseudocode for investigating all four corners.}
}
\nl\label{step:convexity-test-B-and-W}
Let $B$ be the convex hull of all black pixels discovered so far, and
$W=\cup_{i=0}^{3} W_{i}'$.\;
\nl\label{step:misclassified} Query $\frac{8}{\eps}$ pixels in $B\cup W$. If a white pixel in $B$ or a
black pixel in $W$ was detected, \reject; otherwise, \accept.\;
\end{algorithm}

\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{enclosing-box.pdf}
\caption{An illustration to Step~\ref{step:convexity-test-construction_of_R} of Algorithm~\ref{alg:convexity-tester}.}
\label{fig:enclosing-box}
\end{minipage}
\hspace{0.1\linewidth}
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=\linewidth]{walk-on-the-box.pdf}
\caption{An illustration to Steps~\ref{step:convexity-test-walk}--\ref{step:convexity-test-B-and-W} of Algorithm~\ref{alg:convexity-tester}.}
\label{fig:walk-on-the-box}
\end{minipage}
\end{figure}

\begin{proof}
We prove that Algorithm~\ref{alg:convexity-tester} satisfies
Theorem~\ref{thm:convexity-tester}. (Some steps of the algorithm are illustrated in Figures~\ref{fig:enclosing-box} and~\ref{fig:walk-on-the-box}).
First, we prove that Algorithm~\ref{alg:convexity-tester} always accepts if its input is a convex image $M$. If $M$ has no black pixels, Step~\ref{step:convexity-init} always accepts. Otherwise, all pixels in $B$ are black by convexity of $M$.
We will show that all pixels in $W$ are
white.
%Let $H$ be the convex hull of $p_0,p_1, p_2$ and $p_3$ and $T$ be the
%upper right corner triangle of the region $R-H$.
For the sake of contradiction, suppose there is a black pixel $b=(x',y')$ in $W_0$. By definition of $W_0$, there is a white pixel $w=(x,y)$ in $W'_0$ such that $x'\geq x$ and $y'\geq y$. Thus, white pixel $w$ is inside the
triangle $p_0 b p_3$, formed by three black pixels, contradicting convexity of $M$. Analogously, there are no black pixels in $W_1,W_2$ and $W_3$. Since there are no white pixels in $B$ and no black pixels in $W=\cup_{i=0}^{3} W'_i$,
Step~\ref{step:misclassified} of Algorithm~\ref{alg:convexity-tester} always $M$.

Now assume that $M$ is $\eps$-far from convexity. First, we prove the two
lemmas below:

\begin{lemma}\label{lem:black-pixels-outside-R}
The probability that there are more than $\frac{\eps n^2}4$ black pixels outside
$R$ after Step~\ref{step:convexity-test-construction_of_R} of Algorithm~\ref{alg:convexity-tester}
is at most $1/9$.
\end{lemma}
\begin{proof}
Let $L$ be a horizontal line with the largest $y$-coordinate such that the image
$M$ contains at least $\frac{\eps n^2}{16}$ black pixels on or above $L$. The
probability that none of these pixels are sampled in Step~1 of Algorithm~\ref{alg:convexity-tester}
(and, consequently $R$ lies below $L$) is at most
$(1-\frac{\eps}{16})^{64/\eps}\leq e^{-4}<1/36$. Thus, the probability that
there are more than $\frac{\eps n^2}{16}$ of black pixels in the half-plane
above $R$ is at most $1/36$. The same bound holds for the half-planes to the left, to the right and below $R$.
By a union bound the probability that there are more than $\frac{\eps
n^2}{16}\cdot 4=\frac{\eps n^2}{4}$ black pixels outside $R$ is at most
$(1/36)\cdot 4=1/9$.
\end{proof}
\begin{lemma}\label{lem:total_number_of_pixels_in_F}
Let $F=R-(B\cup W)$. Then $F$ contains at most $\frac{\eps n^{2}}{2}$ pixels.
\begin{proof}
Let $m=\lceil\eps n/12\rceil$ and $(x_i,y_i)=p_i$ (see Step~\ref{step:convexity-test-construction_of_R} of
Algorithm~\ref{alg:convexity-tester}) for $i\in\{0\}\cup[3]$.
Call a subimage that consists of pixels $(x,y)+[m]^{2}$, where $m|(x-x_i+1)$ and
$m|(y-y_i+1)$, a \emph{square}. Call squares that contain pixels from $F$
\emph{fence squares}. Let $q=(x_3,y_0)$ be the third vertex of the triangle T.
We will find an upper bound on the number of fence squares inside $T$.
Each pixel that Algorithm~\ref{alg:convexity-tester}
queries in Step 5 discovers at most one (new) square in $T$. The
number of fence squares is at most the number of all discovered squares in the
triangle. The algorithm queries at most $\frac{x_3-x_0+y_0-y_3}{\eps n/12}+2$
pixels in the triangle (thus, it discovers at most that many squares), since every time it either increases the $x$-coordinate or decreases the $y$-coordinate of the queried pixel.
Therefore, there are at most $\frac{x_3-x_0+y_0-y_3}{\eps n/12}+2$
fence squares in this triangle. Similarly, we can
find an upper bound on the number of discovered squares in the remaining
triangles. Since the perimeter of $R$ is at most $4n$, the sum of the upper bounds is at most
$\frac{4n}{\eps n/12}+8=\frac{48}{\eps}+8\leq \frac{56}{\eps}$.
The number of pixels from $F$ in a single
fence square is at most $(\frac{\eps n}{12})^{2}=\frac{\eps^{2} n^{2}}{144}$ and
the total number of pixels from $F$ in all
fence squares is at most $\frac{(\eps n)^{2}}{144}\cdot
\frac{56}{\eps}\leq\frac{\eps n^{2}}{2}$.
\end{proof}
\end{lemma}

We call a pixel {\em misclassified} if it is black and is in $W$ or if it is white and in $B$.
If we make all pixels in $B$ black and all pixels outside of $B$ white, we obtain a
convex image. Thus, by Lemma~\ref{lem:total_number_of_pixels_in_F},
$B\cup W$ contains at least $\frac{\eps n^{2}}{4}$ misclassified pixels if there are
at most $\frac{\eps n^{2}}{4}$ black pixels outside of $R$. If the latter is the
case, the probability that the algorithm will not detect a violated pixel
is at most $(1-\frac{\eps}{4})^{\frac{8}{\eps}}<e^{-2}<2/9$. By
Lemma~\ref{lem:black-pixels-outside-R} the probability that $B\cup W$
contains less than $\frac{\eps n^{2}}{4}$ misclassified pixels is at most
$1/9$.
Therefore, the probability Algorithm~\ref{alg:convexity-tester} accepts is at most
$2/9+1/9=1/3$, as desired.
\paragraph{Query complexity.} The algorithm queries pixels in Steps 1,5 and 9.
In Steps 1 and 9, the algorithm makes $O(\frac{1}{\eps})$ queries. As we mentioned earlier, the
algorithm queries $O(\frac{1}{\eps})$ pixels in Step~5. Thus, the overall query
complexity of the algorithm is $O(\frac{1}{\eps})$.

\paragraph{Running time.} The running time of the algorithm in Steps 1 through
7 and Step 9 is $O(\frac{1}{\eps})$. In Step 8, one can
obtain the convex hull of $B$ represented by a set of
$O(\frac{1}{\eps})$ points lexicographically sorted by their coordinates
in time $O(\frac{1}{\eps}\log \frac{1}{\eps})$. In Step 10, $W$ is represented
by at most 4 sets of $O(\frac{1}{\eps})$ points. In each set points are sorted
by their $y$-coordinates (either in decreasing or increasing order) and by
their $x$-coordinates (either in decreasing or increasing order).
We need to check whether a point is inside $B$ or $W$ in this step. For a single point we can do
this in time $O(\log \frac{1}{\eps})$ by a
binary search. Since we query $O(\frac{1}{\eps})$ points the running
time of Step 10 is $O(\frac{1}{\eps}\log \frac{1}{\eps})$. Therefore, the running time
of the algorithm is $O(\frac{1}{\eps})+O(\frac{1}{\eps}\log \frac{1}{\eps})=O(\frac{1}{\eps}\log \frac{1}{\eps})$.
\end{proof}








\begin{comment}

Let $\ell(d)$ denote the parallel line to the base $b'b''$ that passes at distance $d$ from it inside $\bigtriangleup b'b''v$ and let $l(d)$ denote the length of $\ell(d)$ inside $M$. Consider the line $\ell(1.5\bigdelta n)$. It partitions $\bigtriangleup b'b''v$ into a trapezoid and a triangle as shown in Figure~\ref{}. We consider the case when all black pixels of $M$ in $\bigtriangleup b'b''v$ lie inside the trapezoid.  The length of each leg of the trapezoid is at least $1.5\bigdelta n$ and thus, there exists at least one reference point on each leg, i.e, there exists a type-2 reference line that passes through the legs of the trapezoid. This reference line misclassifies at most all pixels inside the trapezoid. The area of the trapezoid is at most $1.5\cdot|b'b''|\bigdelta n$ and the claim holds.

Now let us assume that there are black pixels of $M$ above the line $\ell(1.5\bigdelta n)$. Let $\hat\ell_1\in L_{\hat\varphi}$ be the closest to the
base type-1 reference line that does not cross the base and $\hat\ell_2\in L_{\hat\varphi}$ be the closest to the
base type-1 reference line that crosses the base as shown in Figure~\ref{}. Let $\hat\ell_1$ intersect $b'v$ and $b''v$ at $v_1'$ and $v_1''$ respectively and $\hat\ell_2$ intersect $b'v$ and $b'b''$ at $v_2'$ and $v_2''$ respectively. Let $\gamma$ denote the angle between $\hat\ell_2$ and the base. Then $\gamma\leq \frac \bigdelta 2$. Let $d_1'$ be the distance from $v_1'$ to the base and $d_2'$ denote the distance from $v_2'$ to the base. The distance $d_2'$ equals the length of $v_2'v_2''$ multiplied by $\sin\gamma$. The length of $v_2'v_2''$ is at most $\sqrt{2}n$, thus, $d_2'\leq \sqrt{2}n\sin\gamma\leq \sqrt{2}n\sin\frac\bigdelta 2\leq \frac {\sqrt{2}} 2\bigdelta n$. The distance between $\hat\ell_1$ and $\hat\ell_2$ is $\bigdelta n$ and by the triangle inequality $d_1'\leq d_2'+\bigdelta n\leq\frac {\sqrt{2}} 2\bigdelta n+\bigdelta n\leq1.71\bigdelta n$
Consider the line $\ell(\hat d_1')$. There are two cases:

Case 1: All black pixels of $M$ lie inside the trapezoid below the line $\ell(\hat d_1')$. Then the line misclassifies at most $d_1'\cdot|b'b''|-\frac {1.5\bigdelta n} 2\cdot |b'b''|\leq 1.71\cdot|b'b''|\bigdelta n-0.75\cdot|b'b''|\bigdelta n< |b'b''|\bigdelta n$.

Case 2: $M$ crosses the line $\ell(\hat d_1')$. This implies that it also crosses the line $\hat\ell_1$. Let $M$ cross the line $\ell(\hat d_1')$ at points $w_1$ and $w_2$ (see Figure~\ref{}). The length of $\hat\ell_1$ inside $M$ is at most $\bigdelta n$ since no reference point was found on this portion of the line. Thus, $l(d_1')$ is also at most $\bigdelta n$ (by convexity of $M$). Let $w_3$ be the intersection point of the lines $b'w_1$ and $b''w_2$. By similarity the height of $\bigtriangleup w_1w_2w_3$ is at most $d_1'<1.71\bigdelta n$ and this triangle contains all black pixels of $M$ above $\ell(\hat d_1')$. Therefore, $\ell(\hat d_1')$ misclassifies at most $A(\bigtriangleup w_1w_2w_3)\leq \frac {1} 2\cdot d_1'\cdot|w_1w_2| $ black pixels of $M$ and at most $d_1'\cdot|b'b''| - A(b'b''w_2w_1)=d_1'\cdot|b'b''|-\frac {1} 2 \cdot(|b'b''|+|w_1w_2|)\cdot d_1'$ white pixels of $M$. This implies that $\ell(\hat d_1')$ misclassifies at most $\frac {d_1'\cdot|b'b''|} 2<0.86|b'b''|\cdot\bigdelta n$ pixels of $M$.

Therefore, $\ell(\hat d_1')$ misclassifies at most $|b'b''|\bigdelta n$ pixels of $M$. Let us consider the closest type-2 reference line to $\ell(\hat d_1')$ above it, i.e., there is now type-2 reference line that crosses the region between that line and $\ell(\hat d_1')$. Analogously, consider the closest type-2 reference line below $\ell(\hat d_1')$. The area of the region in $\bigtriangleup b'b''v$ between these two type-2 reference lines is at most $|b'b''|\bigdelta n$ and thus, either the region between $\ell(\hat d_1')$ and the upper reference line or the region between $\ell(\hat d_1')$ and lower reference line is at most $0.5\cdot|b'b''|\bigdelta n$. This implies that one of these type-2 reference lines misclassifies at most $1.5\cdot|b'b''|\bigdelta n$ pixels of M and such lines always exist since the distances from $\ell(\hat d_1')$ to the base and from $v$ to $\ell(\hat d_1')$ are at least $\bigdelta n$.

\begin{lemma}\label{lem:alg3_is_connectedness_tester}
Algorithm~\ref{alg:connectedness_tester-na} is a 1-sided error $\ste$ for connectedness.
\end{lemma}
\begin{proof}
The algorithm accepts all connected images since in step 1b \emph{Exhaustive-Square-Tester} will see no violation of $\C'$ inside each sampled square and will return TRUE every time.

Let us assume that $M$ is $\eps$-far from connectedness. Let $\phi_{i}$ be the fraction of witnesses of level $i$ and $k_{i}=\frac{4}{\eps}\cdot 2^{-i}-1$. The probability that all sampled squares are not witnesses is
$$\mathbf{p}_{\it{fail}}=\prod\limits_{i=0}^{\log\frac{1}{\eps}}(1-\phi_{i})^{2^{i+1}\phi_{i}}<\exp(-\sum\limits_{i=0}^{\log\frac{1}{\eps}}2^{i+1}\phi_{i}).
$$
Let $\exp(-\sum\limits_{i=0}^{\log\frac{1}{\eps}}2^{i+1}\phi_{i})=s_{fail}$. We will show that $s_{fail}\leq 2$. There are $\frac{\eps n^{2}}{2}$ grid pixels of level $0$. Let us make all white pixels among them black. We modify at most $\frac{\eps n^{2}}{2}$ pixels. Now, we will try repair witnesses (i.e., make them satisfy property $\C'$) bottom up starting from witnesses of level $0$ up to witnesses of level $(\log\frac{1}{\eps}-1)$. In each witness of level $i$ we make black all the pixels in the middle row and the middle column of the witness. If a modified witness of level $i$ still violates property $\C'$ then we will see this violation in witnesses of level $i+1$ and we will try to repair them at the next level (i.e., $i+1$). At each level we modify at most $2\phi_{i}(\frac{n}{k_{i}+1})^{2}(k_{i}+1)=2^{i+1}\phi_{i}\frac{\eps n^{2}}{4}$ pixels, where $i\in[0,(\log\frac{1}{\eps}-1)]$. We will reach witnesses of the last level $\log\frac{1}{\eps}$. If we repair them  we will obtain a connected image. By Claim~\ref{cl:max_dist_to_border_connectedness} we can
repair a witness of this level by modifying at most $\frac{3^{2}+3}{4}<2\cdot4$. Since there are $(\frac{n}{4})^{2}$ squares of the last level we can repair all the witnesses of this level by modifying at most $2\cdot4\cdot\phi_{\log\frac{1}{\eps}}(\frac{n}{4})^{2}=2^{(\log\frac{1}{\eps}+1)}\cdot\phi_{\log\frac{1}{\eps}}\cdot\frac{\eps n^{2}}{4}$ pixels. Thus, we obtain a connected image by modifying at most

$$\frac{\eps n^{2}}{2}+\sum\limits_{i=0}^{\log\frac{1}{\eps}}2^{i+1}\phi_{i}(\frac{\eps n^{2}}{4})=\frac{\eps n^{2}}{2}(1+\frac{s_{fail}}{2})$$

Since the image is $\eps$-far from connectedness $\frac{\eps n^{2}}{2}(1+\frac{s_{fail}}{2})\leq \eps n^{2}\rightarrow s_{fail}\leq 2$. Then $\mathbf{p}_{\it{fail}}<\exp(-2)\leq 1/3$. Thus, the probability that the algorithm detects a violation of $\C'$ and rejects the image is at least $2/3$.
\end{proof}

Analysis:
The algorithm makes $O(\frac{4}{\epsilon}  \sqrt{\frac{4/\epsilon}{\log 4/\epsilon}}\log \frac{4}{\epsilon})=O(\frac{1}{\epsilon^{3/2}}\sqrt{\log \frac{1}{\epsilon}})$ steps


It uses a subroutine that succeeds to find a violation in a square of type $k$ with probability $min(c/2k,1)\alpha$,where $c$ is the actual distance(in pixels) of the square to $C'$. This subroutine is called $(\alpha,k)$-tester of property $C'$ and $\alpha$ is a constant that will be chosen later.
At each level the algorithm queries all \emph{ lattice pixels} of the sampled square. Then it queries $kF$ of the remaining pixels, where $F=\lceil\sqrt{k/\log k}\rceil$, and for each discovered black pixel above it picks some number $L$ such that $\Pr(L\geq i)=1/i$ and performs a search until a component of size $L$ is found or there are no more black pixels exist for this component.

\end{comment}
\fi
\fi
\end{document}


Tolerant-testing-image-properties.bbl
\begin{thebibliography}{25}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Barany(2000)]{Barany00}
I.~Barany.
\newblock Extremal problems for convex lattice polytopes: a survey.
\newblock \emph{Contemporary Mathematics}, 2000.

\bibitem[Berman et~al.(2014)Berman, Raskhodnikova, and
  Yaroslavtsev]{BermanRY14}
P.~Berman, S.~Raskhodnikova, and G.~Yaroslavtsev.
\newblock {$L_p$}-testing.
\newblock In \emph{STOC}, pages 164--173, 2014.

\bibitem[Berman et~al.(2016{\natexlab{a}})Berman, Murzabulatov, and
  Raskhodnikova]{BMR16icalp}
P.~Berman, M.~Murzabulatov, and S.~Raskhodnikova.
\newblock Tolerant testers of image properties.
\newblock In \emph{ICALP}, 2016{\natexlab{a}}.

\bibitem[Berman et~al.(2016{\natexlab{b}})Berman, Murzabulatov, and
  Raskhodnikova]{BMR16socg}
P.~Berman, M.~Murzabulatov, and S.~Raskhodnikova.
\newblock Testing convexity of figures under the uniform distribution.
\newblock In \emph{SoCG}, 2016{\natexlab{b}}.

\bibitem[Blum()]{Avrim-lecture-notes}
A.~Blum.
\newblock Machine learning theory.
\newblock \emph{Lecture notes}.
\newblock URL \url{www.cs.cmu.edu/~avrim/ML12/lect0201.pdf}.

\bibitem[Campagna et~al.(2013)Campagna, Guo, and Rubinfeld]{CampagnaGR13}
A.~Campagna, A.~Guo, and R.~Rubinfeld.
\newblock Local reconstructors and tolerant testers for connectivity and
  diameter.
\newblock In \emph{APPROX-RANDOM}, pages 411--424, 2013.

\bibitem[Czumaj and Sohler(2001)]{CS01}
A.~Czumaj and C.~Sohler.
\newblock Property testing with geometric queries.
\newblock In \emph{Algorithms - {ESA} 2001, 9th Annual European Symposium,
  Aarhus, Denmark, August 28-31, 2001, Proceedings}, pages 266--277, 2001.
\newblock \doi{10.1007/3-540-44676-1_22}.
\newblock URL \url{http://dx.doi.org/10.1007/3-540-44676-1_22}.

\bibitem[Czumaj et~al.(2000)Czumaj, Sohler, and Ziegler]{CzumajSZ00}
A.~Czumaj, C.~Sohler, and M.~Ziegler.
\newblock Property testing in computational geometry.
\newblock In \emph{Algorithms - {ESA} 2000, 8th Annual European Symposium,
  Saarbr{\"{u}}cken, Germany, September 5-8, 2000, Proceedings}, pages
  155--166, 2000.
\newblock \doi{10.1007/3-540-45253-2_15}.
\newblock URL \url{http://dx.doi.org/10.1007/3-540-45253-2_15}.

\bibitem[Ehrenfeucht et~al.(1989)Ehrenfeucht, Haussler, Kearns, and
  Valiant]{EHKV89}
A.~Ehrenfeucht, D.~Haussler, M.~J. Kearns, and L.~G. Valiant.
\newblock A general lower bound on the number of examples needed for learning.
\newblock \emph{Inf. Comput.}, 82\penalty0 (3):\penalty0 247--261, 1989.

\bibitem[Fischer and Fortnow(2006)]{FischerF06}
E.~Fischer and L.~Fortnow.
\newblock Tolerant versus intolerant testing for boolean properties.
\newblock \emph{Theory of Computing}, 2\penalty0 (1):\penalty0 173--183, 2006.

\bibitem[Goldreich and Ron(2002)]{GR02}
O.~Goldreich and D.~Ron.
\newblock Property testing in bounded degree graphs.
\newblock \emph{Algorithmica}, 32\penalty0 (2):\penalty0 302--343, 2002.

\bibitem[Goldreich et~al.(1998)Goldreich, Goldwasser, and Ron]{GGR98}
O.~Goldreich, S.~Goldwasser, and D.~Ron.
\newblock Property testing and its connection to learning and approximation.
\newblock \emph{J. ACM}, 45\penalty0 (4):\penalty0 653--750, 1998.

\bibitem[Haussler(1992)]{Haussler92}
D.~Haussler.
\newblock Decision theoretic generalizations of the {PAC} model for neural net
  and other learning applications.
\newblock \emph{Inf. Comput.}, 100\penalty0 (1):\penalty0 78--150, 1992.
\newblock \doi{10.1016/0890-5401(92)90010-D}.
\newblock URL \url{http://dx.doi.org/10.1016/0890-5401(92)90010-D}.

\bibitem[Kalai et~al.(2008)Kalai, Klivans, Mansour, and Servedio]{KalaiKMS08}
A.~T. Kalai, A.~R. Klivans, Y.~Mansour, and R.~A. Servedio.
\newblock Agnostically learning halfspaces.
\newblock \emph{{SIAM} J. Comput.}, 37\penalty0 (6):\penalty0 1777--1805, 2008.

\bibitem[Kearns et~al.(1994)Kearns, Schapire, and Sellie]{KearnsSS94}
M.~J. Kearns, R.~E. Schapire, and L.~Sellie.
\newblock Toward efficient agnostic learning.
\newblock \emph{Machine Learning}, 17\penalty0 (2-3):\penalty0 115--141, 1994.
\newblock \doi{10.1007/BF00993468}.
\newblock URL \url{http://dx.doi.org/10.1007/BF00993468}.

\bibitem[Kleiner et~al.(2011)Kleiner, Keren, Newman, and Ben-Zwi]{KleinerKNB11}
I.~Kleiner, D.~Keren, I.~Newman, and O.~Ben-Zwi.
\newblock Applying property testing to an image partitioning problem.
\newblock \emph{IEEE Trans. Pattern Anal. Mach. Intell.}, 33\penalty0
  (2):\penalty0 256--265, 2011.

\bibitem[Korman et~al.(2011)Korman, Reichman, and Tsur]{KormanRT}
S.~Korman, D.~Reichman, and G.~Tsur.
\newblock Tight approximation of image matching.
\newblock \emph{CoRR}, abs/1111.1713, 2011.

\bibitem[Korman et~al.(2013)Korman, Reichman, Tsur, and Avidan]{KormanRTA13}
S.~Korman, D.~Reichman, G.~Tsur, and S.~Avidan.
\newblock Fast-match: Fast affine template matching.
\newblock In \emph{CVPR}, pages 2331--2338. IEEE, 2013.

\bibitem[Parnas et~al.(2006)Parnas, Ron, and Rubinfeld]{PRR06}
M.~Parnas, D.~Ron, and R.~Rubinfeld.
\newblock Tolerant property testing and distance approximation.
\newblock \emph{J. Comput. Syst. Sci.}, 72\penalty0 (6):\penalty0 1012--1042,
  2006.

\bibitem[Pick(1899)]{pick}
G.~Pick.
\newblock Geometrisches zur zahlenlehre.
\newblock \emph{Sitzenber. Lotos (Prague)}, 19:\penalty0 311--319, 1899.

\bibitem[Raskhodnikova(2003)]{Ras03}
S.~Raskhodnikova.
\newblock Approximate testing of visual properties.
\newblock In \emph{RANDOM-APPROX}, pages 370--381, 2003.

\bibitem[Ron and Tsur(2014)]{TsurR10}
D.~Ron and G.~Tsur.
\newblock Testing properties of sparse images.
\newblock \emph{{ACM} Trans. Algorithms}, 10\penalty0 (4):\penalty0
  17:1--17:52, 2014.
\newblock \doi{10.1145/2635806}.
\newblock URL \url{http://doi.acm.org/10.1145/2635806}.

\bibitem[Rubinfeld and Sudan(1996)]{RS96}
R.~Rubinfeld and M.~Sudan.
\newblock Robust characterizations of polynomials with applications to program
  testing.
\newblock \emph{SIAM J. Comput.}, 25\penalty0 (2):\penalty0 252--271, 1996.

\bibitem[Schmeltz(1992)]{Sch92}
B.~Schmeltz.
\newblock Learning convex sets under uniform distribution.
\newblock In \emph{Data Structures and Efficient Algorithms, Final Report on
  the {DFG} Special Joint Initiative}, pages 204--213, 1992.

\bibitem[Valiant(1984)]{Valiant84}
L.~G. Valiant.
\newblock A theory of the learnable.
\newblock \emph{Commun. {ACM}}, 27\penalty0 (11):\penalty0 1134--1142, 1984.
\newblock \doi{10.1145/1968.1972}.
\newblock URL \url{http://doi.acm.org/10.1145/1968.1972}.

\end{thebibliography}
