Tolerant Testers of Image Properties∗

arXiv:1503.01363v3 [] 15 Aug 2016

Piotr Berman†

Meiram Murzabulatov‡

Sofya Raskhodnikova§

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 , after reading a number of pixels polynomial in 1/ and
independent of the size of the image. The running time of the testers for half-plane and convexity is also polynomial in 1/. 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 halfplane 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 such that (1) every convex image has a nearby polygon in P and
(2) one can use dynamic programming to quickly compute the smallest empirical distance to a
polygon in P . This construction might be of independent interest.
∗
A preliminary version of this article was published in the proceedings of the 43rd International Colloquium on
Automata, Languages, and Programming, ICALP, 2016 [3]
†
Pennsylvania State University, USA; berman@cse.psu.edu.
‡
Pennsylvania State University, USA; meyram85@yahoo.co.uk. This author was supported by NSF CAREER
award CCF-0845701 and NSF award CCF-1422975.
§
Pennsylvania State University, USA; 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.

1

1

Introduction

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 rejection-based
algorithms that employ a quick test that is likely to reject a large number of unsuitable images
(see, e.g., citations in [16]).
Property testing [23, 12] 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 [21]. Ron and Tsur [22] 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. [16, 17, 18].
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 [19] 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 . (Distance approximation algorithms imply tolerant testers in a straightforward way: see
the remark after Definition 2.2). The only image problem for which tolerant testers were studied
is the image partitioning problem investigated by Kleiner et al. [16].
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 halfplane? 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 -additive distance approximation algorithms that run in constant time (i.e.,
dependent only on , but not the size of the image). We remark that even though it was known that
these properties can be tested in constant time [21], this fact does not necessarily imply constantquery tolerant testers for these properties. E.g., Fischer and Fortnow [10] 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Ω(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

2

Property

Sample Complexity

Half-plane

O

1
2

log 1



Convexity

O

1
2

log 1



Connectedness

O

1
4



Run Time
O

1
3

O

log 1
1
8

exp O




1


Access to Input
uniformly random pixels
uniformly random pixels



uniformly random blocks of pixels

Table 1: Our results on distance approximation. To get complexity of (1 , 2 )-tolerant testing,
substitute  = (2 − 1 )/2.
the input size1 . Implications of the VC dimension bound on convexity are further discussed below.
Our results on distance approximation are summarized in Table 1. 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/. To achieve this, we define a set of reference polygons
P such that (1) every convex image has a nearby polygon in P and (2) one can use dynamic
programming to quickly compute the smallest empirical distance to a polygon in P . 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. 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 2 for a formal specification
of the input access.)
Our algorithms for convexity and half-plane work by first implicitly learning the object2 . PAC
learning was defined by Valiant [25], and agnostic learning, by Kearns et al. [15] and Haussler [13].
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. The sample and time
complexity3 of the PAC learners is as indicated in Table 1 for distance approximation algorithms
for corresponding properties.
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 [14],
but only for the hypercube {−1, 1}d domains, not the plane. Our PAC learner of convex sets, in
1

For n × n images, the VC dimension of convexity is Θ(n2/3 ) (this is the maximum number of vertices of a convex
lattice polygon in an n × n lattice [1]); for connectedness, it is Θ(n).
2
There is a known implication from learning to testing. As proved in [12], a proper PAC learning algorithm for
property P with sampling complexity q() implies a 2-sided error (uniform) property tester for P that takes q(/2) +
O(1/) samples. There is an analogous implication from proper agnostic PAC learning to distance approximation
with an overhead of O(1/2 ) instead of O(1/). 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.
3
All our results are stated for error probability δ = 1/3. To get results for general δ, by standard arguments, it is
enough to multiply the complexity of an algorithm by log 1/δ.

3

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
[9].) Since VC dimension of convexity of n×n images is Θ(n2/3 ), proper PAC learners of convex sets
in two dimensions (that work under arbitrary distributions) must have sample complexity Ω(n2/3 ).
However, one can do much better with respect to the uniform distribution. Schmeltz [24] showed
that a non-agnostic learner for that task needs Θ(−3/2 ) samples. Surprisingly, it appears that this
question has not been studied at all for agnostic learners. Our agnostic learner for convex sets in

two dimensions under the uniform distribution needs O 12 log 1 samples and runs in time O 18 .
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.
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. [12], the input is
also an n × 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 [8] and Czumaj and Sohler [7], 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.
A line of work potentially relevant for understanding connectedness of images is on connectedness of bounded-degree graphs. Goldreich and Ron [11] gave a tester for this property, subsequently
improved by Berman et al. [2]. Campagna et al. [6] 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 [21] for details). We also
note, that unlike in [6], 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. [16].
They consider the following class of image partitioning problems, each specified by a k × k binary
template matrix T for a small 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/2 ) samples suffice
for tolerant testing of image partitioning properties. Note that VC dimension of such a property
is O(1), so by Footnote 2, we can get a O(1/2 log 1/) 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(−1 ) time [21], convexity can be tested in O(−4/3 ) time [4], and connectedness can
be tested in O(−2 log −1 ) time [21, 2]. As we explained, property testers with running time
independent of  do not necessarily imply tolerant testers with that feature. 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

4

techniques used for analyzing them are different. The tester for convexity in [4] uses only random
samples, but it is not based on dynamic programming.
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 Ω(1/2 ). This follows from the fact that Ω(1/2 ) coin flips are
needed to distinguish between a fair coin and a coin that lands heads with probability 1/2 + .)
Thus, our testers for half-plane and convexity are nearly optimal in terms of query complexity (up
to a logorithmic factor in 1/). But it is open whether their running time can be improved.
Organization. We give formal definitions and notation in Section 2. Algorithms for being a
half-plane, convexity, and connectedness are given in Sections 3, 4, and 5, 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.

2

Definitions and Notation

We use [0..n) to denote the set of integers {0, 1, . . . , n − 1} and [n] to denote {1, 2, . . . , n}. By log
we mean the logarithm base 2, and by ln, the logarithm base e.
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 × n binary matrix M of pixel values, where 0 denotes white and 1
denotes black. We index the matrix by [0..n)2 . The object is a subset of [0..n)2 corresponding to
black pixels; namely, {(i, j) | M [i, j] = 1}. The left border of the image is the set {(0, j) | j ∈ [0..n)}.
The right, top and bottom borders are defined analogously. The image border is the set of pixels
on all four borders.
For any region R, we use A(R) to denote its area.
Distance to a property. The absolute distance, Dist(M1 , M2 ), between matrices M1 and
M2 is the number of the entries on which they differ. The relative distance between them is
dist(M1 , M2 ) = Dist(M1 , M2 )/n2 . A property P is a subset of binary matrices. The distance of an
image represented by matrix M to a property P is dist(M, P) = minM 0 ∈P dist(M, M 0 ). An image
is -far from the property if its distance to the property is at least ; otherwise, it is -close to it.
Computational Tasks. We consider several computational tasks: tolerant testing [19], additive approximation of the distance to the property, and proper (agnostic) PAC learning [25, 15, 13].
Here we define them specifically for properties of images.
Definition 2.1 (Tolerant tester). An (1 , 2 )-tolerant tester for a property P is a randomized
algorithm that, given two parameters 1 , 2 ∈ (0, 1/2) such that 1 < 2 and access to an n × n
binary matrix M ,
1. accepts with probability at least 2/3 if dist(M, P) ≤ 1 ;
5

2. rejects with probability at least 2/3 if dist(M, P) ≥ 2 .
Definition 2.2 (Distance approximation algorithm). An -additive distance approximation algorithm for a property P is a randomized algorithm that, given an error parameter  ∈ (0, 1/4) and
access to an n × n binary matrix M, outputs a value dˆ ∈ [0, 1/2] that with probability at least 2/3
satisfies |dˆ − dist(M, P)| ≤ .
As observed in [19], we can obtain an (1 , 2 )-tolerant tester for any property P by running a
distance approximation algorithm for P with  = (2 − 1 )/2. Thus, all our distance approximation
algorithms directly imply tolerant testers.
Definition 2.3 (Proper agnostic PAC learner). A proper agnostic PAC learning algorithm for class
P that works under the uniform distribution is given a parameter  ∈ (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 0 ∈ P such that dist(M, M 0 ) ≤ dist(M, P) + .
Access to the input. A query-based algorithm accesses its n×n input matrix M by specifying
a query pixel (i, j) and obtaining M [i, j]. The query complexity of the algorithm is the number of
pixels it queries. A query-based algorithm is adaptive if its queries depend on answers to previous
queries and nonadaptive otherwise. A uniform algorithm accesses its n × n input matrix by drawing
independent samples (i, j) from the uniform distribution over the domain (i.e., [0..n)2 ) and obtaining
M [i, j]. A block-uniform algorithm accesses its n × n input matrix by specifying a block length
r ∈ [n]. For a block length r of its choice, the algorithm draws x, y ∈ [dn/re] uniformly at random
and obtains set {(i, j) | bi/rc = x and bj/rc = y} and M [i, j] for all (i, j) in this set. The sample
complexity of a uniform or a block-uniform algorithm is the number of pixels of the image it
examines.
Remark 2.1. Uniform algorithms have access to independent (labeled) samples from the uniform
distribution over the domain. Sometimes it is more convenient to design Bernoulli algorithms that
only have access to (labeled) Bernoulli samples from the image: namely, each pixel appears in the
sample with probability s/n2 , 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).

3

Distance Approximation to the Nearest Half-Plane Image

An image is called a half-plane image if there exist an angle ϕ ∈ [0, 2π) and a real number c such
that pixel (x, y) is black in the image iff x cos ϕ + y sin ϕ ≥ c. The line x cos ϕ + y sin ϕ = c, denoted
Lϕ
c , is a separating line of the half-plane image, i.e., it separates black and white pixels of the image.
We call ϕ the direction of the half-plane image (and Lϕ
c ). Note that ϕ is the oriented angle between
the x-axis and a line perpendicular to Lϕ
.
For
all
ϕ
∈
[0, 2π) and c ∈ R, the half-plane image with
c
ϕ
ϕ
a separating line Lc is denoted Mc and the closed half-plane whose every point (x, y) satisfies the
inequality x cos ϕ + y sin ϕ ≥ c is denoted Hcϕ . We can think of a half-plane image as a discretized
half-plane.
1
Theorem 3.1. For  ∈ ( 90
n , 4 ), there is a uniform -additive distance approximation algorithm for
the half-plane property with sample complexity O( 12 log 1 ) and time complexity O( 13 log 1 ).

