Advances in Mathematical
Sciences and Applications
Vol. 26, No.1 (2017), pp. 1–18

GAKKOTOSHOTOKYO JAPANDISTANCES BETWEEN SETS — A SURVEY

Aura Conci
Fluminense Federal University, Niteroi, Brazil(E-mail: aconci@ic.uff.br)andCarlos Kubrusly
Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil(E-mail: carlos@ele.puc-rio.br)

Abstract.
The purpose of this paper is to give a survey on the notions of distance
between subsets either of a metric space or of a measure space, including deﬁnitions, aclassiﬁcation, and a discussion of the best-known distance functions, which is followed bya review on applications used in many areas of knowledge, ranging from theoretical topractical applications.

Communicated by Nobuyuki Kenmochi; Received September 18, 2016.
AMS Subject Classiﬁcation: 28A78, 54E35.
Keywords: Distance between sets, Hausdorﬀ distance, measure theoretical distances.

1

2

1

Introduction

Distances between subsets either of a metric space or of a measure space is the reasonof this paper, where the main focus is to deﬁne, classify, and review the best-known
distance functions, and some of their common applications. Most distances between sets,deﬁned either for closed and bounded (in particular, for compact, more particularly, forﬁnite) nonempty sets in a metric space, or for measurable sets with ﬁnite measure (inparticular, for ﬁnite sets under the counting measure) in a measure space, become ametric themselves. Behind the scenes, the main tools are naturally the notions of metricspace and measure space. Although the notion of distance between sets has a myriad ofconceivable deﬁnitions (see, e.g., [16, pp. 46-48, 85-86, 173-184, 298-301, 359-360], there
are two main distinct families of them, which we refer to as the Hausdorﬀ family and the
Measure Theoretical family.
Notation, terminology, basic deﬁnitions and a few results that will be required in
the sequel are posed in Section 2. These are naturally bound to the notions of metricand measure. Section 3 gives a detailed account on the Hausdorﬀ distance (which isa metric for closed and bounded sets) and its many relatives, which are obtained by
gradual modiﬁcations of the original Hausdorﬀ distance. Four equivalent forms of theoriginal Hausdorﬀ measure are discussed, as well as ﬁfteen variations of it. The measure
theoretical approach, dealing with the Fréchet–Nikodým–Aronszajn distance (and alsowith its normalized version, the Markzewisky–Steinhaus distance) is discussed in Section
4. Section 5 closes the paper with a review of the bibliography (since the 80’s) dealing withapplications of distance between sets towards innumerable subjects. This is split into threeclasses, namely, (1) Computational Aspects (with three subclasses: (1.1) distance in graphs,(1.2) distance between polygons, and (1.3) numerical procedures and algorithms), (2) On
Distances Between Fuzzy Sets (also with three subclasses: (2.1) Markzewisky–Steinhaus
distance, (2.2) Hausdorﬀ distances, (2.3) non-Hausdorﬀ distances), and (3) Distance in
Object Analysis (again with three subsections: (3.1) new metrics and comparisons, (3.2)
motion — translation and rotation, and (3.3) modiﬁed Hausdorﬀ including asymmetries).

2

Notation and terminology

This section summarizes classical standard topics that will be required in the sequel,
which can be found in an inﬁnitude of books dealing with analysis in general. For instance,see [42, Chapter 3] for metric space properties and [41, Chapter 2] for measure space
properties, among many others.
Let X be an arbitrary nonempty set, let d be a real-valued function on the Cartesian
product X×X of X with itself,d : X×X → R,
and consider the following properties, holding for arbitrary points x, y, z in X.
(i) d(x, y) = d(y, x)(symmetry),(ii) d(x, y) ≥ 0 and d(x, x) = 0 (nonnegativeness),(iii) d(x, y) = 0 implies x = y(positiveness),(iv) d(x, y) ≤ d(x, z) + d(z, y)(triangle inequality).

3
A real-valued function d on X×X that satisﬁes all properties (i), (ii), (iii) and (iv) is ametric in X, and the properties themselves are called the metric axioms. A set X equippedwith a metric d on X×X is a metric space, also denoted by (X, d). If d satisﬁes properties(i), (ii) and (iv), but not necessarily property (iii), then it is called a pseudometric in X.
If d satisﬁes properties (i), (ii) and (iii), but not necessarily (iv), then it is sometimes
called a semimetric in X. What is commonly referred to as a distance function in X is
simply any real-valued function d on X×X that satisﬁes properties (i) and (ii) — i.e.,any symmetric nonnegative function that vanishes at the identity line.
Remark 2.1. The diﬀerence between a metric and a pseudometric is that it is possible
for a pseudometric d to vanish at a pair (x, y) even if x ̸= y. A pseudometric d is trivial ifd(x, y) = 0 for every x, y ∈ X. However, given a nontrivial pseudometric d in X there is ae where the set Xe d),e is a associated with X andnatural way to obtain a metric space (X,e inherited from d. Indeed,d, and de (usually denoted again by d) is the natural metric in X
every nontrivial pseudometric d induces an equivalence relation ∼ on X (given by x∼x′
e is the quotient space— read x is equivalent to x′ — if and only if d(x, x′ ) = 0), and X
X/∼ which is precisely the collection of all equivalence classes [x] = {x ∈ X : x′ ∼x} withrespect to ∼ for every element x in X (i.e., X/∼ is a collection of sets [x], called equivalenceclasses, such that each element in X/∼ is a set consisting of all elements from X that areee is given by d([x],equivalent to each other), and the metric de in X[y]) = d(x, y), which
does not depend on the representatives x ∈ [x] and y ∈ [y] from the equivalence classes.
The power set ℘(X) of a given set X is the collection of all subsets of X. Let X be
an arbitrary nonempty set. Equip X with a metric d : X×X → R and consider the metricspace (X, d). A nonempty subset A of X is bounded if
sup d(x, y) < ∞,x,y ∈Aotherwise A is said to be unbounded, which is denoted by supx,y ∈A d(x, y) = ∞. The
diameter of a nonempty bounded subset A of X is the real number
diam(A) = sup d(x, y).
x,y ∈AThe distance from a point x ∈ X to a nonempty set A ∈ ℘(X) is the real numberd(x, A) = inf d(x, a),a∈A

and the ordinary distance function between two nonempty sets A and B in ℘(X) is thereal numberd(A, B) = inf d(a, b).
a∈A, b∈B

The above expression deﬁnes a mere distance function d : ℘(X)\∅×℘(X)\∅ → R. In fact,
such a function d trivially satisﬁes properties (i) and (ii) for all sets in ℘(X)\∅. It is however clear that in general d does not satisfy property (iii), and it does not satisfy property(iv) as well — e.g., take A, B, C in ℘(X)\∅ (which may even be pairwise disjoint) suchthat d(A, B) ̸= 0 and d(A, C) = d(C, B) = 0.
A σ-algebra A(X) of subsets of a given set X is a subcollection of the power set,
A(X) ⊆ ℘(X) (not necessarily a proper subcollection), such that4
the whole set X and the empty set ∅ belong to A(X),the complement X\E of a set E in A(X) belongs to A(X),the union of a countable collection of sets in A(X) belongs to A(X).
Sets in A(X) are called measurable sets, and the pair (X, A(X)) consisting of a set X anda σ-algebra of subsets of it is referred to as a measurable space. A measure is an extended
real-valued function µ on a σ-algebra A(X),µ : A(X) → R,
where R = R ∪ {−∞} ∪ {+∞} stands for the extended real line, satisfying the following
properties (referred to as the measure axioms).
(a) µ(∅) = 0,(b) µ(E) ≥ 0 for every E ∈ A(X),(∪) ∑(c) µ n En = n µ(En )for every countable family {En } of pairwise disjoint sets in A(X).
A measure space is a triple (X, A(X), µ) consisting of an arbitrary set X, a σ-algebra
A(X) of subsets of X, and a measure µ on A(X). We assume throughout this paper that
all measures are nonzero (i.e., µ(X) > 0).
Consider an arbitrary nonempty subcollection C(X) of ℘(X). If an arbitrary distance function d on C(X)\∅×C(X)\∅ is intended for gauging resemblance of sets in
C(X)\∅, then it may be useful to control it by preventing too large (and too small)values. In this case d can be normalized in terms of a measure µ on a σ-algebra ofsubsets of X, bringing forth new distance functions. For instance, suppose µ is any
nonzero ﬁnite measure (i.e., 0 < µ(X) < ∞) on any σ-algebra A(X) of subsets of X,
let d : C(X)\∅×C(X)\∅ → R be the ordinary distance function in C(X)\∅, and consider
the distance function d ′ : C(X)\∅×C(X)\∅ → R given by11d ′ (A, B) = µ(X)d(A, B) = µ(X)infa∈A, b∈Bd(a, b)for every sets A, B in C(X)\∅, or the distance functions in the intersection of C(X) andA(X), say d ′′, d ′′′ : (C(X) ∩ A(X))\∅ × (C(X) ∩ A(X))\∅ → R, given for every sets A, B
in (C(X) ∩ A(X))\∅ by1d(A, B)d ′′ (A, B) = µ(A∪B)

and

1d ′′′ (A, B) = µ(A)+µ(B)d(A, B)if µ(A) ̸= 0 or µ(B) ̸= 0, otherwise d ′′ (A, B) and d ′′′ (A, B) are deﬁned to be zero.
Let #A denotes the cardinality of an arbitrary set A ∈ ℘(X). Let F(X) ⊆ ℘(X)
stand for the collection of all ﬁnite subsets of the nonempty set X. Consider the collection F(X)\∅ ⊆ ℘(X)\∅ of all ﬁnite nonempty subsets of X. Take arbitrary ﬁnitennonempty sets A = {ai }mi=1 and B = {bi }i=1 in F(X)\∅, where m = #A and n = #B
lie in N, the set of all positive integers. Now consider the restriction d|F(X)\∅×F (X)\∅ ofthe ordinary distance function d : ℘(X)\∅×℘(X)\∅ → R to pairs of ﬁnite nonempty sets,

5
d : F(X)\∅×F(X)\∅ → R, denoted again by the same symbol d. Thus in this case, forevery x ∈ X and every A, B ∈ F (X)\∅,d(x, A) = inf d(x, a) = min d(x, a) = min d(x, ai ),a∈Ad(A, B) =infa∈A, b∈B

1≤i≤m

a∈A

d(a, b) = min d(a, b) =a∈A, b∈Bmin1≤i≤m , 1≤j≤nd(ai , bj );similarly for the normalized versions (to avoid trivialities, suppose X ∈ F (X)):
1
1d ′ (A, B) = #X
d(A, B), d ′′ (A, B) = #(A∪B)
d(A, B),

1d ′′′ (A, B) = #A+#B
d(A, B).

Still in these cases the functions d, d ′ , d ′′ , d ′′′ on F(X)\∅×F(X)\∅ are distance functions
but it is clear that properties (iii) and (iv) may fail (even if #X < ∞).

3

The Hausdorﬀ family

Let (X, d) be a metric space. Perhaps the best-known candidate for a metric in a
subset of ℘(X)\∅ is the Hausdorﬀ function h : ℘(X)\∅×℘(X)\∅ → R, which is deﬁned
for every A, B ∈ ℘(X)\∅ by [29, p.293] (see also [30, p.167]).
{}h(A, B) = max sup d(a, B) , sup d(b, A)
a∈A
b∈B
{
}
= max sup inf d(a, b) , sup inf d(a, b) .
a∈A b∈Bb∈B a∈A

Although the Hausdorﬀ function satisﬁes properties (i) and (ii) and has the property thath({a}, {b}) = d(a, b) for every pair of singletons {a}, {b} ∈ ℘(X)\∅, it is not a distancefunction since it is not real-valued. For instance, on ℘(R)\∅×℘(R)\∅ we get h({0}, R) =+∞. Even if it were plausible to admit an extended-real-valued distance function, thefunction h : ℘(R)\∅×℘(R)\∅ → R would not be a pseudometric since property (iii) fails(e.g., h(A, B) = 0 for A = (0, 1), B = [0, 1] in ℘(R)\∅). An equivalent formulation for
the Hausdorﬀ function (also called Blaschke function [16, p.48], or Pompeiu–Hausdorﬀ
function [50, Example 4.3], [7]) is given below.
Proposition 3.1. For every A, B ∈ ℘(X)\∅,h(A, B) = sup |d(x, A) − d(x, B)|.
x∈X

Proof . Take x ∈ X, a ∈ A, b ∈ B. Since d(x, b) ≤ d(x, a) + d(a, b), we get d(x, B) =inf b∈B d(x, b) ≤ d(x, a) + inf b∈B d(a, b) ≤ d(x, a) + supa∈A inf b∈B d(a, b), and henced(x, B) ≤ inf a∈A d(x, a) + supa∈A inf b∈B d(a, b) = d(x, A) + supa∈A inf b∈B d(a, b). Symmetrically, d(x, A) ≤ d(x, B) + supb∈B inf a∈A d(a, b). Thus, for every x ∈ X,{}
|d(x, A) − d(x, B)| ≤ max sup inf d(a, b) , sup inf d(a, b) .
a∈A b∈Bb∈B a∈A

6
In particular, for x = a ∈ A, it follows that supa∈A inf b∈B d(a, b) = supx=a∈A d(x, B) =supx=a∈A |d(x, A) − d(x, B)|. Symmetrically, by setting x = b ∈ B, it also follows thatsupb∈B inf a∈A d(a, b) = supx=b∈B |d(x, A) − d(x, B)|. Therefore,{}
max sup inf d(a, b) , sup inf d(a, b) ≤ sup |d(x, A) − d(x, B)|.
a∈A b∈Bb∈B a∈Ax∈X

Although the Hausdorﬀ function is not even a distance function when deﬁned on thedomain ℘(X)\∅×℘(X)\∅, if restricted to an appropriate subcollection it becomes a metric. Let B(X) ⊆ ℘(X) denote the collection of all closed and bounded subsets of the metricspace (X, d), take the collection B(X)\∅ ⊆ ℘(X)\∅ of all nonempty closed and bounded
subsets of (X, d), and consider the restriction h|B(X)\∅×B(X)\∅ of h : ℘(X)\∅×℘(X)\∅ → R
to B(X)\∅×B(X)\∅, denoted by the same symbol,
h : B(X)\∅×B(X)\∅ → R.
This is not only real-valued but is a metric in B(X)\∅ [18, Problem IX.4.8], [8, Example 1.9.7]. In particular, since F(X) ⊆ B(X), when restricted still further, now to
F(X)\∅×F(X)\∅ (i.e., when restricted to nonempty ﬁnite sets), the Hausdorﬀ function(again, denoted by the same symbol h)h : F(X)\∅×F(X)\∅ → R,ngiven for every A = {ai }mi=1 and B = {bi }i=1 in F(X)\∅ by{}h(A, B) = max max min d(ai , bj ) , max min d(ai , bj ) ,1≤i≤m 1≤j≤n

1≤j≤n 1≤i≤m

is a metric in F(X)\∅. For more on theoretical aspects of Hausdorﬀ distance see, forinstance, [57, Chapter 2] (also [56], [58]), and for the topology of Hausdorﬀ distancessee [4]. Indeed, the Hausdorﬀ metric has many appealing properties, but it shares some
practical drawbacks [5, Section 3.4], [19, Section 2]. For an account on theoretical andpractical aspects of some common distances between ﬁnite sets, including Hausdorﬀ’s see,e.g., [5, 36, 17, 19, 25, 26] and the references therein.
Let C(X) stand either for B(X) or F(X). Associated with each A ∈ ℘(X) set
 #A,
if C(X) = F(X),size(A) = diam(A), if C(X) = B(X) ̸= F(X),(to avoid trivialities suppose size(X) > 0) and consider the Hausdorﬀ metrich : C(X)\∅×C(X)\∅ → R.
A natural normalization h′ : C(X)\∅×C(X)\∅ → R of h is given by{}11h(A, B) = size(X)max sup d(a, B) , sup d(b, A)h′ (A, B) = size(X)
a∈A
b∈B
1
= size(X) sup |d(x, A) − d(x, B)|x∈X

7(cf. Proposition 3.1), which is again a metric (since h is a metric) if size(X) < ∞. Whendealing with normalized versions of metrics on C(X)\∅×C(X)\∅ it is advisable to assume
that size(X) < ∞ (i.e., X is bounded if C(X) = B(X) ̸= F(X), or X is ﬁnite if C(X) =F(X)) in order to avoid trivial pseudometrics. Further natural normalizations of h, say
h′′ , h′′′ : C(X)\∅×C(X)\∅ → R, lead to the distances1h′′ (A, B) = size(A∪B)
h(A, B)

1h′′′ (A, B) = size(A)+size(B)h(A, B)andif size(A) ̸= 0 or size(B) ̸= 0; otherwise they are zero. Straightforward modiﬁcations of h,namely, eh, eh′ : C(X)\∅×C(X)\∅ → R, where maximum is replaced with sum,eh(A, B) = sup d(a, B) + sup d(b, A),
a∈A

b∈B

(
)
1
1
e
e
h′ (A, B) = size(X)h(A, B) = size(X)sup d(a, B) + sup d(b, A) ,
a∈A

b∈B

are still metrics in C(X)\∅ (if size(X) < ∞ — see [59, Section 1]). Again, further natural
normalizations eh′′ , eh′′′ : C(X)\∅×C(X)\∅ → R of e
h are
1
e
e
h′′ (A, B) = size(A∪B)
h(A, B)1eeh′′′ (A, B) = size(A)+size(B)h(A, B)andif size(A) ̸= 0 or size(B) ̸= 0, otherwise the distances are set down to zero.
Another modiﬁed version hp : F(X)\∅×F(X)\∅ → R of h, where the supremum isreplaced with a p-sum, given by
hp (A, B) =(∑x∈X|d(x, A) − d(x, B)|p

) p1

for any real p ≥ 1 if X ∈ F(X), and its normalization h′p : F(X)\∅×F(X)\∅ → R,
h′p (A, B) =

(

1
#X

∑
x∈X

|d(x, A) − d(x, B)|p

) p1

,

are referred to as p-Hausdorﬀ distances (see [16, p.48,359]), which in fact are metrics [5,eq.21]). Further variants of h, viz., hk , h′k ,: F(X)\∅×F(X)\∅ → R for k = 0, 1 (not all
metrics), read as follows. First modify h by replacing supremum with sum,}{∑∑d(b, A) .
d(a, B) ,h0 (A, B) = max
b∈B

a∈A

Its averaged version,
h′0 (A, B) = max

{

1
#A

∑
a∈A

1
d(a, B) , #B

∑
b∈B

}
d(b, A) ,is called modiﬁed Hausdorﬀ distance in [16, p.360] (see also [17, eq.6,8]). Next modify hby replacing maximum with sum in h0 ,∑∑d(b, A)d(a, B) +h1 (A, B) =
a∈A

b∈B

8
(considered in [19] with a multiplicative factor of 12 ), and again its averaged version,∑∑11h′1 (A, B) = #A
d(a, B) + #B
d(b, A)a∈A

b∈B(considered in [17, eq.6,9]) with a factor of 12 ). Caution: h1 and h′1 are diﬀerent from hp
and h′p for p = 1. A normalized version h′′1 : F(X)\∅×F(X)\∅ → R of h1 ,
(∑
)
∑
′′
1
h1 (A, B) = #A+#B
d(a, B) +d(b, A) ,a∈Ab∈B