6

Proof. At a high level, our algorithm for approximating the distance to being a half-plane (Algorithm 1) constructs a small set M 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 M is that the smallest empirical distance to a half-plane image in M can be computed
quickly.
√
Definition 3.1 (Reference directions and half-planes). Given  ∈ (0, 14 ), let a = n/ 2. Let
D be the set of directions of the form i for i ∈ [0..d2π/e), called reference directions. The set
of reference half-plane images, denoted M , consists of every half-plane image for which Lϕ
c is a
separating line, where ϕ ∈ D and c is an integer multiple of a.
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 2n/a = 2/ reference half-plane images
for each direction in D and, consequently, |M | ≤ 2π/ · (2/) < 13/2 .
Algorithm 1: Distance approximation to being a half-plane.
input : parameters n ∈ N,  ∈ (90/n, 1/4); Bernoulli access to an n × n binary matrix M .
1
2

Sample a set S of s = 62 ln 7 pixels uniformly at random with replacement.
Let D , M be the sets of reference directions and half-planes, respectively (see
√
Definition 3.1) and a = n/ 2.
ˆ 0 ), where d(M
ˆ 0 ) = 1 · |{p ∈ S : M [p] 6= M 0 [p]}|:
// Compute dˆ = min
d(M
s
0
M ∈M

3

4
5
6
7

foreach ϕ ∈ D do
// Lines with direction ϕ partition the image. Bucket sort samples by
position in the partition:
Assign each sample (x, y) ∈ S to bucket j = b(x cos ϕ + y sin ϕ)/ac.
For each bucket j, compute wj and bj , the number of white and black pixels it has.
ϕ
1P
ˆ ϕ) = 1 P
For each j, where Mja
∈ M , compute d(M
k<j bk + s
k≥j wk .
ja
s
ˆ the minimum of the values computed in Step 6.
Output d,

Lemma 3.2. For every half-plane image M , there is M 0 ∈ M such that dist(M, M 0 ) ≤ /1.8.
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.
Definition 3.2. The set of reference half-planes, denoted H , consists of every half-plane Hcϕ ,
where ϕ ∈ D and c is an integer multiple of a.
Claim 3.3. For every half-plane H, there is a half-plane H 0 ∈ H such that the area of the
symmetric difference of H and H 0 is at most n2 /2.
Proof. Consider a half-plane Hcϕ . Let ϕ0 be a reference direction closest to ϕ. Then |ϕ − ϕ0 | ≤ /2.
We consider two cases. See Figures 3.1 and 3.2.
0
ϕ0
Case 1: Suppose that there is a reference half-plane Hcϕ0 such that the lines Lϕ
c and Lc0
intersect inside inside [0, n − 1]2 . Note that the length of every line segment inside [0, n − 1]2 is
√
0
at most 2n. The symmetric difference of Hcϕ and Hcϕ0 inside [0, n − 1]2 consists of two regions

7

𝜑1 𝜑
2

𝜀/2

Figure 3.1: Proof of Lemma 3.2: triangular
regions.

Figure 3.2: Proof of Lemma 3.2: triangular
and quadrilateral regions.

0

ϕ
formed by lines Lϕ
c and Lc0 . 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 2n, whereas the sum of their heights is at most
sin(/2) × 2n ≤ n/ 2. Hence, the sum of their areas is at most n2 /2.
If exactly one of the regions is a quadrilateral, we add a line through the corner of the image
ϕ0
contained in the quadrilateral and the intersection point of Lϕ
c and Lc0 . It partitions the symmetric
0
difference of Hcϕ and Hcϕ0 into two pairs of triangular regions. Let ϕ1 (respectively, ϕ2 ) be the angle
ϕ0
between the new line and Lϕ
c (respectively, Lc0 ). Then ϕ1 + ϕ2 ≤ /2. Applying the same reasoning
as before to each pair of regions, we get that the sum of their areas is at most ϕ1 n2 + ϕ2 n2 ≤ n2 /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
0
0
difference of Hcϕ and Hcϕ0 is at most n2 /2. Thus, Hcϕ0 is the required M 0 .
0
0
Case 2: There exist reference half-planes Hcϕ0 and Hcϕ0 +a such that the line Lϕ
c is between
√
ϕ0
ϕ0
0
0
L = Lc0 and L = Lc0 +a . The region between L and L inside the image has length at most 2n
and width a. Thus, its area is at most n2 . Partition it into two regions: between L and Lϕ
c and
ϕ
ϕ0
ϕ0
0
2
between L and Lc . One of the two regions has area at most n /2. Thus, Hc0 or Hc0 +a is the
required M 0 .

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.)
Theorem 3.4 (Pick’s theorem [20]). For a simple lattice polygon G, let α denote the number of
lattice points in the interior of G and β denote the number of lattice points on the boundary of G.
Then A(G) = α + β/2 − 1.

8

Definition 3.3. For a polygon G, let P erim(G) denote the perimeter of G and P ix(G) denote the
number of pixels in G, i.e., pixels in the interior of G and on its boundary.
Proposition 3.5. Let G be a convex polygon. Then P ix(G) ≤ A(G) + P erim(G)/2 + 1.
Proof. If all pixels in G are collinear then P ix(G) ≤ P erim(G)/2 + 1 ≤ A(G) + P erim(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 α and β 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 3.4, we
obtain that α+β/2−1 ≤ A(G) and P ix(G) = α+β ≤ A(G)+β/2+1 ≤ A(G)+P erim(G)/2+1.
For some ϕ and c, half-plane image M = Mcϕ . Consider the half-plane Hcϕ . By Claim 3.3, there
0
0
is a half-plane Hcϕ0 such that the area of the symmetric difference of Hcϕ and Hcϕ0 is at most n2 /2,
where ϕ0 ∈ D and c is a multiple of a.
Recall that there are 4 cases for the symmetric difference of H and H 0 . 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 0 consist of two quadrilaterals Q1 and Q2 . (For reference,
see Figure 3.2 where
a triangle and a quadrilateral are shown.)
√
√ Every line segment in the image has
length at most 2n. Thus, P erim(Q1 ) + P erim(Q2 ) ≤ 6 2n. By Proposition 3.5, we obtain
that
√
2
P ix(Q1 ) + P ix(Q2 ) ≤ A(Q1 ) + A(Q2 ) + (P erim(Q1 ) + P erim(Q2 ))/2 + 2 ≤ n /2 + 3 2n + 2 ≤
n2 /1.8 (recall that  ∈ (90/n, 1/4)). This completes the proof.

Analysis of Algorithm 1. Let dM be the distance of M to being a half-plane. Then there
exists a half-plane matrix M ∗ such that dist(M, M ∗ ) = dM . By a uniform convergence bound
(see, e.g., [5]), since s ≥ (2.6/2 )(ln |M | + ln 6) for all  ∈ (0, 1/4), we get that with probability at
ˆ 0 )| ≤ /2.25 for all M 0 ∈ M . Suppose this event happened. Then
least 2/3, |dist(M, M 0 ) − d(M
ˆ
d ≥ dM − /2.25 because dist(M, M 0 ) ≥ dM for all half-planes M 0 . Moreover, by Lemma 3.2,
there is a matrix M̂ ∈ H such that dist(M, M̂ ) ≤ dist(M, M ∗ ) + dist(M ∗ , M̂ ) ≤ dM + /1.8. For
ˆ M̂ ) ≤ dist(M, M̂ ) + /2.25 ≤ dM + . Thus, dM − /2.25 ≤ dˆ ≤ dM + . That is,
this matrix, d(
ˆ ≤  with probability 2/3, as required.
|dM − d|
Sample and time complexity. The number of samples, s, is O(1/2 log 1/). To analyze
the running time, recall that |D | = O(1/). For each direction in D , we perform a bucket
sort of all samples in expected O(s) time. The remaining steps in the foreach loop of Step 3
can also be implemented to run in O(s) time. The expected running time of Algorithm 1 is thus
O(1/·s) = O(1/3 log 1/). Remark 2.1 implies a tester with the same worst case running time.
Corollary 3.6. The class of half-plane images is properly agnostically PAC-learnable with sample
complexity O( 12 log 1 ) and time complexity O( 13 log 1 ) under the uniform distribution.
ˆ 0 ), a reference halfProof. We can modify Algorithm 1 to output, along with dˆ = minM 0 ∈M d(M
plane M̂ that minimizes it. By the analysis of Algorithm 1, with probability at least 2/3, the
output M̂ satisfies dist(M, M̂ ) ≤ dM + .
9

4

Distance Approximation to the Nearest Convex Image

An image is convex if the convex hull of all black pixels contains only black pixels.
Theorem 4.1. For  ∈ (n−1/6 , 1/4), there is a uniform -additive distance approximation algorithm
for convexity with sample complexity O( 12 log 1 ) and running time O( 18 ).
Proof. The starting point for our algorithm for approximating the distance to convexity (Algorithm 2) is similar to that of Algorithm 1 that approximates the distance to a nearest half-plane.
We define a small set P of reference polygons. Algorithm 2 implicitly learns a nearby reference
polygon and outputs the empirical distance from the image to that polygon. The key features
of P is that (1) every convex image has a nearby polygon in P , and (2) one can use dynamic
programming (DP) to quickly compute the smallest empirical distance to a polygon in P .
We start by defining reference directions, lines, points, and line-point pairs that are later used
to specify our DP instances. Reference directions are almost the same as in Definition 3.1.
Definition 4.1 (Reference lines, line-point pairs). Fix 0 = /144. The set of reference directions
is D = {π/2} ∪ {i0 : i ∈ [0, d2π/0 e)}. For every ϕ ∈ D , define the set of reference lines
Lϕ = {` : ` passes through the image and satisfies the equation x cos ϕ + y sin ϕ = c, where c is an
integer multiple of 0 n}. For each reference line, the set of reference points on ` contains points
w.r.t. `, which are inside [0, n − 1]2 , spaced exactly 0 n apart (it does not matter how the initial
point is picked). A line-point pair is a pair (`, b), where ` is a reference line and b is a reference
point w.r.t. `. (Note that there could be reference points on ` that were defined w.r.t. some other
reference line. This is why we say “a reference point w.r.t. `”, and not “a reference point on `”.)
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.

ℓ0

Triangles of 𝑇0

𝑏0

𝑏0

𝑏1

𝑏1

𝑏3

𝑏3

ℓ1
ℓ2

ℓ3
𝑏2

𝑏2
Figure 4.1: A reference box.

Figure 4.2: Triangles of the set T0 .

10

Definition 4.2 (Reference box). A reference box is a set of four line-point pairs (`i , bi )
i = 0, 1, 2, 3, where `0 , `2 are distinct horizontal lines, such that `0 is above `2 , and (`1 , `3 )
distinct vertical lines, such that `1 is to the left of `3 . The reference box defines a vertex
B0 = {b0 , b1 , b2 , b3 } and a triangle set T0 , formed by removing the quadrilateral b0 b1 b2 b3 from
rectangle delineated by the lines `0 , `1 , `2 , `3 . See Figures 4.1- 4.2.

for
are
set
the

Note that line-point pairs do not depend on the input. Intuitively, by picking a reference box,
we decide to keep the area inside the quadrilateral b0 b1 b2 b3 black, the area outside the rectangle
formed by `0 , `1 , `2 , `3 white, and the triangles in T0 gray, i.e., undecided for now.
Definition 4.3. For points x, y, let `(x, y) denote the line that passes through x and y. Let xy
denote the line segment between x and y and |xy| denote the length of xy.
Reference polygons are defined next. Intuitively, to obtain a reference polygon, we keep subdividing “gray” triangles in T0 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”). The main
recoloring operation from Definition 4.4 is illustrated in Figure 4.3. Even though the definition of
reference polygons is somewhat technical, the readers can check their understanding of this concept
by following Algorithm 2, as it chooses the best reference polygon to approximate the input image.
Definition 4.4 (Reference polygon). A 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 B0 and a triangle set T0 by the
following recursive process. Initially, Tend = ∅ and B = B0 . While T0 6= ∅, move a triangle T
from T0 to Tend and perform the following steps:
1. (Base Change). Let T = 4b0 b00 v, where b0 , b00 ∈ B. Select reference point b00 on b0 v w.r.t. line
`(b0 , v), and reference point b000 on b00 v w.r.t. line `(b00 , v). Add b00 , b000 to B. (This corresponds
to coloring the quadrilateral b0 b00 b000 b00 black.) Let h be the height of 4b00 b000 v w.r.t. the base b00 b000 .
2. (Subdivision Step) If h > 60 n, choose whether to proceed with this step or go to Step 3 (both
choices correspond to a legal reference polygon); otherwise, go to Step 3. Let ϕ be the angle
between `(b00 , b000 ) and the x-axis, and ϕ̂ ∈ D be such that |ϕ̂ − ϕ| ≤ 0 /2. Select a reference
line-point pair (`, b), where the line ` ∈ Lϕ̂ crosses b00 v and b000 v, whereas b is in the triangle
4b00 b000 v. Let v 0 (resp., v 00 ) be the point of intersection of ` and b00 v (resp., ` and b000 v). Let
T 0 = 4b00 bv 0 , T 00 = 4b000 bv 00 , as shown on Figure 4.3. Add b to B and triangles T 0 , T 00 to T0 .
(This represents coloring 4b00 b000 b black and keeping T 0 and T 00 gray.)
3. (End of Processing) Do nothing. (This represents coloring 4b00 b000 v white).
By Remark 2.1, to prove Theorem 4.1, it suffices to design a Bernoulli tester that takes s =
O( 12 log 1 ) samples in expectation and runs in time O( 18 ). Our Bernoulli tester is Algorithm 2.
In Algorithm 2, 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 0 , let
ˆ 0 ) = 1 · |{u ∈ S : M [u] 6= M 0 [u]}|. For every region R ⊆ [0..n)2 , we let dˆ+ (R) = 1 · |{u ∈
d(M
s
s
S ∩ R : M [u] = 0}|, and dˆ− (R) = 1s · |{u ∈ S ∩ R : M [u] = 1}|, i.e., the empirical error if we make
R black/white, respectively.
Subroutine Best, presented next, chooses the option with the smallest empirical relative error
among those given in Definition 4.4, items 1-3.
11

Algorithm 2: Bernoulli approximation algorithm for distance to convexity.
input : parameters n ∈ N,  ∈ (0, 1/4); Bernoulli access to an n × n binary matrix M .
1

2

3
4
5

6
7
8
9

10
11

Set s = Θ( 12 log 1 ). Include each image pixel in the sample S w.p. p = s/n2 .
ˆ the smallest fraction of samples
// Run the algorithm to find d,
misclassified by a reference polygon in P . A dynamic programming
implementation of the algorithm is given in Section 4.3.
Let W`0 (resp., W`2 ) be the set of pixels of the image M that lie either above `0 or to the
left of b0 on `0 (resp., either below `2 or to the left of b2 on `2 ). Let W`1 (resp., W`3 ) be the
set of pixels of M − W`0 − W`2 to the left of `1 (resp., to the right of `3 ). (See Figure 4.4)
Set dˆ = 1.
forall the line-point pairs (`0 , b0 ), (`2 , b2 ), where `0 , `2 are horizontal lines do
Set dˆleft = 1.
// The variable to compute the best error for the
region to the left of b0 b2 , between `0 and `2 .
foreach line-point pair (`1 , b1 ), where `1 is a vertical line do
Let v0 (resp., v2 ) be the point where `1 intersects `0 (resp., `1 intersects `2 ).
dˆleft = min(dˆleft , dˆ− (W`1 ) + dˆ+ (4b0 b1 b2 ) + Best(4b0 b1 v0 ) + Best(4b1 b2 v2 ))
Similarly to Steps 5–8, compute dˆright .
// The best error for the region to the right of b0 b2 , between `0 and `2 .
ˆ dˆ− (W` ∪ W` ) + dˆleft + dˆright ).
Compute dˆ = min(d,
0
2
ˆ
return d.

Algorithm 3: Subroutine Best used in Algorithm 2.
input : triangle 4b0 b00 v
1
2
3
4

// Use dynamic programming (see Section 4.3 for implementation details).
Set d∗ = 1.
forall the reference points b00 and b000 on the sides b0 v and b00 v, respectively, do
Compute d∗ = min(d∗ , d+ (b0 b00 b000 b00 ) + BestForFixedBase(b00 b000 v))
return d∗

Algorithm 4: Subroutine Best For Fixed Base used in Algorithm 3.
input : triangle 4b00 b000 v

4

Set d∗ = d− (4b00 b000 v)
if the height of 4b1 b2 v w.r.t. the base b1 b2 is more than 60 n then
foreach line-point pair (`, b), where ` ∈ Lϕ̂ (see Definition 4.4, item 2), b ∈ 4bb00 b000 ,
line ` intersects the side b00 v at some point v 0 and the side b000 v at some point v 00 , resp. do
Compute d∗ = min(d∗ , dˆ− (4v 0 v 00 v) + dˆ+ (4b0 b00 b) + Best(4b0 bv 0 ) + Best(4bb00 v 00 ))

5

return d∗

1
2
3

0 0

12

0

0

ℓ0

ℎ
𝑏0′

𝑏0

𝑊ℓ1

𝑣
𝑣′

𝑊ℓ0

𝑏

𝑊ℓ3

𝑏1
𝑣 ′′
𝑇′′

𝑏3

ℓ

ℓ1

𝑏0′′

𝑏 ′′

𝑏′

Figure 4.3: An illustration to Definition 4.4: Triangle
4b0 b00 v.

ℓ2

ℓ3

𝑅
𝑏2

𝑊ℓ2

Figure 4.4: Regions W`0 , W`1 , W`2 , and W`3 .

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 4.1. It turns out that the empirical error
for a region is proportional to the square root of its area. The second key featurePof our reference
p
polygons is that, for each of them, the set of considered triangles, Tend , has small T ∈Tend A(T ).
The proof of this fact, as well as the analysis of the empirical error appears in Section 4.2. Finally,
Section 4.3 completes the analysis of the algorithm, gives details of its implementation and presents
the corollary about agnostic PAC learning of convex objects.

4.1

Existence of a nearby reference polygon

Lemma 4.2. For every convex image M , there exists M 0 ∈ P such that dist(M, M 0 ) ≤ /6.
Proof. Consider a convex image M . We will show how to construct a nearby reference polygon M 0
using the recursive process in Definition 4.4. First, we obtain a reference box (see Definition 4.2)
for M as follows. Let (`0 , b0 ) be a line-point pair, where b0 is black in M and `0 is the topmost
horizontal line that contains such a reference point. Similarly, define (`2 , b2 ), replacing “topmost”
with “bottommost”. Analogously, define the two line-point pairs (`1 , b1 ), (`3 , b3 ) with vertical lines.
The four line-point pairs (`i , bi ) for i ∈ [0..4) define the reference box for M , as shown in Figure 4.5.
Next we construct the set B from the reference box, as in Definition 4.4. We also maintain two
sets of line segments, F1 and F2 , that are used in the analysis. Initially, F1 = F2 = ∅. 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 4.4 to obtain our reference polygon:
1. (Base Change) Choose b00 , b000 to be the furthest from b0 b00 black reference w.r.t. lines `(b0 , v)
and `(b00 , v), respectively. Recall that h is the height of 4b00 b000 v w.r.t. the base b00 b000 .
2. (Subdivision Step) If h > 60 n, let BM denote the convex hull of all black pixels in M and
points b01 , b001 be the intersection points of BM with b00 v and b000 v, respectively. Choose a linepoint pair (`, b) such that ` ∈ Lϕ̂ is the furthest from b01 b001 line that intersects b0 v and b00 v,
13

ℓ0
𝑏0

𝑇
𝑏1
𝑏3

ℓ1

𝑏2

𝑀

ℓ3

ℓ2
Figure 4.5: Reference box for a convex image M .
and b is black. Let ` intersect b0 v and b001 v at v 0 and v 00 , respectively and let it intersect BM
at y 0 and y 00 , as in Figure 4.6. Put the line segment y 0 y 00 in F1 and 4v 0 v 00 v in Tcut . If no line
in Lϕ̂ contains a black reference point in 4b01 b001 v or if h ≤ 60 n, go to Step 3.
3. (End of Processing) Put the line segment b01 b001 in F2 and 4b00 b000 v in Tfin . Triangle 4b00 b000 v is
not subdivided and is called a final triangle.
Observe that M and M 0 differ only on three types of regions: outside of the reference box,
2
inside the triangles in Tfin , and inside the triangles in Tcut . To show that Dist(M, M 0 ) ≤ n6 , we
prove in Claims 4.3, 4.4, and 4.7 that the number of disagreements in each of the three regions is
small. For any region R ⊆ [0..n)2 , let Err(R) = |{u ∈ R : M [u] 6= M 0 [u]}|.
Next claim follows from the analysis of the convexity tester in [21].
Claim 4.3. The number of black pixels in M outside the reference box is at most 12 · 0 n2 .
Claim 4.4. Let 4b00 b000 v be a final triangle and points b01 , b001 be the points of intersection of BM with
b00 v and b000 v, respectively. Then Err(4b00 b000 v) ≤ 4 · |b01 b001 |0 n + 2.
Proof. By Proposition 3.5, Err(4b00 b000 v) ≤ P ix(4b01 b001 v) ≤ A(4b01 b001 v) + P erim(4b01 b001 v)/2 + 1.
Note that ∠b01 vb001 is obtuse.
Proposition 4.5. Let T be a triangle with sides a, b and c. Let α be the angle opposite to side a,
and ha be the height w.r.t. base a in T . If α ≥ π/2 then ha ≤ a/2.
Proof. By the cosine theorem, a2 = b2 + c2 − 2bc · cos α ≥ b2 + c2 ≥ 2bc ≥ 4 · A(T ) = 2 · a · ha .
Thus, ha ≤ a/2, as claimed.
If h ≤ 60 n then by Proposition 4.5, the area A(4b01 b001 v) ≤ 3·|b01 b001 |0 n. Since P erim(4b01 b001 v) ≤
3 · |b01 b001 | we obtain that A(4b01 b001 v) + P erim(4b01 b001 v)/2 + 1 ≤ 3 · |b01 b001 |0 n + 1.5 · |b01 b001 | + 1 ≤
14