is referred to as geometric mean error between two images in [16, p.360] (see also [17,eq.6,10]). Properties (i) and (ii) hold trivially, and property (iii) is readily veriﬁed, andhence all the above functions are semimetrics in F(X)\∅. However, property (vi) may
fail. For instance, if A = {a}, B = {b, c}, and C = {c} with 0 < d(b, c) < d(a, b) and0 < d(a, c) ≤ d(a, b), then hk (A, C)+hk (C, B) < hk (A, B) for k = 0, 1. So the semimetrics
h0 , h1 are a not metrics in F(X)\∅. On the other hand, it was show in [25, Theorem 1]that the function h′′′1 : F(X)\∅×F(X)\∅ → R given by
( ∑
)
∑
∑
∑
1
1
1
h′′′
(A,
B)
=
d(a,
b)
+
d(a,
b)
1
#(A∪B) #A
#B
a∈A

b∈B\A

b∈B

a∈A\B

is a metric in F(X)\∅. For more combinations along these lines, including theoreticalaspects or practical applications, see, e.g., [5, 36, 17, 19, 16, 25, 26].
The envelope of radius ε centered at an arbitrary set A ∈ ℘(X)\∅, also referred to as
the ε-envelope (or even the ε-neighborhood ) of A is the set{}
Aε = x ∈ X : d(x, A) ≤ ε .
If A is closed, so that d(x, A) = inf a∈A d(x, a) = mina∈A d(x, a) for every x ∈ X, then Aε ={x ∈ X : d(x, a) ≤ ε for some a ∈ A}. Another equivalent formulation for the Hausdorﬀ
function reads as follows [40, Problem 4.D] (also [21, Section 9.1]).
Proposition 3.2. For every A, B ∈ ℘(X)\∅,{}h(A, B) = inf ε ≥ 0 : A ⊆ Bε and B ⊆ Aε .
Proof . Take A, B ∈ ℘(X)\∅ arbitrary, set
hA = sup d(a, B)