𝑣

𝑦′

𝑦 ′′

ℓ

ℎ
𝑏1′′

𝑏1′

𝑏0′

𝑏0′′
Figure 4.6: An illustration to Subdivision Step in 4b00 b000 v.

𝑣
𝑣
𝑦′

𝑦 ′′

ℓ
𝑏1′′

𝑏1′
𝑏0′

𝑏0′′
Figure 4.7: An illustration of triangle 4y 0 y 00 v̂.

4 · |b01 b001 |0 n + 2 and the claim holds (recall that  = Ω(1/n)). Now assume that h > 60 n and no
line in Lϕ̂ with a black reference point intersects the line segments b01 v and b001 v in 4b00 b000 v.
Proposition 4.6. Let 4b00 b000 v be a triangle in which ∠b00 vb000 is obtuse and BM intersects the sides
b00 v and b000 v. Let ` ∈ Lϕ̂ be a line that intersects BM at y 0 and y 00 , and it intersects b00 v and b000 v at
0 00 2
0 00
v 0 and v 00 , respectively. See Figure 4.7. Then Err(v 0 v 00 v) ≤ |y y4 | + 3|y2y | + 1.
Proof. Let v̂ be a point (inside 4b00 b000 v) such that `(y 0 , v̂) is parallel to `(b00 v) and `(y 00 , v̂) is parallel
to `(b000 v). Since BM is convex, the portion of BM in 4v 0 v 00 v is entirely inside 4y 0 y 00 v̂. Angle
0 00 2
∠y 0 v̂y 00 is obtuse since ∠y 0 v̂y 00 = ∠b00 vb000 . Then by Proposition 4.5, A(4y 0 y 00 v̂) ≤ |y y4 | . Note that
P erim(4y 0 y 00 v̂) ≤ 3|y 0 y 00 |. Since Err(v 0 v 00 v) ≤ P ix(4v 0 v 00 v) then by Proposition 3.5, Err(v 0 v 00 v) ≤
0 00
|y 0 y 00 |2
+ 3|y2y | + 1.
4
Let ` ∈ Lϕ̂ be the line that does not intersect the line segment b01 b001 and that is closest to
it. Let ` intersect the line segments b01 v and b001 v at v 0 and v 00 . Then either ∠v 0 v 00 v ≤ ∠b00 b000 v or
∠v 00 v 0 v ≤ ∠b000 b00 v. W.l.o.g. assume that ∠v 0 v 00 v ≤ ∠b00 b000 v. Let `ˆ be the line that is parallel to `
and that passes through point b000 as shown in Figure 4.8. Let v10 be the intersection point of `ˆ and
the line segment b00 v. Denote the angle between `ˆ and `(b00 , b000 ) by γ. The distance between ` and `ˆ

15

𝑣
𝑣′
𝑣 ′′
𝑣1′

ℓ
𝑏1′′

𝑏1′

𝛾

𝑏0′

ℓ

𝑏0′′

Figure 4.8: An illustration of line `ˆ in 4b00 b000 v.
is at most 20 n. Otherwise there are two distinct lines from Lϕ̂ that pass through the line segment
b000 b001 . Since |b000 b001 | ≤ 0 n the distance between the two lines is less than 0 n, contradiction.
Now we find an upper on the number of black pixels in 4b00 b000 v. Let BM intersect ` at y 0 and
2
y 00 . Then |y 0 y 00 | ≤ 0 n. By Proposition 4.6, P ix(4v 0 v 00 v) ≤ (04n) + 320 n + 1. The number of black
pixels in the rectangle b00 b000 v 00 v 0 is at most P ix(b00 b000 v 00 v 0 ). The area
A(b00 b000 v 00 v 0 ) = A(v10 b000 v 00 v 0 ) + A(4b00 b000 v10 ) ≤ 20 n|v10 b000 | + A(4b00 b000 v10 ) ≤ 2|b00 b000 |0 n + A(4b00 b000 v10 ).
The last inequality holds since ∠b00 v10 b000 is obtuse. Let d1 (resp., d2 ) denote the distance from the
point v 0 (resp., v10 ) to the line `(b01 , b001 ). We find an upper bound on A(4b00 b000 v10 ):
A(4b00 b000 v10 )

√
|b00 b000 | · d2
|b00 b000 | · |b000 v10 | · sin γ
|b00 b000 | · 2n(0 /2)
=
=
≤
< 0.4|b00 b000 | · 0 n.
2
2
2

Thus, A(b00 b000 v 00 v 0 ) ≤ 2.4 · |b00 b000 |0 n. The height h ≤ d1 + 0 n. By Proposition 4.5, if |b01 b001 | ≤ 100 n
then d1 ≤ 50 n. It implies that h ≤ 60 n, contradiction. Therefore, |b01 b001 | > 100 n. By the triangle
inequality |b00 b000 | ≤ |b01 b001 | + 20 n. Thus,
A(b00 b000 v 00 v 0 ) ≤ 2.4 · (|b01 b001 | + 20 n)0 n ≤ 3 · |b01 b001 |0 n.
The last inequality holds since |b01 b001 | > 100 n. Note that
P erim(b00 b000 v 00 v 0 )/2 ≤ 2 · |b00 b000 | ≤ 2|b01 b001 | + 40 n.
Thus, by Proposition 3.5,
P ix(b00 b000 v 00 v 0 ) ≤ 3 · |b01 b001 |0 n + 2|b01 b001 | + 40 n + 1
and
Err(4b00 b000 v) ≤ P ix(b00 b000 v 00 v 0 )+P ix(4v 0 v 00 v) ≤ 3·|b01 b001 |0 n+2|b01 b001 |+40 n+1+

(0 n)2 30 n
+
+1 ≤
4
2

≤ 4 · |b01 b001 |0 n + 2.
The last inequality holds since |b01 b001 | > 100 n. This completes the proof of Claim 4.4.
16

Claim 4.7. Let triangle 4b00 b000 v and line ` be as defined in Step 2 of the recursive construction of
M 0 . Let v 0 and v 00 denote the points of intersection of ` and b00 v and b000 v, respectively. Let y 0 and
y 00 be the points of intersection of BM and `. Then Err(4v 0 v 00 v) ≤ 4 · |y 0 y 00 |0 n + 2.

𝑣

𝑣′

𝑦′

𝑏
𝑦′′

ℓ′
ℓ

𝑣 ′′

𝑏0′′

𝑏0′
Figure 4.9: An illustration of line `0 in triangle 4b00 b000 v.
0 00 2

0 00

Proof. If |y 0 y 00 | ≤ 0 n then, by Proposition 4.6, Err(4v 0 v 00 v) ≤ |y y4 | + 3|y2y | + 1 ≤ 4 · |y 0 y 00 |0 n + 2.
Now assume that |y 0 y 00 | > 0 n. Let `0 ∈ Lϕ̂ be the line at distance 0 n from ` closer to v, as in
Figure 4.9. Let `0 intersect b00 v and b000 v at v10 and v100 , respectively. Then Err(v 0 v10 v100 v 00 ) is at most
the number of black pixels in v 0 v10 v100 v 00 . Note that all black pixels in v 0 v10 v100 v 00 are inside a rectangle
with length |y 0 y 00 |. Thus, by Proposition 3.5, the number of black pixels in v 0 v10 v100 v 00 is at most
|y 0 y 00 |0 n + 2|y 0 y 00 | + 1. The distance between the points of intersection of BM with `0 is at most
0 n. Thus, by Proposition 4.6,
Err(v 0 v 00 v) ≤ |y 0 y 00 |0 n + 2|y 0 y 00 | + 1 +

(0 n)2 30 n
+
+ 1 ≤ 4 · |y 0 y 00 |0 n + 2.
4
2

The last inequality holds since |y 0 y 00 | > 0 n. This completes the proof of Claim 4.7.
Observe that all points in B lie on the boundary of a convex polygon. Images M and M 0 differ
only on pixels outside of the reference box and inside the triangles 4b01 b001 v and 4v 0 v 00 v. All the
line segments in F1 ∪ F2 are the sides of a convex polygon which is inside an n × n square. Thus,
the sum of the lengths of the line segments in F1 ∪ F2 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
T0 , every triangle is subdivided into at most two new triangles. Fix a triangle T ∈ T0 . Consider a
binary tree BT rooted at T , where every node is some triangle obtained during the reference polygon
construction and every triangle in BT 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 BT and we need
to assume that the tree is full. Recall 4b00 b000 v and h from the construction of a reference polygon.
Triangle 4b00 b000 v is not subdivided if h ≤ 60 n. By Proposition 4.5, if A(4b00 b000 v) ≤ 36(0 n)2 then
h ≤ 60 n. Thus, a triangle is not subdivided if its area drops below 36(0 n)2 . Note that every
triangle in T0 has area at most n2 . Consider a triangle T1 in BT with two children T10 and T100 . Let
k be the height of BT . By Claim 4.9, max{A(T10 ), A(T20 )} ≤ 32 A(T1 ). Thus, every triangle in level
17

i ∈ [k] of BT has area at most (2/3)i n2 . The area of every triangle in level k − 1 of BT is at least
36(0 n)2 (otherwise, non of the triangles in this level is subdivided and the height of BT cannot be
k). We obtain that (2/3)k−1 n2 ≥ 36(0 n)2 and thus, k ≤ 5 · ln 30
 . Therefore, the number of leaves
k
−1/5
in BT is at most 2 ≤ n/4 (recall that  > n
) and |Tfin | ≤ 4 · (n/4) = n. By Claims 4.3, 4.4
and 4.7,
X
X
|y 0 y 00 |)·40 n+120 n2 +2|Tfin | ≤ 260 n2 +2n ≤ 270 n2 .
|b01 b001 |+·
Dist(M, M 0 ) ≤ (
0 00
0 00
y y ∈F1

b1 b1 ∈F2

This completes the proof of Lemma 4.2.

4.2

Error analysis

Lemma 4.8. For each set Tend obtained in the construction of a reference polygon in Definition 4.4,
X p
A(T ) < 11n.
T ∈Tend

𝑣
𝑟𝑦

𝑞𝑥
𝑣′ 𝑡-𝑡𝑧
𝑇′
𝑏0′

𝑏

𝑡𝑧
𝑇 ′′

𝑣 ′′ ℓ

𝛽

𝛼

𝑏0′′

Figure 4.10: Triangle 4b00 b000 v.
Proof. All triangles in Tend are obtained by partitioning the four initial triangles in T0 . The
following claim analyzes how the area is affected by one step of partitioning.
Claim 4.9. Let T 0 and T 00 be two gray triangles
q obtained from a triangle T in Subdivision Step of
p
p
0
00
Definition 4.4. Then A(T ) + A(T ) ≤ 23 · A(T ).
p
p
Proof. Observe that A(T 0 ) + A(T 00 ) is maximized when b00 = b0 and b000 = b00 . W.l.o.g. we prove
the lemma for this case. We use notation from Figure 4.10. Recall that a √
triangle T is partitioned
only if its height h ≥ 60 n. Since the sides of T are of length at most 2n, the height is that
large only if both angles adjacent to the base b00 b000 are greater than 40 . (To see this,
√ consider an
angle α between
the
base
and
a
side
of
length
a.
We
get
6
n
≤
h
=
a
·
sin
α
≤
2n · α. Thus,
0
√
α ≥ 60 / 2 > 40 .)
p
p
First, we find the maximum value of A(T 0 ) + A(T 00 ) for a fixed line ` on which position
of point b varies. Let α = ∠b000 b00 v, β = ∠b000 b00 v and γ be the angle between lines ` and `(b00 , b000 ).
W.l.o.g. assume that ∠v 0 v 00 v ≤ β. Then ∠v 00 v 0 v = α + γ and ∠v 0 v 00 v = β − γ. By the construction
18