and

a∈A

hB = sup d(b, A),b∈B

and observe thatA ⊆ Bε ⇐⇒ hA ≤ εand

B ⊆ Aε ⇐⇒ hB ≤ ε.

(Indeed, A ⊆ Bε if and only if d(a, B) ≤ ε for all a ∈ A). Thus{}{}
h(A, B) = max hA , hB ≤ inf ε ≥ 0 : A ⊆ Bε and B ⊆ Aε .
Conversely, note thatA ⊆ BhAandB ⊆ AhB(in fact, A ⊆{x ∈ X : d(x, B) ≤ supa∈A d(a, B)} = BhA ). Therefore,

9
}
}
{
{
inf ε ≥ 0 : A ⊆ Bε and B ⊆ Aε ≤ max hA , hB = h(A, B).
This version of the Hausdorﬀ function is particularly useful to verify that the metricspace (B(X)\∅×B(X)\∅, h) is complete if X = Rn equipped with its usual Euclidian
metric (see, e.g., [20, p.37]) — this can be extended to any complete metric space (X, d)if B(X) is swapped with K(X), the collection of all compact subsets of the metic space(X, d) (where F(X) ⊆ K(X) ⊆ B(X) ⊆ ℘(X)). Since A ⊆ B if and only if A\B = ∅, forany sets A and B, it follows that the equivalent expression for the Hausdorﬀ function in
Proposition 3.2 can also be rewritten as{}h(A, B) = inf ε ≥ 0 : A\Bε = ∅ and B\Aε = ∅ ,yielding still another equivalent way to write the same Hausdorﬀ function h which, if
acting on B(X)\∅×B(X)\∅ (in particular, on F(X)\∅×F(X)\∅), is a metric. This lastform has been used in some applications (see, e.g., [14]).

4

The measure theoretical family

Let X be any nonempty set and consider the power set ℘(X). The symmetric diﬀerenceof two sets A, B ∈ ℘(X) is the set
A▽B = (A\B) ∪ (B\A) = (A ∪ B)\(A ∩ B),
so that A = B if and only if A▽B = ∅ (and A▽∅ = ∅▽A = A for every A ∈ ℘(X)). Letµ : A(X) → R be an arbitrary nonzero measure (i.e., µ(X) > 0) on an arbitrary σ-algebra
A(X) of subsets of X (in particular, ℘(X) may itself be a possible σ-algebra of subsetsof X, depending on the measure µ). Consider the measure space (X, A(X), µ). Two sets
E, F in A(X) are equivalent (or µ-equivalent), denoted by E∼F, if µ(E▽F ) = 0. The
relation ∼ is an equivalence relation on A(X). Deﬁne a function δ : A(X)×A(X) → R by
δ(E, F ) = µ(E▽F )for every E, F in A(X). In general, the property(iii) δ(E, F ) = 0 implies E = F
fails; it fails for diﬀerent sets whose symmetric diﬀerence (which is nonempty) is of measurezero (i.e., for distinct equivalent sets). On the other hand, the properties(i) δ(E, F ) = δ(F, E),(ii) δ(E, F ) ≥ 0 and δ(E, E) = 0,(iv) δ(E, F ) ≤ δ(E, G) + δ(G, F ),hold for every E, F, G ∈ A(X) [48, p.138], [28, Problems 3-4.9] (also [41, Problem 6.5]).
Note that δ(∅, E) = δ(E, ∅) = µ(E) for every E ∈ A(X). If the measure µ is ﬁnite,then the function δ is real-valued. Thus assume from now on that the positive measureµ is ﬁnite (i.e., 0 < µ(X) < ∞). In this case δ is not only a distance function but is a
pseudometric in A(X).

10Remark 4.1. This pseudometric δ : A(X)×A(X) → R is referred to as the Fréchet–
Nikodým–Aronszajn distance [47, p.319]. In fact, it is sound and clear that the distanceis introduced and proved to be a pseudometric in Nikodým’s paper [48, Deﬁnition 4] as of1930. As for Aronszajn’s credit, Nikodým himself [48, p.134] mention a work “to appear”
which we were not able to trace back. As for Fréchet’s own claim of priority, [48, p.134]
refers to [23] and [24] as of 1921 and 1934, respectively (see also [49, Section 27.3.4]).
There are essentially two ways of normalizing this pseudometric: either set))
δ ′ (E, F ) = δ(E,F= µ(E▽F
,
µ(X)
µ(X)

or (since {(E ∪ F )\(E ∩ F ), E ∩ F } is a partition of E ∪ F so that µ(E ∪ F ) = µ(E▽F )+µ(E ∩ F ) ), set δ(E,F )))= µ(E▽F= 1 − µ(E∩F, if µ(E ∪ F ) ̸= 0,′′µ(E∪F )µ(E∪F )
δ (E, F ) = µ(E∪F ) 0,
if µ(E ∪ F ) = 0,
for every sets E, F in A(X). Both functions are bounded by 1 (i.e., δ ′ (E, F ) ≤ 1 andδ ′′ (E, F ) ≤ 1 since E▽F ⊆ E ∪ F ⊆ X). The function δ ′ : A(X)×A(X) → R clearly isa pseudometric in A(X) (because δ is), and it was proved in [47, Section 1.2] that thefunction δ ′′ : A(X)×A(X) → R is again a pseudometric in A(X), which is referred to as
the Markzewisky–Steinhaus distance (see also [16, pp.46,175,299]).
It is worth noticing that a normalized real-valued function on A(X)×A(X) given byµ(E∩E)µ(E∩F )
if µ(E ∪ F ) ̸= 0 is not even a distance function, since 1 = µ(E∪E)
̸= 0 for every Eµ(E∪F )in A(X) for which µ(E) ̸= 0 (i.e., it is only symmetric and nonnegative but it does notvanish at the identity line, so that property (ii) fails — as well as properties (iii) and (iv)).
The functions δ, δ ′, δ ′′ : A(X)×A(X) → R are pseudometrics in A(X) ⊆ ℘(X) (nontrivial pseudometrics because µ is a nonzero measure), and so each of them induces a
metric on the quotient space A(X)/∼ (of classes of equivalence of sets which diﬀer fromeach other in the same class only by a set of measure zero: E∼F ⇐⇒ µ(E▽F ) = 0 —cf. Remark 2.1). However, if the ﬁnite measure µ is zero only at the empty set, then inthis particular case E∼F if and only if E = F , and so δ, δ ′, δ ′′ are themselves metrics inthe σ-algebra A(X) ⊆ ℘(X)..
Set A(X) = ℘(X) for a given nonempty set X and consider the counting measureν : ℘(X) → R, which is deﬁned by{#E, if E is ﬁnite,
ν(E) =+∞, if E is inﬁnite,
for every set E ∈ ℘(X). In this case, the only set of measure zero is the empty set. However,the counting measure is not ﬁnite if there exist inﬁnite subsets of X. Thus suppose X is
ﬁnite (i.e., #X < ∞) so that ν : ℘(X) → R is given by
ν(E) = #E

11for every subset E of the ﬁnite set X. Hence ν(X) = #X < ∞, and ν is a ﬁnite countingemeasure on ℘(X), and so the function δe: ℘(X)×℘(X) → R deﬁned by δ(E,F ) = ν(E▽F ),equivalently,eδ(E,F ) = #(E▽F ),for every subsets E and F of the ﬁnite set X is indeed a metric in the power set ℘(X).
This function δe is the ﬁnite version of the Fréchet–Nikodým–Aronszajn pseudometric δ(cf. Remark 4.1), now trivially a metric, whose natural normalizations yield the metrics
δe′ , δe′′ : ℘(X)×℘(X) → R,)
δe′ (E, F ) = #(E▽F,#X
 #(E▽F ))= 1 − #(E∩F, if E ∪ F ̸= ∅,#(E∪F )
δe′′ (E, F ) = #(E∪F ) 0,
if E ∪ F = ∅,for every E, F ∈ ℘(X). The function δe′′ is the ﬁnite version of the Markzewisky–Steinhaus
pseudometric δ ′′ which, again, is a metric. This particular metric is sometimes called
Jaccard distance (see, e.g., [25, eq.4], [26, eq.5], [16, p.299] — see also [43, p.34], [27,p.174]) after the botanist Paul Jaccard, which has been referred to as Tanimoto distance aswell [16, pp.46,299], [45, p.263]. For more on metrics based on the cardinality of nonempty
ﬁnite sets see [31].
Observe again that the normalized real-valued function on ℘(X)×℘(X) given by#(E∩F )
if E ∪ F ̸= ∅ and 1 otherwise is not a distance function. In fact, #(E∩E)
̸= 0 for#(E∪F )#(E∪E)

every nonempty set E in ℘(X), and properties (ii), (iii) and (iv) fail. For instance, consider
the sets E = {e, f }, F = {f }, and G = {g} for pairwise distinct points e, f, g ∈ X, so)#(G∩F )
that #(E∩F
̸= 0, #(E∩G)= #(G∪F= 0, and #(H∩H)= 1 for every H in ℘(X). Such a#(E∪F )#(E∪G))#(H∪H)
nondistance function has been refereed to as Jaccard similarity or Tanimoto similarity in[16, p.299], and as Jaccard index in [26, eq.4].

5

A concise review on applications

A collection of contributions on applications, classiﬁed into three apparently distinct(but certainly not disjoint) classes, is considered in this section. Distance functions aresupposed to act on appropriate domains. When we refer to a Hausdorﬀ distance, it isunderstood that it acts on an admissible domain that makes it well-deﬁned (e.g., on
B(X)\∅×B(X)\∅ or, in particular, on F(X)\∅×F(X)\∅, which make the Hausdorﬀ
function into a metric). The distances and metrics of the families h(s) and δ(s) discussed in
Sections 3 and 4 will be freely referred throughout this section, where we will now proceed
formally, omitting theoretical details.
The forthcoming reference list bears no claim of completeness. Perhaps a complete
list (if this were possible), supporting a brief review, would become unacceptably large,
leading to a dull catalog. The objective criterion for selecting the representatives in eachclass of the present review was mostly based on citations; the subjective one relies on theauthors’ taste.

12Applications of the notion of distances between sets, in a variety of sensible deﬁnitions,have been commonly (and naturally) used in many areas of knowledge, ranging fromtheoretical to practical applications; for instance, from computer science to biologicalsciences. Roughly speaking, these applications aim at shape analysis in a wide sense (andso they encompass questions involving any sort of procedures towards sets distinction in
general). We propose a simple (perhaps too simple) and rough classiﬁcation of application
areas into three classes.
5.1.Computational Aspects. All applications in this subsection deal with the Hausdorﬀ
family, most of them exclusively with the plain Hausdorﬀ distance h.
5.1.1. Distance in graphs. Computational aspects, with emphasis in graph theory, for the
Hausdorﬀ metric h over ﬁnite sets and some of its variant distance functions as in Section
3, were considered by Eiter and Mannila [19] in 1997. These were compared both fromtheoretical and computational points of view, whose comparisons are specially tailored for
applications to link distances [19, p.113] in graphs, some of them computed by polynomial
time algorithms. In fact the Hausdorﬀ metric is computable in polynomial time and, inspite of its appealing properties, it is shown that it may not be appropriate for some
applications, since it does not take into account the entire conﬁguration of some ﬁnite
sets. A review on some distances in the Hausdorﬀ family is presented together with areview on the literature up to then.
5.1.2. Distance between polygons. Polygons (as well as polyhedra) are characterized by the
position of a ﬁnite number of points, in general in a ﬁnite-dimensional Euclidean space.
An algorithm for computing the Hausdorﬀ distance h between a pair of convex polygons
was proposed by Atallah [2] in 1983. This was extended by Atallah, Ribeiro and Liﬁschtiz[3] in 1991, where algorithms for computing some Hausdorﬀ-type distances of two possibly
overlapping and not necessarily convex polygons was proposed. Algorithms for computing
Hausdorﬀ distance h for general polyhedra represented by triangular meshes was considered by Barton, Hanniel, Elber and Ki [6] in 2010, including a literature review regarding
applications along this line — the reader is referred to the references therein. For anotherapproach, using the Minimum Norm Duality Theorem (see, e.g. [46, p.136]) regarding
the ordinary distance function d between convex sets in a normed space, see [15].
5.1.3. Numerical procedures and algorithms. The preceding subsection dealt with numerical aspects and algorithms as well, although this may not have been the main purpose
there. Shonkwiler [59] considered in 1989 an algorithm for computing the eh distance between two images in linear time. Huttenlocher and Kedem [34] in 1990 and Huttenlocher,
Kedem and Kleinberg [35] in 1992 computed translates of the Hausdorﬀ distance h forsubsets of the real line and of the Euclidian plane, where the results were also applied forcomparing polygons under aﬃne transformations, the main focus being on computational
speed. Chew and Kedem [13] in 1998 proceeded along the same line, considering more
options for the metric d on an n-dimensional (n ≤ 3) real space X, such as the sup metricand the d1 metric in addition to the usual d2 Euclidian metric. Numerical comparisons for
estimating the Hausdorﬀ distance h between discrete 3-dimensional surfaces represented
by triangular meshes, aiming at the reduction of computational eﬀort and memory usage,
was considered by Aspert, Santa-Cruz and Ebrahimi [1] in 2002.

13
5.2. On Distances Between Fuzzy Sets. “There has been a number of papers proposing diﬀerent extensions of the Hausdorﬀ metric to fuzzy sets. None of these proposals
behave as one would intuitively expect” [10].
5.2.1. Marczewski–Steinhaus distance. Following the Marczewski–Steinhaus metric δe′′ ,Gardner, Kanno, Duncan, and Selmic [26] proposed in 2014 an extension of δe′′ , boundedby δe′′ itself, which was shown to be a metric and suitable for applications in patternrecognition, image processing, machine learning, and information retrieval. As one would
expect, δe′′ would be too much of a metric to be used for fuzzy sets, and so further measure
theoretical distances are also considered. Comparisons were implemented involving also
the Hausdorﬀ metric.
5.2.2. Hausdorﬀ distances. Applications along this lines involving Hausdorﬀ-like distancefunctions for fuzzy sets had been considered before by Rosenfeld [51] in 1985 and by
Chaudhuri and Rosenfeld [11] in 1996, which were followed by Boxer [9] in 1997, by Fan[22] in 1998, and by Chaudhuri and Rosenfeld [12] in 1999. A diﬀerent approach where
the Hausdorﬀ distance is used to generate further similarity measures for fuzzy sets wasconsidered by Hung and Yang [33] in 2004.
5.2.3. Non-Hausdorﬀ distances. A critical analysis on applications to fuzzy sets was undertaken by Brass [10] in 2002, where under an intriguing title “on the nonexistence ofHausdorﬀ-like metrics for fuzzy sets” he set about to discuss plausible systems of metricaxioms for fuzzy sets. Fujita [25] considered in 2013 some distance functions that canbe applied to fuzzy sets, where the Hausdorﬀ metric h and the Marczewski–Steinhaus
ﬁnite-version metric δe′′ are taken as starting points for yielding the original metric h′′′1.
5.3. Distance in Object Analysis. By “object analysis” we simply mean “image
analysis” in a very broad sense, ranging from visible images to binary strings in general.
The majority of applications of set distances focuses on problems inside this classiﬁcation,
including all ranges of applications for pattern recognition. There is a very large set ofreferences (most on Hausdorﬀ distance and its relatives) for image processing in sucha broad sense. Also nonmetric distances (or nonmetric similarity functions), meaning
semimetrics (where the triangle inequality may fail), have been considered for image
analysis by Jacobs, Weinshall and Gdalyahu [38] in 2000. Actually, a whole book on visual
recognition using Hausdorﬀ distance by Rucklidge [54] has appeared in 1996, emphasizing
computational aspects towards applications on imaging processing, including concrete
experiments and a large list of references (which goes beyond set distances applied to image
processing), to which the reader is referred. We comment on a shorter list (not included
and not disjoint with the above-mentioned) with a cutoﬀ roughly after considering someof the most cited articles (but not only) in order keep up with a reasonable-size list.
5.3.1. New metrics and comparisons. Baddeley [5] presents in 1992 a rather detailed discussion on the Hausdorﬀ metric h pointing out that, although theoretically attractive, this is
too sensitive a metric for image processing purposes, becoming practically unstable. Thus
the metric h′p is introduced and compared for p = 2 with “error measures of current use”,
which is essentially the metric δ ′ (and some asymmetric variants of it), and comparisonsinvolving classical synthetic images are also considered. As we have seen in 5.2.1 and 5.2.3,

14
Fujita [25] in 2013, and also Gardner, Kanno, Duncan, and Selmic [26] in 2014, introduced
original metrics as well, including discussions on the metrics h and δe′′ . Dubuisson and Jain
[17] considered in 1994 most of the Hausdorﬀ family of distances (and metrics) of Section
3 towards applications in image processing, comparing 24 combinations of them, including
comparisons involving real images. They point out that h′0 presents the best performance
among their experiments.
5.3.2. Motion – translation and rotation. Rote [52] proposed in (1991) an algorithm
for computing the minimum Hausdorﬀ distance between subsets of the real line undertranslation. This was also considered by Li, Shen and Li [44] in 2008. Huttenlocher, Klanderman and Rucklidge [36], and Huttenlocher and Rucklidge [37], investigated in 1993 theHausdorﬀ distance h to evaluate nearness between a model set and an image set, including comparisons under translation and rigid motion (combined translation and rotation),and an algorithm is proposed to compute these distances with examples using real image.
Rucklidge [53, 55] in 1995 and 1997 considered a procedure for searching space transformations of a model to match transformations that minimize the Hausdorﬀ distance h
between the transformed model and an image, including examples. Hossain, Dewan, Ahn
and Chae, [32] also proposed in 2012 an algorithm for computing Hausdorﬀ-like distanceswith application to moving objects. Also see 5.1.3.
5.3.3. Modiﬁed Hausdorﬀ including asymmetries. Takács [61] considered in 1998 a procedure for face matching based on the Hausdorﬀ family’s distance h′0 . This includes a penalty
scheme to ensure that images with large overlap are easily distinguished. Experimental
results on a large set of face images are carried out. Sim, Kwon and Park [60] considered in
1999 an asymmetric function associated to the distance h′1 for object matching, including
simulations for comparisons based on synthetic and real images. Jesorsky, Kirchberg andFrischholz [39] also used in 2001 an asymmetric function associated to the distance h′1 ,applied for shape comparisons towards face detection, where experiments were carried out
with real images. Zhao, Shi and Deng [62] compared in 2005 asymmetric versions of hand h1 for object matching in two-dimensional images, including experimental results.

References[1] N. Aspert, D. Santa-Cruz and T. Ebrahimi, Mesh: measuring errors between surfaces
using the Hausdorﬀ distance, Proc. IEEE Int. Conf. Multim. Expo. Lausanne (2002),
705-708.
[2] M.J. Atallah, A linear time algorithm for the Hausdorﬀ distance between convex
polygons, Inform. Process. Lett. 17 (1983), 207–209.
[3] M.J. Atallah, C.C. Ribeiro and S. Liﬁschtiz, Computing some distances functions
between polygons, Pattern Recognition 24 (1991), 775-781.
[4] H. Attouch, R. Lucchetti and R.J.-B. Wets, The topology of the ρ-Hausdorﬀ distance,
Ann. Mat. Pura Appl. (4) CLX (1991), 303–320.

15[5] A.J. Baddeley, Errors in binary images and Lp version of the Hausdorﬀ metric,
Nieuw Arch. Wisk. (4) 10 (1992), 157–183.
[6] M. Barton, I. Hanniel, G. Elber and M.-S. Kim, Precise Hausdorﬀ distance computation between polygonal meshes, Comput. Aided Geom. Design 27 (2010), 580-591.
[7] T. Birsan and D. Tiba, One hundred years since the introduction of the set distanceby Dimitrie Pompeiu, Proc. 22nd IFIP TC7 Conf., Turin (2005), 35–39.
[8] L.M. Blumenthal, Theory and Applications of Distance Geometry, 2nd ed., Chelsea,
New York, 1970.
[9] L. Boxer, On Hausdorﬀ-like metrics for fuzzy sets, Pattern Recognition Lett. 18(1997), 115–118; Erratum: Pattern Recognition Lett. 18 (1997), 505–506.
[10] P. Brass, On the nonexistence of Hausdorﬀ-like for fuzzy sets, Pattern Recognition
Lett. 23 (2002), 39–43.
[11] B.B. Chaudhuri and A. Rosenfeld, On a metric distance between fuzzy sets. Pattern
Recognition Lett. 17 (1996), 1157–1160.
[12] B.B. Chaudhuri and A. Rosenfeld, A modiﬁed Hausdorﬀ distance between fuzzy sets,
Inform. Sci. 118 (1999), 159–171.
[13] L.P. Chew and K. Kedem, Getting around a lower bound for the minimum Hausdorﬀ
distance, Comput. Geom. 10 (1998), 197–202.
[14] A. Conci, S.L. Galvão, G.O. Sequeiros, D.C.M. Saade and T. MacHenry, A new measure for comparing biomedical regions of interest in segmentation of digital images,
Discrete Appl. Math. 197 (2015), 103–113.
[15] A. Dax The distance between two convex sets, Linear Algebra Appl. 416 (2006),
184–213.
[16] M.M. Deza and E. Deza, Encyclopedia of Distances, Springer, Berlin, 2009.
[17] M.-P. Dubuisson and A.K. Jain, A modiﬁed Hausdorﬀ distance for object matching,Proc. Int. Conf. Pattern Recognition, Jerusalem (1994), 566–568.
[18] J. Dugundji, Topology, Allyn & Bacon, Boston, 1966.
[19] T. Eiter and H. Mannila, Distance measures for point sets and their computation,
Acta Inform. 34 (1997), 109–133.
[20] K.J. Falconer, The Geometry of Fractal Sets, Cambridge University Press, Cambridge, 1986.
[21] K.J. Falconer, Fractal Geometry: Mathematical Foundations and Applications, 3rded., Wiley, Chichester, 2014.

16[22] J.-L. Fan, Note on Hausdorﬀ-like metrics for fuzzy sets, Pattern Recognition Lett.
19, (1998), 793–796.
[23] M. Fréchet, Sur le diverses modes de convergence d’une suite de fonctions d’une
variable, Bull. Calcutta Math. Soc. 11 (1921), 187–306.
[24] M. Fréchet, Sur la distance de deux ensembles, Bull. Calcutta Math. Soc. 15 (1924),
1–8.
[25] O. Fujita, Metrics based on average distance between sets, Japan J. Indust. Appl,
Math. 30 (2013), 1–19.
[26] A. Gardner, J. Kanno, C.A. Duncan and R. Selmic, Measuring distance between
unordered sets of diﬀerent sizes, Proc. IEEE Conf. Comput. Vis. Pattern Recognit.,
Columbus (2014), 137–143.
[27] G. Gilbert, Distance between sets, Nature 239 (1972), 174.
[28] P.R. Halmos, Measure Theory, Van Nostrand, New York, 1950.
[29] F. Hausdorﬀ, Grundzüge der Mengenlehre, Veit, Leipzig, 1914.
[30] F. Hausdorﬀ, Set Theory, 2nd ed., Chelsea, New York, 1962.
[31] K.J. Horadam and M.A. Nyblom, Distances between sets based on set commonality,
Discrete Appl. Math. 167 (2014), 310–314.
[32] M.J. Hossain, M.A.A Dewan, K. Ahn and O. Chae, A linear time algorithm of computing Hausdorﬀ distance for content-based image analysis, Circuits Systems Signal
Process. 31 (2012), 389–399.
[33] W.-L. Hung and M.-S. Yang, Similarity measures of intuitionistic fuzzy sets based on
Hausdorﬀ distance, Pattern Recognition Lett. 25 (2004), 1603–1611.
[34] D. Huttenlocher and K. Kedem, Computing the minimum Hausdorﬀ distance forpoint sets under translation, Proc. 6th ACM Symp. Comp. Geometry, Berkeley(1990), 340–349.
[35] D.P. Huttenlocher, K. Kedem and J.M. Kleinberg, On dynamic Voronoi diagramsand the minimum Hausdorﬀ distance for point sets Under Euclidean motion in theplane, Proc. 8th ACM Symp. Comp. Geometry, Berlin (1992), 110–119.
[36] D.P. Huttenlocher, G.A. Klanderman and W.J. Rucklidge, Comparing images using
the Hausdorﬀ distance, IEEE Trans. Pattern Anal. Mach. Intell. 15 (1993), 850–863.
[37] D.P. Huttenlocher and W.J. Rucklidge, A multi-resolution technique for comparing
images using the Hausdorﬀ distance, Proc. IEEE Conf. Comput. Vis. Pattern Recognit., New York (1993), 705–706.

17[38] D.W. Jacobs, D. Weinshall and Y. Gdalyahu, Classiﬁcation with nonmetric distances:image retrieval and class representation, IEEE Trans. Pattern Anal. Mach. Intell. 22(2000), 583–600.
[39] O. Jesorsky, K.J. Kirchberg and R.W. Frischholz, Robust face detection using theHausdorﬀ distance, Proc. 3rd Int. Conf. AVBPA, Halmstad (2001), 90–95.
[40] J.L. Kelley, General Topology, Van Nostrand, New York, 1955.
[41] C.S. Kubrusly, Measure Theory: A First Course, Academic Press-Elsevier, San
Diego, 2007.
[42] C.S. Kubrusly, The Elements of Operator Theory, Birkhäuser-Springer, New York,
2011.
[43] M. Levandowsky and D. Winter, Distance between sets, Nature 234 (1971), 34–35.
[44] B. Li, Y. Shen and B. Li, A new algorithm for computing the minimum Hausdorﬀ
distance between two point sets on a line under translation, Inform. Process. Lett.
106 (2008), 52–58.
[45] A.H. Lipkus, A proof of the triangle inequality for the Tanimoto distance, J. Math.
Chem. 26 (1999), 263–265.
[46] D.G. Luenberger, Optimization by Vector Space Methods, Wiley, New York, 1969.
[47] E. Marczewski and H. Steinhaus, On a certain distance of sets and the corresponding
distance of functions, Colloq. Math. 6 (1958), 319–327.
[48] O. Nikodym, Sur une généralisation des intégrales de M.J. Radon, Fund. Math. 15,(1930), 131–179.
[49] J.-C. Pinoli, Mathematical Foundations of Image Processing and Analysis 2, Wiley,
London, 2014.
[50] R.T. Rockafeller and R.J.-B. Wets, Variational Analysis, Springer, Berlin, 1998.
[51] A. Rosenfeld, Distances between fuzzy sets, Pattern Recognition Lett. 3 (1985), 229–
233.
[52] G. Rote, Computing the minimum Hausdorﬀ-distance between two point sets on aline under translation, Inform. Process. Lett. 38 (1991), 123–127.
[53] W.J. Rucklidge, Locating objects using the Hausdorﬀ distance, Proc. 5th Int. Conf.
on Comp. Vis., Cambridge-MA (1995), 457–464.
[54] W. Rucklidge, Eﬃcient Visual Recognition Using Hausdorﬀ Distance, Springer,
Berlin, 1996.
[55] W.J. Rucklidge, Eﬃciently locating objects using the Hausdorﬀ distance, Int. J. Comput. Vis. 24 (1997), 251–270.

18[56] B. Sendov, Some questions of the theory of approximations of functions and sets in
the Hausdorﬀ metric, Russ. Math. Surv. 24 (1969), 143–183.
[57] B. Sendov, Hausdorﬀ Approximations, Kluwer, Dordretcht, 1990.
[58] B. Sendov, Hausdorﬀ distance and image processing, Russ. Math. Surv. 59 (2004),
319–328.
[59] R. Shonkwiler An image algorithm for computing the Hausdorﬀ distance eﬃciently
in linear time, Inform. Process. Lett. 30 (1989), 87–89.
[60] D.-G. Sim, O.-K. Kwon and R.-H. Park, Object matching algorithms using robust
Hausdorﬀ distance measures, IEEE Trans. Image Process. 8 (1999), 425–429.
[61] B. Takács, Comparing face images using the modiﬁed Hausdorﬀ distance, Pattern
Recognition 31 (1998), 1873–1881.
[62] C. Zhao, W. Shi and Y. Deng, A new Hausdorﬀ distance for image matching, Pattern
Recognition Lett. 26 (2005), 581–586.