of triangles in Tend , α + β ≤ π2 and γ ≤ 20 . Let q = |b00 v|, r = |b000 v|, t = |v 0 v 00 | and qx = |v 0 v|,
ry = |v 00 v|, tz = |bv 00 | (x, y, z ∈ [0, 1]). Let
r
r
p
p
q(1 − x) · t(1 − z) sin(α + γ)
r(1 − y) · tz sin(β − γ)
0
00
f (z) = A(T ) + A(T ) =
+
.
2
2
p
√
00 00 0
Thus, f (z) = C1 · (1 − z) + C2 · z, wherepC1 = A(4b00 v 0 v√00 ), C2 = A(4b
p 0 v v ) are constants.
By the Cauchy-Schwarz inequality, f (z) = C1 · (1 − z) + C2 · z ≤ (C1 + C2 )(1 − z + z) =
√
C1 + C2 .
Next, we find the maximum value of C1 + C2 varying position of ` inside T . We use the fact
that
(q − qx)ry · sin(α + β)
,
C1 = A(4b00 v 00 v) − A(4v 0 v 00 v) =
2
(r − ry)qx · sin(α + β)
C2 = A(4b000 v 0 v) − A(4v 0 v 00 v) =
2
to obtain
(x + y − 2xy)qr · sin(α + β)
C1 + C2 =
= (x + y − 2xy)A(T ).
2
β sin(α+γ)
We need to show that x + y − 2xy ≤ 2/3. Let ĉ = xy = sin
sin α sin(β−γ) . Since ĉ is constant and the
geometric mean of two numbers is at most their arithmetic mean
r
√
√
p
1 + ĉ
1
1 + ĉ
1 + ĉ
x + y − 2xy = 2ĉ · x(
− x) ≤ 2ĉ · · (x +
− x) = √ .
2ĉ
2
2ĉ
8ĉ
2

≤ 32 which is equivalent to (3ĉ − 1)(ĉ − 3) ≤ 0. The latter inequality holds if
We prove that (1+ĉ)
8ĉ
1 ≤ ĉ ≤ 3. Function sin θ is increasing on [0, π/2] thus, 1 ≤ ĉ. Now we show that ĉ ≤ 3. If γ = 0
the inequality holds. Let us assume that γ > 0. We need to prove that
sin β sin(α + γ)
cot γ + cot α
=
≤ 3.
sin α sin(β − γ)
cot γ − cot β
Function cot θ is decreasing on (0, π/2] thus,
cot γ + cot α
cot γ + cot 40
cot γ + cot 0
≤
≤
≤ 3.
cot γ − cot β
cot γ − cot 40
cot γ − cot 0
The last inequality is equivalent to 2 cot 0 ≤ cot γ which is true since 2 cot 0 ≤ cot 20 ≤ cot γ.
This completes the proof of Claim 4.9
P
Let A1 , . . . , A4 be the areas of the first four triangles in T0 . Then 4i=1 Ai ≤ n2 . By construction
of triangles in Tend , Claim 4.9, and concavity of the square root function,
4
X p
X
p
p
A(T ) ≤ K ·
Aj ≤ 2K A1 + A2 + A3 + A4 ≤ 2K · n,
T ∈Tend

where K =

P∞

j=1

p
p
2/3)m = (1 − 2/3)−1 < 5.5. This completes the proof of Lemma 4.8.

m=0 (

19

Let M be an input image, S be the set of samples obtained by the algorithm, and s be the
ˆ 0 ) = 1 · |{u ∈ S :
parameter in the algorithm. For any image M 0 , let d(M 0 ) = dist(M, M 0 ) and d(M
s
1
0
2
0
M [u] 6= M [u]}|. Also, for any region R ⊆ [0..n) , let d(M |R ) = n2 · |{u ∈ R : M [u] 6= M 0 [u]}| and
ˆ 0 |R ) = 1 · |{u ∈ S ∪ R : M [u] 6= M 0 [u]}|.
d(M
s
Lemma 4.10. With probability at least 2/3 over the choice of the samples taken by Algorithm 2,
ˆ 0 ) − dist(M, M 0 )| ≤ 5/6 for all reference polygons M 0 .
|d(M
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 dˆ+ (R+ ) + dˆ− (R− ). Let R be the set of all such regions R. We will show that with
probability at least 2/3, the estimates dˆ+ (R+ ) + dˆ− (R− ) are accurate on all regions in R.
Fix R = (R+ , R− ) ∈ R. Let Γ 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 γ = |Γ|/n2 . Algorithm 2 approximates
γ by dˆ+ (R+ ) + dˆ− (R− ) = 1s |Γ ∩ S|. Equivalently, it uses the estimate p1 |Γ ∩ S| for |Γ| (recall that
p = s/n2 ). The error of the estimate is errS (R) = p1 |Γ ∩ S| − |Γ|.
√
Claim 4.11. Pr[|errS (R)| > γ · cn2 ] ≤ 2 exp(− 38 c2 2 s), where c = 1/21.
Proof. For each pixel u, we define random variables χu and Xu , where χu is the indicator random
variable for the event u ∈ S (i.e., a Bernoulli variable P
with the probability parameter
P p), whereas
χu
1
1
Xu = p − 1. Then our estimate of |Γ| is p |Γ ∩ S| = p u∈Γ χu , whereas errS (R) = u∈Γ Xu . We
√
useP
Bernstein inequality (Theorem 4.13) with parameters m = γn2 and z = γ · cn2 to bound
√
Pr[ u∈Γ Xu > γ · cn2 ]. The variables Xu are identically distributed. The maximum value of
2 ] = 1 E[(χ − p)2 ] = 1 Var[χ ] = 1−p = a. We assume w.l.o.g.
|Xu | is a = 1−p
u
u
p . Note that E[X
p
p2
p2
Pu
that z < |Γ|. (If z ≥ |Γ| then u∈Γ Xu can never exceed z, and the probability we are bounding is
0.) By Bernstein inequality,
"
#






X
−z 2 /2
3 z2 · p
3 γ · c2 2 n4 s
Pr
Xu > z
≤ exp
< exp − ·
= exp − ·
· 2
a|Γ| + a · z/3
8 |Γ|
8
γn2
n
u∈Γ

3
= exp(− c2 2 s).
8
The second inequality holds because a < 1/p and z < |Γ|. The equalities are obtained by
substituting the expressions for z, |Γ|, and p, and simplifying. By symmetry, Pr[|errS (R)| ≥ z] ≤
2 exp(− 83 c2 2 s).
Claim 4.12. The number of regions in R is at most 50/0 8 .
Proof. Let k = 1/0 . There are four types of regions in R, each corresponding to a different call
of the form dˆ+ (R+ ) + dˆ− (R− ) in the algorithm. Thefirst type is a horizontal double strip of the
form R+ = ∅ and R− = W`0 ∪ W`2 . There are k+1
such strips. The second type is where R+
2
is a black triangle 4b0 b1 b2 (or 4b0 b3 b2 ) and R− is a vertical strip W`1 (respectively, W`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. Regions
of type 3 are black quadrilaterals of the form R+ = b00 b000 b0 b00 . Each quadrilateral is defined by two
20

reference lines, b0 b00 and b00 b000 , with two reference points on each. There are

πk
2



ways to choose
√ 
reference directions for the two lines. For each of them, there are at most 2k · 22k ways to
choose a reference line and two reference points. Overall, the number of quadrilaterals in R is at
most π 2 k 8 . Finally, regions of type 4 are contained in triangles of the form 4vb00 b000 ; they are of
the form either R+ = ∅, R− = 4vb00 b000 or R+ = 4bb00 b000 , R− = 4vv 0 v 00 . In the former
case, regions

are defined by two line-point pairs (`(b00 , v), b00 ) and (`(b000 , v), b000 ). There are πk
pairs
of reference
2
√
√
directions. For each of them, there are at most 2k choices for each reference line and 2k choices
for each reference points. In the latter case, they are defined by three reference line-point pairs:
0 , v 00 ), b), but the direction of the line through v 0 v 00 is determined
(`(b00 , v), b00 ), (`(b000 , v), b000 ), and (`(v

by b00 , b000 . As before, there are πk
of reference directions. For each of them, there are at most
2 pairs √
√
2k choices for each reference line and 2k choices for each reference points. Overall, the number
of regions of type 4 is upper-bounded by 4π 2 k 8 . Overall, |R| ≤ (5π 2 + .5)k 8 < 50k 8 = 50/0 8 , as
claimed.
√

By taking a union bound over all regions in R and applying Claims 4.11–4.12, we get that the
probability that for one or more of them the error is larger than stated in Claim 4.11 is at most
|R| · 2 exp(− 38 c2 2 s) ≤ 100
· exp(− 38 c2 2 s) ≤ 1/3, where the last inequality holds provided that
0 8
1
1
s ≥ C 2 ln  for some sufficiently large constant C. We get that
√
Pr[|errS (R)| ≤ γ · cn2 for all R ∈ R] ≥ 2/3.
(1)
Now suppose that event in (1) holds, that is, the error is low for all regions. Fix a reference
polygon M 0 . Consider the partition of M 0 into regions from R = (R+ , R− ) ∈ R on which Algoˆ 0 ). Let RM 0 ⊂ R be the set
rithm 2 evaluates dˆ+ (R+ ) + dˆ− (R− ) while implicitly computing d(M
of regions in the partition. Recall the four types of regions from the proof of Claim 4.12. Then
RM 0 contains one region of type 1 and two regions of type 2, defined by the reference box of M 0 .
Denote their areas by A01 , A02 , A03 . For each triangle T ∈ Tend created during the construction of
M 0 in Definition 4.4, the set RM 0 contains at most one region of type 3 and at most one region of
type 4. They were implicitly colored, respectively, in Item 1 and Items 2-3 of Definition 4.4, when
triangle T was processed. Let AT and A0T 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). Since the
event in (1) holds,
errS (M 0 ) ≤

X

errS (R) ≤ cn

R∈RM 0

Since

P3

3 q
q
X p
X
X p

A(R) ≤ cn
A0j +
( AT + A0T ) .
j=1

R∈RM 0

T ∈Tend

0
j=1 Aj

≤ n2 and AT +A0T ≤ A(T ) for all T ∈ Tend , by concavity of the square root function,
v
u 3
3 q
q
q
X
p
p
u X
√
0
Aj ≤ t3
A0j ≤ 3n and AT + A0T ≤ 2(AT + A0T ) ≤ 2A(T ).
j=1

j=1

We substitute these expressions in the previous inequality, use Lemma 4.8 and recall that c = 1/21:
errS (M 0 ) ≤ cn

√

3n +

√

2

X p
√
√

5
A(T ) ≤ cn2 ( 3 + 11 2) ≤ n2 .
6

T ∈Tend

21

This holds for all reference polygons M 0 as long as the event in (1) happens, i.e., with probability
at least 2/3. This completes the proof of Lemma 4.10.
For completeness, we state Bernstein’s inequality, which was used in the proof of Lemma 4.10.
Theorem 4.13 (Bernstein’s inequality). Let X1 , . . . , Xm be m independent zero-mean random
variables, where |Xi | ≤ a for all i ∈ [m]. Then for all positive z,
"m
#


X
z 2 /2
.
Pr
Xi > z ≤ exp − Pm
2
i=1 E[Xi ] + a · z/3
i=1

4.3

Wrapping up: proof of Theorem 4.1 and corollary on agnostic learning

Analysis of Algorithm 2. Let dM be the distance of M to convexity. Then there exists a
convex image M ∗ such that dist(M, M ∗ ) = dM . By Lemma 4.2, there is a reference polygon M̂ such
that dist(M ∗ , M̂ ) ≤ /6, and consequently, dM ≤ dist(M, M̂ ) ≤ dM + /6. By Lemma 4.10, with
ˆ 0 )−dist(M, M 0 )| ≤
probability at least 2/3 over the choice of the samples taken by Algorithm 2, |d(M
0
5/6 for all reference polygons M . Suppose this event happened. Then dˆ ≥ dM − 5/6 because
ˆ M̂ ) ≤ dist(M, M̂ ) + 5/6 ≤ dM + .
dist(M, M 0 ) ≥ dM for all convex images M 0 . Moreover, d(
ˆ
ˆ
ˆ
Thus, dM − 5/6 ≤ d ≤ d(M̂ ) ≤ dM + . That is, |dM − d| ≤  with probability at least 2/3, as
required.
Sample and time complexity of Algorithm 2. The number of samples taken by the
algorithm is s = O(−2 log −1 ).
Next we explain how to implement it to run in time O(−8 ). Refer to Figure 4.3. Each instance
triangle 4b0 b00 v of the dynamic programming in subroutine Best is specified by two line-point pairs:
(`(b0 , v), b0 ), (`(b00 , v), b00 ). The number of line-point pairs is O(−3 ) because for each we select the
reference direction, the shift of the line, and the reference point, each in O(−1 ) ways. Hence, we
have O(−6 ) entries in the dynamic programming table for Best.
In the process of solving an instance of Best, we consider O(−2 ) possibilities for points b00 , b000 ,
that is, O(−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 4.3 in amortized time O(1).
First, we show how to do it for the entire triangle 4b0 b00 v. We have O(−6 ) triangles that can
be partitioned into O(−5 ) groups by specifying the first line-point pair (`(b0 , v), b0 ) and the second
line (through b00 and v). That is, within each group, we vary only point b00 on the second line.
We sort all sample points p ∈ S according to the angle of the segment pb0 . Similarly, we sort the
reference points b00 on the second line according to the angle of the segment b00 b0 . After sorting,
a single scan can establish the counts of white and black pixels in the triangles. Clearly, we can
sort in time o(−3 ). Thus, we compute white/black counts for all instance triangles of Best in time
o(−8 ).
When we consider a possibility in Best, the triangle 4b00 b000 v is also an instance triangle, so we
can find the white/black counts for the quadrilateral b0 b00 b000 b00 by computing the difference between
the counts for entire triangle 4b0 b00 v and triangle 4b00 b000 v, that is, in time O(1).
When we consider a possibility in subroutine Best For Fixed Base, we need the counts for the four
parts of 4b00 b000 v. Since we already calculated the counts for 4b00 b000 v and because we can perform

22

subtractions, it is enough to do it for three parts. Two of them, 4b00 bv 0 and 4b000 bv 00 , are instance
triangles for Best, so we already calculated their counts. The third we choose is the triangle 4v 0 v 00 v.
Note that this triangle is specified by three reference lines, so there are O(−6 ) such triangles. We
make a table for all of them. To fill the table, we consider O(−5 ) groups: we group together
triangles for which line ` has a common direction. By sorting samples in S, we can compute the
counts for each group in time o(−3 ). Thus, the time for filling the second table is o(−8 ). To
summarize, Algorithm 2 runs in time O(−8 ). This completes the proof of Theorem 4.1.
Corollary 4.14. The class of convex images is properly agnostically PAC-learnable with sample
complexity O( 12 log 1 ) and time complexity O( 18 ) under the uniform distribution.
ˆ a reference polygon M̂ with d(
ˆ M̂ ) = d.
ˆ
Proof. We can modify Algorithm 2 to output, along with d,
With an additional DP table, we can compute which points became its vertices. By the analysis of
Algorithm 2, with probability at least 2/3, the output M̂ satisfies dist(M, M̂ ) ≤ dM + .

5

Distance Approximation to the Nearest Connected Image

To define connectedness, we consider the image graph GM of an image M . The vertices of GM are
{(i, j) | M [i, j] = 1}, and two vertices (i, j) and (i0 , j 0 ) are connected by an edge if |i−i0 |+|j−j 0 | = 1.
In other words, the image graph consists of black pixels connected by the grid lines. The image is
connected if its image graph is connected.
Theorem 5.1. There is a block-uniform -additive distance approximation
algorithm for connect
edness with sample complexity O( 14 ) and running time exp O 1 .

5.1

Border Connectedness

The first idea in our algorithms for connectedness is that we can modify an image in a relatively
few places by superimposing a grid on it (as shown in Figures 5.1 and 5.2), 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.
For a set S ⊂ [0..n)2 and (i, j) ∈ [0..n)2 , we define S + (i, j) = {(x + i, y + j) : (x, y) ∈ S}.
Definition 5.1 (Squares and grid pixels). Fix a side length n ≡ 1 (mod r). For all integers
i, j ∈ [0..n − r), where i and j are divisible by r, the (r − 1) × (r − 1) image that consists of all
pixels in [r − 1]2 + (i, j) is called an r-square of M . The set of all r-squares of M is denoted Sr .
The pixels that do not lie in any squares of Sr , i.e., pixels (i, j) where i or j is divisible by r,
are called grid pixels. The set of all grid pixels is denoted by GPr .
Claim 5.2. |GPr | ≤ 2n2 /r.
n−1
2
2
Proof. |GPr | = 2( n−1
r + 1)n − ( r + 1) ≤ 2n /r.

Note that a square consists of pixels of an r-block, 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 2.

23

𝑟-1
Figure 5.2:
from M .

Figure 5.1: An image M .

A gridded image obtained

Definition 5.2 (Border connectedness). A (sub)image S is border-connected if for every black
pixel (i, j) of S, the image graph GS contains a path from (i, j) to a pixel on the border. The
property border connectedness, denoted C 0 , is the set of all border-connected images.

5.2

Proof of Theorem 5.1

The main idea behind Algorithm 5, used to prove Theorem 5.1, is to relate the distance to connectedness to the distance to another property, which we call grid connectedness. The latter distance
is the average over squares of the distances of these squares to border connectedness. The average
can be easily estimated by looking at a sample of the squares.
W.l.o.g. assume that n ≡ 1 (mod 4/). (Otherwise, we can pad the image with white pixels
without changing whether it is connected and adjust the accuracy parameter.)
Algorithm 5: Distance approximation to connectedness.
input : n ∈ N and  ∈ (0, 1/4); block-sample access to an n × n binary matrix M .
1

2

3

Sample s = 4/2 squares uniformly and independently from S4/ (see Definition 5.1).
// This can be done by drawing random blocks from the 4/-partition of [0..n)2 .
For each such square S, compute dist(S, C 0 ) (see Section 5.3 for details), where C 0 is border
connectedness (see Definition 5.2). Let dˆsquares be the average of computed distances
dist(S, C 0 ).
2
return dˆ = (1 −  )(1 − 1 ) · dˆsquares .
4

n

Definition 5.3. Fix  ∈ (0, 1/4). Let image M be a gridded image obtained from image M as
follows:
(
1
if (i, j) is a grid pixel from GP4/ ;
M [i, j] =
M [i, j] otherwise.

24

Let C be the set of all connected images. For  ∈ (0, 1/4), define grid connectedness C = {M |
M ∈ C, and M [i, j] = 1 for all (i, j) ∈ GP4/ }.
Lemma 5.3. Let dM = dist(M, C) and d = dist(M , C ). Then dM −
d =



1−


2

≤ d ≤ dM . Moreover,

X
1
1  2

·
1−
dist(S, C 0 ).
4
n
|S4/ |
S∈S4/

Proof. First, we prove that d ≤ dM . Let M 0 be a connected image such that dist(M, M 0 ) = dM .
Then M0 , the gridded image obtained from M 0 , satisfies C . Since dist(M , M0 ) ≤ dM , it follows
that d ≤ dM .
Now we show that dM − 2 ≤ d . Let M00 ∈ C be such that dist(M , M00 ) = d . Then M00 ∈ C
and, by Claim 5.2, dist(M, M00 ) ≤ |GP4/ |/n2 + d ≤ /2 + d , implying dM ≤ /2 + d , as required.
Finally, observe that to make M satisfy C , it is necessary and sufficient to ensure that each
square satisfies C 0 . In other words,
X
X
d n2 =
Dist(S, C 0 ) = (4/ − 1)2
dist(S, C 0 ).
S∈S4/

S∈S4/

2
Since |S4/ | = ( n−1
4/ ) , the desired expression for d follows.

dist(S, C 0 ). Recall that dˆsquares is
the empirical average computed by the algorithm. By the Chernoff-Hoeffding bound, Pr[|dˆsquares −
dsquares | > /2] ≤ 2 exp(−22 s) ≤ 1/3. So, with probability at least 2/3, we have |dˆsquares −
dsquares | ≤ /2. If this event happens then |dˆ − d | ≤ /2 because by Algorithm 5 and Lemma 5.3,
2
respectively, dˆ = A · dˆsquares and d = A · dsquares , where A = (1 − 4 )(1 − n1 ) ≤ 1. By Lemma 5.3,
|d − | ≤ /2. Thus, |dˆ− | ≤ |dˆ− d | + |d − | ≤ /2 + /2 =  holds with probability at least 2/3,
as required.
Analysis of Algorithm 5. Let dsquares =

1
|S4/ |

P

S∈S4/

Query and time complexity. Algorithm 5 samples O(1/2 ) squares containing O(1/2 )
pixels each. Thus, the sample complexity is O(1/4 ).
The most expensive step in Algorithm 5 is Step 2 where the distance of a square S to border
connectedness is calculated.
By Theorem 5.4 (see section 5.3), the running time of this step for one

1
2
square is exp
 O  and it is called O(1/ ) times. Therefore, the running time of Algorithm 5 is
1
exp O  , as claimed.

5.3

Algorithm for Border Connectedness

Theorem 5.4. Let S be a k × k image. There is an algorithm that computes dist(S, C 0 ) (i.e.,
distance of S to border connectedness) in time exp (O(k)).
Proof. To prove the theorem we give a dynamic programming algorithm that computes dist(S, C 0 )
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.

25

Definition 5.4. Let cl ∈ {0, 1}k be a vector. Call maximal consecutive runs of 1’s in cl 1-blocks
and let n(cl) denote the number of 1-blocks in cl. Let 1t (respectively, 0t ) denote the string of t
ones (respectively, zeros) and let Σ = {0, 1, <, ×, >}.
Consider a k × k image S. Recall that GS denotes the image graph of S. For every i ∈ [k],
denote the subgraph of GS , induced by the first i rows in S, by GiS . 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. GiS :
• connected to the border of S (denoted by 1);
• isolated, i.e., not connected to the border and to any other 1-block in its row (denoted by 0);
• 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 <);
• intermediate 1-block in its connected component, i.e., has neither largest nor smallest index
in its connected component (denoted by ×);
• 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 >).
Definition 5.5. Let cl denote the coloring of S in row i, for some i ∈ [k] (i.e., cl = S[i]). Statuses
of 1-blocks of cl w.r.t. GiS are captured by a status vector st ∈ Σn(cl) . The pair (cl, st) is called the
configuration w.r.t. GiS .
Definition 5.6. For all i ∈ [k], cl ∈ {0, 1}k , and vectors st over Σ of length at most k, define
B(i, cl, st) = {S 0 | S 0 is a k × k border-connected image with configuration (cl, st) w.r.t. GiS 0 }.
For all i ∈ [k] and k × k images S 0 , let costi (S, S 0 ) denote the number of pixels on which the
first i rows of S and S 0 differ. For all i ∈ [k], cl ∈ {0, 1}k , and st ∈ Σk define
(
minS 0 ∈B(i,cl,st) (costi (S, S 0 )) if B(i, col, st) 6= ∅,
cost(i, col, st) =
∞
otherwise.
Note that the number of all possible configurations for a row is at most 2k · 5k = exp(k). We show
that if for some i ∈ [k − 1], the value of cost(i, cl, st) is known for every configuration (cl, st) in row
i, then for every configuration (cl0 , st0 ) in row i + 1, the cost cost(i + 1, cl0 , st0 ) 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 ∈ [k − 1], consider an image S 0 ∈ B(i, cl, st). Let S 00 be an image which has the
same j ∈ [i] rows as S 0 . Let cl0 denote the coloring of row i+1 in S 00 . If S 00 is border-connected then
configuration (cl, st) is consistent with coloring cl0 , i.e., every 1-block in cl that has status other
than 1 w.r.t. GiS 00 is connected to a 1-block in cl0 w.r.t. Gi+1
S 00 . Moreover, for some status vector
0)
n(cl
00
0
0
0
0
st ∈ Σ
, image S ∈ B(i+1, cl , st ) and st can be determined from cl, cl0 , and st. Observe that
if cost(i, cl, st) is known for every configuration (cl, st), then cost(i + 1, cl0 , st0 ) can be computed.
After computing costs for all configurations in each row, dist(S, C 0 ) = mincl,st cost(k, cl, st) can
be found. In order to find st0 , our algorithm uses subroutine ComputeStatus. ComputeStatus uses
26

subroutine ConstructGraph that creates a graph whose nodes are 1-blocks of cl and edges are defined
according to the information provided by st. Now we explain how st0 is found.
Now we show how subroutine ComputeStatus computes st0 from colorings col,col0 , and the status
vector st ∈ Σnum(col) of col w.r.t GiI , where I is an image from B(i, col, st) for i ∈ [k − 1]. Let
n1 = num(col) and n2 = num(col0 ). Index 1-blocks in col in the nondecreasing order of indices of
pixels they contain. Let I 0 be an image obtained from I by recoloring its row i + 1 to col0 . Index
1-blocks in col0 in the nondecreasing order of indices of pixels they contain and add n1 to each
index. Consider graph G = (V, E) where V = [n1 + n2 ] and E has every edge of the following two
types:
1. edges (i, j), where i, j ∈ [n1 ], i < j, and i is not connected to any j 0 < j in GiI 0 .
2. (i, n1 + j), where i ∈ [n1 ], j ∈ [n2 ], and i is connected to n1 + j in Gi+1
I0 .
ComputeStatus uses subroutine ConstructGraph to construct graph G. (ConstructGraph computes
set E.) After graph G is constructed, ComputeStatus checks whether configuration (col, st) and col0
are consistent w.r.t. Gi+1
I 0 . If they are not consistent it outputs a ⊥ symbol. If they are consistent
then B(i + 1, col0 , st0 ) 6= ∅ (rows i + 1, . . . , k in I 0 can be recolored to all black rows and the resulting
image is in B(i + 1, col0 , st0 )). ComputeStatus finds vector st0 based on the connectivity information
of graph G and information provided by vector st.
To check whether cl0 is consistent with (col, st) our algorithm uses subroutine ComputeStatus
(Algorithm 8). If it is consistent, to find the status vector st0 . Subroutine ComputeStatus uses
subroutine ConstructGraph that constructs a graph from cl and st that helps to compute st0 . The
nodes in this graph are 1-blocks of cl and edges are defined according to the information provided
by st. ConstructGraph is explained next.
For each i ∈ [k], every image S has some configuration (cl, st) in its i’th row w.r.t. GiS . Vector
st in this configuration has the information about which 1-blocks in cl are in the same connected
component in GiS and which are connected to the border. Thus, if (cl, st) is given we can construct
a graph G whose nodes are all 1-blocks of cl and the status vector of cl w.r.t. G is st. Subroutine
ConstructGraph (Algorithm 6) constructs graph G.
Algorithm 6: Subroutine ConstructGraph used in Algorithm 8.
input : vector cl ∈ {0, 1}k , and st ∈ Σn(cl) .
1

2
3
4
5
6
7

Index 1-blocks in cl in the nondecreasing order of indices of pixels they contain.
// Let n1 = num(cl), V = [n1 ], E = ∅, and stack = ∅ (we maintain a stack)
forall the indices j = 1, 2, . . . , n1 do
if stack 6= ∅ and st[j] = 1 then return ⊥
if stack = ∅ and st[j] ∈ {×, >} then return ⊥
if st[j] ∈ {<, ×} then push(j)
if st[j] = > then do p = pop(stack); add {p, j} to E until p = <
return G = (V, E)

Analysis of Algorithm 7.

The following lemma shows that Algorithm 7 is correct.

Lemma 5.5. For all i ∈ [k], col ∈ {0, 1}k , and st ∈ Σk , Algorithm 7 correctly computes cost(i, col, st).
27

Algorithm 7: Distance to border connectedness of a square S.
input : access to a k × k square S.
1

2

forall the indices i ∈ [k], vectors col ∈ {0, 1}k , and st ∈ Σnum(col) do
// For i ∈ [k], let ri ∈ {0, 1}k be a vector that corresponds to the ith row of S.
(
|r1 − col|1 , if i = 1 and st = 1num(col) ;
cost(i, col, st) =
∞,
otherwise.

3

forall the indices i = 2, 3, ..., k, vectors col, col0 ∈ {0, 1}k and st ∈ Σnum(col) do

4

if cost(i − 1, col, st) 6= ∞ then st0 = ComputeStatus(i, col, st, col0 )
if st0 6=⊥ then cost(i, col0 , st0 ) = min{cost(i, col0 , st0 ), cost(i − 1, col, st) + |ri − col0 |1 }
return (mincol∈{0,1}k ,st∈Σnum(col) cost(k, col, st)) · k −2

5
6

Proof. We prove the lemma inductively. For the first row, Algorithm 7 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, col, st) = |r1 − col|1 if st = 1num(col) ,
and cost(1, col, st) = ∞, otherwise). Assume that the statement in the lemma holds for some
row i ∈ [k − 1]. We prove the statement for row i + 1. Note that if B(i + 1, col0 , st0 ) = ∅ for
some col0 , st0 , then cost(i + 1, col0 , st0 ) = ∞. The algorithm correctly sets cost(i + 1, col0 , st0 ) to ∞
and never changes it. If B(i + 1, col0 , st0 ) 6= ∅ consider an image I ∗ ∈ B(i + 1, col0 , st0 ) such that
cost(i + 1, col0 , st0 ) = costi+1 (S, I ∗ ). Let col be the coloring of row i in I ∗ and st be the status
vector of col w.r.t. GiI ∗ . Then col0 and the configuration (col, st) are consistent w.r.t. Gi+1
I ∗ . Note
that I ∗ ∈ B(i, col, st) and costi+1 (S, I ∗ ) = costi (S, I ∗ ) + |ri+1 − col0 |1 . Moreover, for every image
I1 ∈ B(i, col, st), there is an image I2 ∈ B(i + 1, col0 , st0 ) such that costi (S, I1 ) = costi (S, I2 ). (In
I2 , recolor row i + 1 to col0 and all rows i + 2, . . . , k to all black rows and obtain image I2 . In image
I2 , col0 and (col, st) are consistent w.r.t. Gi+1
I2 and every 1-block in its rows i + 1, . . . , k is borderconnected. Thus, image I2 is border-connected and I2 ∈ B(i+1, col0 , st0 ).) Therefore, costi (S, I ∗ ) =
minI∈B(i,col,st) costi (S, I) = cost(i, col, st). At some point, the algorithm considers the configuration
(col, st) for row i and the coloring col0 for row i + 1. By the inductive assumption, the algorithm
correctly computes cost(i, col, st) which is equal to costi (S, I ∗ ). The output of ComputeStatus for
the triple i, col, st will be the vector st0 and the algorithm sets cost(i + 1, col0 , st0 ) to cost(i, col, st) +
|ri+1 − col0 |1 = costi (S, I ∗ ) + |ri+1 − col0 |1 which is the correct value. This completes the proof.
By Lemma 5.5, Algorithm 7 computes the cost of every configuration in row k. The algorithm
outputs the minimum one among these costs. Let Ŝ be an image such that dist(S, C 0 ) = dist(S, Ŝ).
Note that configurations of row k that are not possible for a border-connected image have unbounded costs (i.e., ∞). Thus, row k in 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 7
is equal to dist(S, C 0 ).
Query and Time Complexity of Algorithm 7. The most expensive step in Algorithm 7
is Step 3. Note that there are at most k · 2k · 5k sets B(·, ·, ·) for which subroutine ComputeStatus is
called in this step. ComputeStatus uses subroutine ConstructGraph to construct graph G = (V, E).
28

Algorithm 8: Subroutine ComputeStatus used in Algorithm 7.
input : index i; vectors col, col0 ∈ {0, 1}k , and st ∈ Σnum(col) .
1
2

3
4
5
6
7
8
9
10
11
12
13

14

15

Construct graph G = ConstructGraph(col, col0 , st)// Let G = (V, E).
if E = ∅ then return ⊥
// Let n1 = num(col), n2 = num(col0 )
Let col[0] = col0 [0] = row1 = row2 = 0
For every j = 1, 2, . . . , n1
if col[j − 1] = 0 and col[j] = 1 then increment row1 by 1
if col0 [j − 1] = 0 and col0 [j] = 1 then increment row2 by 1
/ E then add {row1 , row2 } to E
if col[j] · col0 [j] = 1 and {row1 , row2 } ∈
/ E for all j 0 ∈ [n2 ] then return ⊥
if ∃j ∈ [n1 ] with st[j] 6= 1 such that (j, n1 + j 0 ) ∈
if i = k then st0 = 1n2
else
Let st0 = 0n2 . Update st0 [1] = col0 [1] and st0 [n2 ] = col0 [k]
For each edge (j, n1 + j 0 ) ∈ E, j ∈ [n1 ], j 0 ∈ [n2 ], if st[j] = 1 then st[n1 + j 0 ] = 1.
Run BFS to find connected components in G. For each pair (n1 + j, n1 + j 0 ), where
j, j 0 ∈ [n2 ], if j and j 0 are connected and st0 [j] = 1 then st0 [n1 + j 0 ] = 1.
For each connected component of vertices n1 + j not marked by 1, where j ∈ [n2 ], update
the corresponding entries of st0 with the corresponding symbols in Σ (i.e., st0 [j] = < if it is
the vertex with the smallest index in the component, st0 [j] = > if it is the vertex with the
largest index in the component, and st0 [j] = ×, otherwise).
return st0

29

To construct type 1 and type 2 edges in E subroutine ConstructGraph performs O(n1 ) + O(n1 ) =
O(k) operations. Thus, the running time of ConstructGraph is O(k) (recall that n1 = num(col),
n2 = num(col0 )). Therefore, Steps 1-5 of ComputeStatus run in time O(k). Among the remaining
steps (Steps 6-10) of ComputeStatus the most expensive ones are Steps 8 and 9. Each of them
runs in time O(n1 · n2 ) = O(k 2 ) time. Thus, the running time of ComputeStatus is O(k 2 ) and
Algorithm 7 runs in time O(k 2 · k2k 5k ) = exp (O(k)), as claimed.

References
[1] I. Barany. Extremal problems for convex lattice polytopes: a survey. Contemporary Mathematics, 2000.
[2] P. Berman, S. Raskhodnikova, and G. Yaroslavtsev. Lp -testing. In STOC, pages 164–173,
2014.
[3] P. Berman, M. Murzabulatov, and S. Raskhodnikova. Tolerant testers of image properties. In
ICALP, 2016.
[4] P. Berman, M. Murzabulatov, and S. Raskhodnikova. Testing convexity of figures under the
uniform distribution. In SoCG, 2016.
[5] A. Blum. Machine learning theory. Lecture notes. URL www.cs.cmu.edu/~avrim/ML12/
lect0201.pdf.
[6] A. Campagna, A. Guo, and R. Rubinfeld. Local reconstructors and tolerant testers for connectivity and diameter. In APPROX-RANDOM, pages 411–424, 2013.
[7] A. Czumaj and C. Sohler. Property testing with geometric queries. In Algorithms - ESA
2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings,
pages 266–277, 2001. doi: 10.1007/3-540-44676-1 22. URL http://dx.doi.org/10.1007/
3-540-44676-1_22.
[8] A. Czumaj, C. Sohler, and M. Ziegler. Property testing in computational geometry. In Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings, pages 155–166, 2000. doi: 10.1007/3-540-45253-2 15. URL
http://dx.doi.org/10.1007/3-540-45253-2_15.
[9] A. Ehrenfeucht, D. Haussler, M. J. Kearns, and L. G. Valiant. A general lower bound on the
number of examples needed for learning. Inf. Comput., 82(3):247–261, 1989.
[10] E. Fischer and L. Fortnow. Tolerant versus intolerant testing for boolean properties. Theory
of Computing, 2(1):173–183, 2006.
[11] O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):
302–343, 2002.
[12] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and
approximation. J. ACM, 45(4):653–750, 1998.

30

[13] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other
learning applications. Inf. Comput., 100(1):78–150, 1992. doi: 10.1016/0890-5401(92)90010-D.
URL http://dx.doi.org/10.1016/0890-5401(92)90010-D.
[14] A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio. Agnostically learning halfspaces.
SIAM J. Comput., 37(6):1777–1805, 2008.
[15] M. J. Kearns, R. E. Schapire, and L. Sellie. Toward efficient agnostic learning. Machine
Learning, 17(2-3):115–141, 1994. doi: 10.1007/BF00993468. URL http://dx.doi.org/10.
1007/BF00993468.
[16] I. Kleiner, D. Keren, I. Newman, and O. Ben-Zwi. Applying property testing to an image
partitioning problem. IEEE Trans. Pattern Anal. Mach. Intell., 33(2):256–265, 2011.
[17] S. Korman, D. Reichman, and G. Tsur. Tight approximation of image matching. CoRR,
abs/1111.1713, 2011.
[18] S. Korman, D. Reichman, G. Tsur, and S. Avidan. Fast-match: Fast affine template matching.
In CVPR, pages 2331–2338. IEEE, 2013.
[19] M. Parnas, D. Ron, and R. Rubinfeld. Tolerant property testing and distance approximation.
J. Comput. Syst. Sci., 72(6):1012–1042, 2006.
[20] G. Pick. Geometrisches zur zahlenlehre. Sitzenber. Lotos (Prague), 19:311–319, 1899.
[21] S. Raskhodnikova. Approximate testing of visual properties. In RANDOM-APPROX, pages
370–381, 2003.
[22] D. Ron and G. Tsur. Testing properties of sparse images. ACM Trans. Algorithms, 10(4):
17:1–17:52, 2014. doi: 10.1145/2635806. URL http://doi.acm.org/10.1145/2635806.
[23] R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to
program testing. SIAM J. Comput., 25(2):252–271, 1996.
[24] B. Schmeltz. Learning convex sets under uniform distribution. In Data Structures and Efficient
Algorithms, Final Report on the DFG Special Joint Initiative, pages 204–213, 1992.
[25] L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984. doi:
10.1145/1968.1972. URL http://doi.acm.org/10.1145/1968.1972.

31

