Acta Informatica, 34(2):109–133, 1997.

Distance Measures for Point Sets and Their Computation^{∗}

Thomas Eiter Information Systems Dept. Technical University of Vienna

Heikki Mannila Dept. of Computer Science University of Helsinki

final manuscript

Abstract

We consider the problem of measuring the similarity or distance between two finite sets of points in a metric space, and computing the measure. This problem has applications in, e.g., computational geometry, philosophy of science, updating or changing theories, and machine learning. We review some of the distance functions proposed in the literature, among them the minimum distance link measure, the surjection measure, and the fair surjection measure, and supply polynomial time algorithms for the computation of these measures. Furthermore, we introduce the minimum link measure, a new distance function which is more appealing than the other distance functions mentioned. We also present a polynomial time algorithm for computing this new measure.

We further address the issue of defining a metric on point sets. We present the metric infimum method that constructs a metric from any distance functions on point sets. In particular, the metric infimum of the minimum link measure is a quite intuitive. The computation of this measure is shown to be in NP for a broad class of instances; it is NP-hard for a natural problem class.

keywords: distances, point sets, metrics, computational complexity, graph algorithms

∗Authors’ addresses: Thomas Eiter, Information Systems Department, Technical University of Vienna, Paniglgasse 16, A-1040 Vienna, Austria; Heikki Mannila, Department of Computer Science, University of Helsinki, P.O. Box 26 (Teollisuuskatu 23), SF-00014 University of Helsinki, Finland. email: eiter@vexpert.dbai.tuwien.ac.at, mannila@cs.helsinki.fi

1 Introduction

A function d : B × B → ℜ^{+} is a metric on a nonempty set B, if for all x, y, z ∈ B we have

1 d(x, y) = 0 if and only if x = y;

2 d(x, y) = d(y, x)

3 d(x, z) ≤ d(x, y) + d(y, z).

The function d is a distance function on B, if it satisfies (1) and (2).

In this paper we consider the following questions. (1) How can a distance function (or even metric) Δ on B be extended to a distance function or a metric d on the collection of all nonempty (finite) subsets of B? The extension condition we require is that for singletons, d agrees with Δ, that is, d({x}, {y}) = Δ(x, y) for all x and y from B. (2) Algorithms for computing such extensions, which run in polynomial time if possible.

Questions of this type arise in several areas, such as cluster analysis [2, 20], computational geometry [1], philosophy of science [17, 18, 13, 15], updating and revising theories [6, 25], arbitration between theories [19], and machine learning [12, 11, 26].

The best-known metric between subsets of a metric space is the Hausdorff metric, defined as

d_{h}(S_{1}, S_{2}) = max{max_{e∈S_{1}} min_{f∈S_{2}} Δ(e, f), max_{e∈S_{2}} min_{f∈S_{1}} Δ(e, f)}.

This metric is trivially computable in polynomial time, and it has some quite attractive properties. Unfortunately, it is not very well suited for some applications. The reason is that the Hausdorff distance does not take into account the overall structure of the point sets (see Figure 1).

Several alternative distance functions between subsets have been proposed in philosophy of science [13], for the objective of measuring the distance between theories in a logical language L. Here, the points of the metric space are the interpretations of L, whose distance is measured by some metric Δ; for propositional L, the Hamming distance between interpretations (i.e., the number of atoms on which they are different) is a natural choice. Each theory in L is identified with the set of its models, which thus is a set of points in the metric space.^{1} This way, measuring the distance between two theories is abstracted to measuring the distance between two sets of points in a metric space. In the particular case where one theory describes categorically TRUTH (i.e., the true state of affairs), the distance value is taken for a quantitative extent of the truthlikeness of the other theory. Notice that measuring theory distance in this setting has suggestive applications for theory revision (change a theory into the closest possible one that meets the revision) and arbitration between theories.

1Theories are thus not necessarily categorical, and reflect incomplete information about certain facts; they may leave open several possibilities for the true state of affairs, which is considered to be among the models.

An example can be drawn from the court domain (cf. [19]). Suppose that in a trial two testimonies (which can be represented as theories) are very similar while a third is much different. Given that the witnesses are independent of each other, the belief of the jury in the reliability of the third testimony will naturally decrease with growing distance to the other testimonies.

Another use of such distance functions between subsets is in the new area of knowledge discovery in databases [5, 16], where one often has to choose between or form clusters from different rules discovered from the data. The rules can be identified with the data points to which they apply, and then rule distance can be computed by using a distance function for subsets [21].

Particularly appealing among the distance functions between point sets that have been proposed in philosophy of science are the minimum distance measure, d_{md}, the surjection measure, d_{s}, and the fair surjection measure, d_{fs}. Intuitively, these measures compute the amount of distance covered when each point of one set is mapped to a point of the other set under some restrictions. Under d_{md}, each point of the one set is mapped to the point of the other set that is closest to it; for the surjection distance d_{s}, one considers all surjections from one set to the other and computes the length of the elements in the surjection; for the fair surjection distance d_{fs}, one additionally requires that the surjection has to be fair in the sense that it distributes the points as evenly as possible.

While the properties and relationships of these measures have been considered, their computation was left open. In particular, it was unclear for some of these measures whether they can be computed efficiently if this is possible for the underlying distance function on points.

Another interesting issue is an appealing distance function on sets of points which satisfies the triangle inequality, i.e., a metric on the sets of points. Note that the distance measures d_{md}, d_{s}, and d_{fs} do not satisfy the triangle inequality.

The main results of this paper can be shortly summarized as follows.

• We propose a new measure, the link measure d_{l}, which is motivated by some intuitive problems with the other measures.

• We show that the measures d_{md}, d_{s}, d_{fs}, and d_{l} can be computed in polynomial time under very general assumptions. While this is trivial for d_{md}, the algorithms for the other measures use sophisticated matching and network flow techniques.

• We introduce the metric infimum method, a general construction that produces for a given distance function d on sets of points a refinement d^{ω} of d which is a metric and hence satisfies the triangle inequality. The intuition in the construction is to consider in computing the distance between two sets S_{1} and S_{2} all possible sequences of intermediate sets and take the minimum distance obtainable by using such a sequence. We show that applied to d_{md}, d_{s}, d_{fs} and d_{l}, this construction produces only two different metrics.

• We present an algorithm for computing the refined link measure d_{l}^{ω} which makes use of standard graph algorithms. This algorithm is not polynomial; we show, however, that a polynomial algorithm is not likely to exist by proving that computing d_{l}^{ω} is NP-hard. On the other hand, our results imply that for a broad class of instances, computing d_{l}^{ω} is NP-easy, i.e., possible in polynomial time with an oracle for some problem in NP (cf. [8]), and hence not much harder than the NP-complete problems.

The rest of the paper is organized as follows. After introducing the some notation at the end of the introduction, we review in Section 2 measures for the distance of point sets derived from measures of theory distance from [13, 22, 14]. Furthermore, in this section we define the new minimum link measure d_{l} and compare it to the distance measures d_{md}, d_{s}, and d_{fs}. In Section 3 we analyze the structural properties of d_{s}, d_{fs}, and d_{l}, which are employed by our algorithms. Section 4 is devoted to the computation of the distance measures d_{md}, d_{s}, d_{fs}, and d_{l}, for which we describe polynomial time algorithms. In Section 5 we provide the metric infimum method and study properties of the metric produced from a distance function. In Section 6 we consider computing the d_{l}^{ω} measure and show NP-completeness of the associated decision problem. The concluding Section 7 states some open problems and issues for further work.

We start by defining some notation. We assume that B is finite; however, the constructions can be carried out also for infinite B under some conditions. We shall discuss this issue in Section 7. Elements of B are referred to as points. The set of all nonempty subsets of B is denoted by P_{∅}(B). We use a special notation for the minimum distance of an element x from a set S:

Δ_{m}(x, S) = min_{y∈S} Δ(x, y).

We call each point y ∈ S such that Δ(x, y) = Δ_{m}(x, S) a closest point of S for x. We further denote by μ a function μ : B × P_{∅}(B) → B that for all x and nonempty S yields a closest point of S for x, i.e.

μ(x, S) = y, such that y ∈ S and Δ(x, y) = Δ_{m}(x, S).

We assume that the reader knows about basic concepts of graph theory (cf. [3, 24]) and NP-completeness (cf. [8]).

Let the union of a family of graphs {G_{i} = (V_{i}, E_{i}) : 1 ≤ i ≤ n} be the graph (⋃_{i} V_{i}, ⋃_{i} E_{i}). The union is disjoint if V_{i} ∩ V_{j} = ∅, 1 ≤ i < j ≤ n. In case that the G_{i} are weighted, i.e. G_{i} = (V_{i}, E_{i}, w_{i}), the union (⋃_{i} V_{i}, ⋃_{i} E_{i}, ⋃_{i} w_{i}) is only defined if the weight function ⋃_{i} w_{i} is well-defined.

We denote by deg(v, G) the degree of vertex v in the graph G. A graph G is called a line iff it is a tree (i.e. a connected acyclic graph) on 2 vertices, and G is called a star iff it is a tree on > 2 vertices and exactly one vertex v has degree > 1, which is called the center of the star.

In our examples, we use as the base set B a finite fragment of the integral plane with, unless stated otherwise, the Manhattan metric, which is defined by

Δ_{M}((x_{1}, y_{1}), (x_{2}, y_{2})) = |x_{1} − x_{2}| + |y_{1} − y_{2}|.

2 Distance measures for point sets

In this section, we review some of the distance functions which have been proposed in the literature. A comparative analysis of these measures, from the viewpoint of philosophy of science, can be found in [13]. We further propose a new distance function which overcomes weaknesses of previously suggested distance functions in some situations.

Hausdorff distance (d_{h}) The Hausdorff distance d_{h} can be defined using the Δ_{m} notation as

d_{h}(S_{1}, S_{2}) = max{max_{e∈S_{1}} Δ_{m}(e, S_{2}), max_{e∈S_{2}} Δ_{m}(e, S_{1})}.

This function defines a distance function on P_{∅}(B), which is a metric if Δ is a metric ([4]). The problem of computing the Hausdorff distance between geometric entities has been considered in the area of computational geometry (see, e.g., [9]).

The problem with d_{h} is that it is very sensitive to extreme points in the sets S_{1} and S_{2}. (See Figure 1.)

[figure: a; b; c; d; e; f]

Figure 1: Sets {a, b, c, d, e} and {a} are equally distant from {f} according to the Hausdorff metric.

In fact, for every pair of sets S_{1} and S_{2} there are points x_{1} ∈ S_{1} and x_{2} ∈ S_{2} such that d_{h}(S_{1}, S_{2}) = d_{h}({x_{1}}, {x_{2}}) = Δ(x_{1}, x_{2}). We are looking for a distance measure that attempts to combine information about the distances between the elements of S_{1} and S_{2}. Therefore we do not consider d_{h} in the sequel.

Sum of minimum distances (d_{md}) The sum of minimum distances function d_{md} [13] is defined by

d_{md}(S_{1}, S_{2}) = \frac{1}{2} ( ∑_{e∈S_{1}} Δ_{m}(e, S_{2}) + ∑_{e∈S_{2}} Δ_{m}(e, S_{1})) .

This function takes into account the distances between each element and the other set.

Surjection distance (d_{s}) Oddie [14] suggested defining the distance between two sets by considering surjections that map the larger set to the smaller set. This leads to the following distance function:

d_{s}(S_{1}, S_{2}) = min_{η} ∑_{(e_{1},e_{2})∈η} Δ(e_{1}, e_{2}),

where the minimum is taken over all surjections η from the larger of the sets S_{1} and S_{2} to the smaller.

Fair surjection distance (d_{fs}) In order to overcome certain unsatisfactory behavior of the surjection measure d_{s}, Oddie introduced a variant of the surjection measure, in which admissible surjections must be fair. A surjection η between S_{1} to S_{2} is fair, if η maps the elements of S_{1} as evenly as possible onto the elements of S_{2}, i.e., | |η^{−1}(x)| − |η^{−1}(y)| | ≤ 1 for all x, y ∈ S_{2}, where η^{−1}(z) = {w : η(w) = z}. Thus,

d_{fs}(S_{1}, S_{2}) = min_{η′} ∑_{(e_{1},e_{2})∈η′} Δ(e_{1}, e_{2}),

where the minimum is taken over all surjections.^{2}

Link distance (d_{l}) We propose an alternative distance measure between two sets. Given two sets S_{1}, S_{2} ⊆ B, a linking between S_{1} and S_{2} is a relation R ⊆ S_{1} × S_{2} satisfying

(1) for all e_{1} ∈ S_{1} there exists e_{2} ∈ S_{2} such that (e_{1}, e_{2}) ∈ R, and

(2) for all e_{2} ∈ S_{2} there exists e_{1} ∈ S_{1} such that (e_{1}, e_{2}) ∈ R. The minimum link distance d_{l} between subsets S_{1} and S_{2} is defined by

d_{l}(S_{1}, S_{2}) = min_{R} ∑_{(e_{1},e_{2})∈R} Δ(e_{1}, e_{2}),

where the minimum is taken over all relations R such that R is a linking between S_{1} and S_{2}.

For convenience, we adopt the following convention. For any binary relation R ⊆ B × B, the cost of R, c(R), is c(R) = ∑_{(e_{1},e_{2})∈R} Δ(e_{1}, e_{2}). Notice that the cost of a surjection, a fair surjection, and a linking between sets S_{1} and S_{2} is implicit by this definition.

Example 2.1 Consider the sets S_{1} = {a, b, c, e} and S_{2} = {c, d} in Figure 2. The distance functions d_{md}, d_{s}, d_{fs} and d_{l} evaluate as follows.

d_{md}(S_{1}, S_{2}) = ((0 + 1) + (0 + 1 + 1 + 2))/2 = 5/2.
d_{s}(S_{1}, S_{2}) = 5; the surjection η = { (a, c), (b, c), (e, c), (c, d) }

is optimal and c(η) = 2 + 1 + 1 + 1 = 5.

d_{fs}(S_{1}, S_{2}) = 6; the fair surjection η′ = { (a, c), (b, d), (e, c), (c, d) }

is optimal and c(η′) = 2 + 2 + 1 + 1 = 6.

d_{l}(S_{1}, S_{2}) = 5; the linking L = {(a, c), (b, c), (e, c), (c, d)}
is optimal and c(L) = 1 + 1 + 1 + 2 = 5. □

2Oddie [14] actually considered only the version normalized by the size of the larger set.

[figure: a; b; c; d; e]

Figure 2: Examples of the distance measures; the distance from a to b is the unit distance.

The following proposition is easily derived from the definitions.

Proposition 2.1 Assume that Δ is a distance function on B. Then d_{md}, d_{s}, d_{fs}, and d_{l} are distance functions on P_{∅}(B). □

For a discussion of the relationships and properties of d_{md}, d_{s}, and d_{fs}, the reader is referred to [13]. As mentioned above, these functions have been considered for measuring the distance between logical theories. However, they have also applications in other contexts.

The minimum distance measure is appealing in many cases. For example, suppose the distance between two countries with respect to travelling should be determined. For this purpose, the (possibly normalized) result of the d_{md} function, evaluated on sets S_{1}, S_{2} of representative cities of the countries seems well apt; it amounts to the least cost of getting from a city in one country to a closest city in the other country, and takes account of each possible starting point. The intercity distance Δ may be measured in different ways, e.g. in terms of the geographical distance, or by the cheapest ticket (in this case, Δ may not be a metric). An example for an application of the surjection distance measures in the plane is given below.

We argue that the minimum link measure is more appealing than the other measures in some scenarios. A situation in which d_{l} is intuitively more appealing than d_{s} or d_{fs} is sketched in Figure 3, where B is the plane and Δ is the euclidean distance between points.^{3} (Notice that d_{s} and d_{fs} take the same value as each surjection between S_{1} and S_{2} is trivially fair.) Each pair of the minimum linking between S_{1} and S_{2} is represented by a line between dots. The small value of d_{l} seems to represent the intuitive distance between the point sets better than the larger value of d_{s} (resp. d_{fs}). Note that the value of d_{s} (resp. d_{fs}) increases if the distance between the left and the right group of three vertices increases, while the value of d_{l} remains the same; this behavior seems to be more intuitive.

3Similar situations can be found for the integral plane and the Manhattan metric.

[figure: S_{1}; S_{2}]

Figure 3: Situation favoring the minimum link measure d_{l} over d_{s} and d_{fs}.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; (c); (b); (a)]

Figure 4: Situation favoring the minimum link measure d_{l} over d_{dmd}. (I)

Comparing d_{l} to d_{md}, we find that the latter acts in a sense locally (or pointwise), since the distance between sets S_{1} and S_{2} is basically the sum of the distances of each point in the one set to the other set. On the other hand, d_{l} acts globally (or setwise), since it aims at minimizing the total distance value rather than the distance value of each point. In particular, it is possible that an optimal linking L between S_{1} and S_{2} contains a pair (e_{1}, e_{2}) such that Δ(e_{1}, e_{2}) > Δ_{m}(e_{1}, S_{2}) and Δ(e_{1}, e_{2}) > Δ_{m}(e_{2}, S_{1}) (see Figure 4(b)). In some situations, setwise distance is more appropriate than pointwise.

For example, assume that point sets are the sites of organizations, and that an organization is interested in a working exchange program with another organization such that mutual connections between sites are established, involving all sites of both organizations. For example, organizations might be associations of universities from the same country. Here, the d_{l} measure is more appropriate for measuring the geographical distance between the organizations than the d_{md} measure. An example is given in Figure 4. For the situation in (a), d_{l} and d_{md} amount to the connections between sites as shown in (b) and (c), respectively. The solution in (b) can be considered preferable; it seems to correspond more closely with the intuition.

The global operation mode of d_{l} makes it also appealing for measuring the distance between logical theories, based on a revision argument. Suppose that as in Section 1, the points of a metric space are interpretations of a logical language L, and that theories are identified with the sets of their models (i.e., sets of points).^{4} The distance between two theories S_{1} and S_{2} can be seen as the “cost” for a believer to change his current view, given by S_{1}, to S_{2}. For this purpose, each model in S_{1} must be revised to some model in S_{2}, and all models of S_{2} must be covered; it is reasonable to allow that the same model from S_{1} is multiply revised to different models in S_{2} (think of a model in S_{1} which is very close to several models in S_{2}; see also Figure 3), and that different models in S_{1} can be revised to the same model in S_{2}. The cost of a particular revision process is the sum of the distances between each model of S_{1} and its revisions. Notice that by inverting each revision step, S_{2} can be revised to S_{1} and thus the cost of revision is symmetric. The least cost for a revision process between S_{1} and S_{2} is thus a suggestive value for the distance between S_{1} and S_{2}. However, this is precisely the value computed by d_{l}. Notice that d_{md} is less appealing for this application; due to pointwise minimization, this function reflects the cost of revising one set to a close part of the other set rather than to the whole set.

4By the assumptions from above, only finitely many interpretations may be in the metric space.

3 Link graph

We associate with each linking L between sets of points S and S′ a graph G(L), which we call the link graph of L. The link graph is useful for studying structural properties of linkings.

Assume that S = {s_{1}, …, s_{n}} and S′ = {s′_{1}, …, s′_{m}} (note that S_{1} ∩ S_{2} ≠ ∅ is possible). Let V_{1} = {v_{1}^{1}, …, v_{n}^{1}} and V_{2} = {v_{1}^{2}, …, v_{m}^{2}} be disjoint sets of vertices. For every linking L between S and S′, G(L) is the undirected bipartite graph (V_{1} ∪ V_{2}, E), where E = {{v_{i}^{1}, v_{j}^{2}} : (s_{i}, s′_{j}) ∈ L}.

We note some useful structural properties of the link graph.

Proposition 3.1 For each surjection η : S → S′, the graph G(η) is the disjoint union of |S′| lines and stars, whose centers are all from V_{2}.

Proof. Each set {v_{j}^{2}} ∪ {v_{i}^{1} : s_{i} ∈ η^{−1}(s′_{j})}, where 1 ≤ j ≤ m, induces a line or star in G(η). G(η) is clearly the disjoint union of all these stars and lines.□

Proposition 3.2 Let L be an optimal linking between S and S′. Then G(L) is the disjoint union of stars and lines.

For example, if L is a first-order language over a finite vocabulary, all interpretations of L in a fixed finite domain might be included. In particular, a propositional L over a finite set of atoms has only finitely many interpretations. Such languages are relevant in the area of data and knowledge representation.

[figure: v_{1}^{1}; v_{2}^{1}; v_{3}^{1}; v_{4}^{1}; v_{5}^{1}; v_{6}^{1}; v_{8}^{2}; v_{7}^{2}; v_{6}^{2}; v_{5}^{2}; v_{4}^{2}; v_{3}^{2}; v_{2}^{2}; v_{1}^{2}]

Figure 5: G(L) that is the disjoint union of stars and lines.

Proof. If not, an edge can be removed from G(L) so that the resulting graph is G(L′) for a linking L′ ⊆ L between S and S′, which contradicts optimality of L. □

Thus, for every optimal linking L between S and S′, we can imagine G(L) as a forest of stars and lines. By taking the metric Δ into account, the following properties of the stars in this forest can be derived.

For a disjoint union G(L) of a forest of stars and lines, denote by cst(L) the set of all centers of the stars of G(L). For example, in Figure 5 we have cst(L) = {v_{1}^{1}, v_{3}^{1}, v_{7}^{2}}.

It can be easily seen that for an optimal linking L, each center x of a star in G(L) is connected only to vertices y such that x corresponds to a closest point of S (resp. S′) for y.

Proposition 3.3 Let L be an optimal linking between S and S′ and let {v_{i}^{1}, v_{j}^{2}} be an edge of G(L). If v_{i}^{1} ∈ cst(L), then Δ(s_{i}, s′_{j}) = Δ_{m}(s′_{j}, S), and if v_{j}^{2} ∈ cst(L), then Δ(s_{i}, s′_{j}) = Δ_{m}(s_{i}, S′).

An analogous proposition holds on optimal surjections.

Proposition 3.4 If η : S → S′ is an optimal surjection between S and S′, then for each i and j, 1 ≤ i ≤ n, 1 ≤ j ≤ m, such that {v_{i}^{1}, v_{j}^{2}} is an edge of G(η) but not a line, we have Δ(s_{i}, s′_{j}) = Δ_{m}(s_{i}, S′).

4 Computing the distance measures

In this section, we investigate computing the distance functions from the previous section. While it is clear that under suitable assumptions computing d_{md} is simple and efficient, this is not obvious for d_{s}, d_{fs}, and d_{l}. It turns out that all these distance functions are computable in polynomial time, however.

4.1 Assumptions, graph matchings, and network flows

We need some assumptions for distance computation first. The input for computing d(S, S′) consists of the sets S = {s_{1}, …, s_{n}} ⊆ B and S = {s′_{1}, …, s′_{m}} ⊆ B, such that n ≥ m ≥ 1. Furthermore, we assume that the distance function Δ on B takes rational values and can be computed in polynomial time.^{5}

Our algorithms make use of graph matching and network flow techniques. A matching of an undirected weighted graph G = (V, E, w) is a set of edges M ⊆ E such that for each pair of distinct e, e′ ∈ M, it holds that e∩e′ = ∅; the matching M is called perfect iff ⋃ M = V. The weight w(M) of M is w(M) = ∑_{e∈M} w(e). It is wellknown that a perfect matching of minimum weight (hence, by our assumptions, also its weight) in G can computed in polynomial time (cf. [10]). Specialized algorithms have been developed for bipartite graphs and for other graph classes.

Proposition 4.1 (cf. [10, p.93,Theorem 14]) Let G = (V_{1} ∪ V_{2}, E, w) be a bipartite weighted graph with nonnegative weights from the reals. Then, a perfect matching M in G of minimal weight (if it exists) can be computed in time

O ( \frac{|V_{1}|·|E|·log |V_{1}|}{max(1, log(|E|/|V_{1}|))} ) . □

A network N = (V, E, cap, c) is a directed weighted graph (V, E, c) where each edge e ∈ E has assigned a capacity cap(e) ∈ ℜ^{+}; the second weight function c assigns a cost c(e) to each edge e. Let s and t be specified vertices from V. An s-t-flow (or simply flow, if s and t are understood) on N is a function f : E ∪{(x, y) : (y, x) ∈ E} → ℜ^{+} such that

(i) for each (x, y) ∈ E, 0 ≤ f(x, y) ≤ cap(x, y) and f(y, x) = −f(x, y), and

(ii) for each x ≠ s, t we have ∑_{(x,y)∈E} f(x, y) = ∑_{(z,x)∈E} f(z, x).

The first condition states that the flow on an edge is legal and that on a “loop” (x, y), (y, x), the flow must be zero. The second condition states that what flows in, flows out of every node distinct from s and t. The value |f| of flow f is defined as |f| = ∑_{(s,x)∈E} f(s, x), and the cost c(f) of f is defined as c(f) = ∑_{e∈E} w(e)f(e).

A maximum flow is any flow f such that |f| is a maximum over all flow values, and a minimum cost flow of value v is any flow f such that |f| = v and c(f) is minimum over the costs of all flows of value v. The integrality theorem for minimum cost flows states the following.

5This assumption is stricter than necessary, but avoids problems arising if the values of Δ are possibly difficult to compare to a number or among each other (cf. [7]).

[figure: 1; 1; 6; 2; 3; 2; 3; 5; 7; x_{3}; x_{1}; x_{2}; u_{2}; u_{1}; v_{1}; Δ(s, s′); 3; 7; 5; 6; 2; 1; s′_{2}; s′_{1}; s_{3}; s_{2}; s_{1}]

Figure 6: Graph G for S = {s_{1}, s_{2}, s_{3}} and S′ = {s′_{1}, s′_{2}}. The bold edges constitute a minimum weight perfect matching of G.

Theorem 4.2 ([24, p. 593]) If all capacities in a network N = (V, E, cap, c) are integers, then there exists a maximum flow which is integral and has minimum cost (over all maximum flows).

4.2 Computing the surjection distance d_{s}

First we consider computing d_{s} for S = {s_{1}, …, s_{n}} and S′ = {s′_{1}, …, s′_{m}}. We show that computing d_{s}(S, S′) can be reduced to computing the cost of a minimum weight perfect matching in a graph in polynomial time.

Construct from S and S′ an complete bipartite weighted graph G = (X∪Y, E, w) as follows. Let k = n − m. Let X = {x_{1}, …, x_{n}} and Y = U ∪ V, where U = {u_{1}, …, u_{m}} and V = {v_{1}, …, v_{k}}. The weight function w is defined as follows.

w(e) = \{ \begin{matrix}Δ(s_{i}, s′_{j}) & for e = \{x_{i}, u_{j}\}, 1 ≤ i ≤ n, 1 ≤ j ≤ m; \\ Δ_{m}(s_{i}, S′) & for e = \{x_{i}, v_{j}\}, 1 ≤ i ≤ n, 1 ≤ j ≤ k. \end{matrix}

The link graph G(η) of an optimal surjection is a collection of stars and lines. The auxiliary vertices v_{i} allow us to obtain from G(η) a graph with a perfect matching: from each star of G(η), all vertices except one are linked to an auxiliary node.

Figure 6 shows an example of the construction, where S = {s_{1}, s_{2}, s_{3}}, S′ = {s′_{1}, s′_{2}}, and the distance function Δ is assumed to yield the following values: Δ(s_{1}, s′_{1}) = 1, Δ(s_{2}, s′_{1}) = 2, Δ(s_{3}, s′_{1}) = 6, Δ(s_{1}, s′_{2}) = 5, Δ(s_{2}, s′_{2}) = 7 and Δ(s_{3}, s′_{2}) = 3. Notice that for a minimum weight perfect matching M of G, we have w(M) = 6.

Lemma 4.3 Let M be an arbitrary minimum weight perfect matching of G and let η be an optimal surjection between S and S′. Then w(M) = c(η).

Proof. We show first that w(M) ≤ c(η). From an optimal surjection η we get a perfect matching M′ of G such that w(M′) ≤ c(η) as follows. We take all edges {x_{f(j)}, u_{j}} such that f(j) is the least index of any s_{h} in η^{−1}(s′_{j}), and all edges {x_{g_{i}}, v_{i}} for an arbitrary enumeration x_{g_{1}}, x_{g_{2}}, … x_{g_{k}} of the remaining x vertices. M′ consists of the following edges:

(i) {x_{f(j)}, u_{j}} for every j with 1 ≤ j ≤ m, where f(j) = min{i : s_{i} ∈ η^{−1}(s′_{j})};

(ii) {x_{g_{i}}, v_{i}} for every i with 1 ≤ i ≤ k, where {x_{g_{1}}, …, x_{g_{k}}} = X−{x_{f(1)}, …, x_{f(m)}}.

It is not hard to see that M′ is indeed a perfect matching in G. Since w(x_{i}, v_{l}) ≤ w(x_{i}, u_{j}), for all i, j, l with 1 ≤ i ≤ n, 1 ≤ j ≤ m, and 1 ≤ l ≤ k, we have that w(M′) ≤ c(η); hence, it follows that w(M) ≤ c(η).

On the other hand, w(M) ≥ c(η) holds. Indeed, from a matching M we can define a surjection η′ : S → S′ as follows. Let for all i with 1 ≤ i ≤ n be

η′(s_{i}) = \{ \begin{matrix}s′_{j}, & if \{x_{i}, u_{j}\} ∈ M; \\ μ(s_{i}, S′) & if \{x_{i}, v_{l}\} ∈ M for some l. \end{matrix}

It is easy to see that η′ is well-defined and indeed a surjection, and that c(η′) = w(M). Hence, it follows that w(M) ≥ c(η); the result follows. □

Theorem 4.4 The distance function d_{s} is computable in polynomial time.

Proof. Consider sets S and S′. The graph G for S and S′ is clearly constructible in polynomial time. Since a minimum weight perfect matching M in G can be constructed in polynomial time, by our assumptions w(M) can be computed in polynomial time. Hence the result follows. □

Remark: Since the graph G is bipartite, a minimum weight perfect matching in G can be computed in time O(n^{3}) (cf. Proposition 4.1; |V_{1}| = n, |E| = n^{2}).

4.3 Computing the fair surjection distance d_{fs}

Next we show that d_{fs} can be efficiently computed by solving a network flow problem.

Given sets S = {s_{1}, …, s_{n}} and S′ = {s′_{1}, …, s′_{m}} with 1 ≤ m ≤ n, we construct a network N = (V, E, cap, c) as follows. Let V = X ∪ Y ∪ {s, t}, where X = {x_{1}, …, x_{n}} and Y = {y_{1}, …, y_{m}} are disjoint. The set of edges E consists of four groups of edges e with capacity cap(e) and cost c(e) as follows. Let c_{0} = ⌈n/m⌉.

(i) (s, x_{i}), for every i with 1 ≤ i ≤ n, for which cap(s, x_{i}) = 1 and c(s, x_{i}) = 0,

[figure: t; s; x_{1}; x_{3}; y_{2}; y_{1}; (1,0); (1,0); (1,Ω); (1,Ω); (1,1); (2,0); (2,0); (1,0); (1,3); (1,6); (1,5); (1,7); x_{2}; (1,2)]

Figure 7: Network N for S = {s_{1}, s_{2}, s_{3}}, S′ = {s′_{1}, s′_{2}}. The flow f assigning cap(e) to the bold edges and 0 to all others is a minimum cost maximum flow.

(ii) (x_{i}, y_{j}), for every i and j with 1 ≤ i ≤ n, 1 ≤ j ≤ m, for which cap(x_{i}, y_{j}) = 1 and c(x_{i}, y_{j}) = Δ(s_{i}, s′_{j}),

(iii) (y_{i}, t), for every i with 1 ≤ i ≤ m, for which cap(y_{i}, t) = c_{0} and c(y_{i}, t) = 0, and

(iv) (s, y_{i}), for every i with 1 ≤ i ≤ m, for which cap(s, y_{i}) = 1 and c(s, y_{i}) = Ω,

where Ω is an arbitrary real number greater than ∑_{i,j} Δ(x_{i}, y_{j}). Figure 7 shows an example of the construction, where S, S′, and Δ are as above.

The intuition behind N is as follows. Mapping S to S′ corresponds to forwarding from every vertex x_{i} one unit of flow coming from the source s to one of the vertices y_{j}, from which it is transported to the sink t. The capacity of the edge from y_{j} to t is restricted such that no more units can be transported than elements from S can be mapped to s′_{j} by a fair surjection. The edges from s to the y_{j} vertices assure that at least as many units reach y_{j} from the x_{i} vertices as elements from S must at least be mapped to y_{j} in any fair surjection. Each such edge can transport one unit of flow, but only at the extremely high cost Ω. Thus, as few units as necessary will be transported via such edges in a maximum flow.

It is straightforward to check that for any S and S′, a maximum s-t flow in N has value c_{0}m = n + k, where

k = \{ \begin{matrix}0, & if n = i·m, for some integer i ≥ 0 \\ m − (n mod m), & otherwise. \end{matrix}

In a maximum flow of minimum cost exactly k units are transported from s directly to the y_{j} vertices and all other units via the x_{i} vertices, such that the flow corresponds to an optimal fair surjection between S and S′. Since all capacities are integers, the integrality theorem for minimum cost flows asserts that an integral maximum s-t flow f of minimum cost on N exists. Clearly, each e ∈ E with cap(e) = 1 has in f value 0 or 1, i.e., cap(e). It can be easily seen that in f every other edge e also has value 0 or cap(e).

For an example, consider Figure 7. There, k = 1. The cost of the flow f is c(f) = 6 + 1·Ω. On the other hand, η′ = { (s_{1}, s′_{1}), (s_{2}, s′_{1}), (s_{3}, s′_{2}) } is an optimal fair surjection between S and S′ with c(η) = 6.

The next lemma states that the construction works correctly.

Lemma 4.5 Let f be a maximum s-t flow of minimum cost on N and let η be an optimal fair surjection between S and S′. Then c(f) = c(η) + kΩ.

Proof. First observe that a surjection η between S and S′ is a fair if and only if ⌊n/m⌋ ≤ |η^{−1}(s′_{j})| ≤ ⌈n/m⌉ for every j, 1 ≤ j ≤ m.

We show that c(f) ≥ c(η) + kΩ. By the integrality theorem for minimum cost flows, we can assume that f is integral. As easily seen, f assigns 1 to exactly k edges from (s, y_{1}), …, (s, y_{m}), to all edges (s, x_{i}), where 1 ≤ i ≤ n, and to exactly one of the edges (x_{i}, y_{1}), …,(x_{i}, y_{m}) for every i with 1 ≤ i ≤ m; let (x_{i}, y_{g(i)}) be this edge.

Define the mapping ζ : S → S′ by ζ(s_{i}) = s′_{g(i)}, for every i with 1 ≤ i ≤ n. We show that ζ is a fair surjection between S and S′. Assume this does not hold. Then, there must exist a j with 1 ≤ j ≤ m, such that f assigns 1 to fewer than c_{0} − 1 edges from (x_{1}, y_{j}), …,(x_{n}, y_{j}) and 0 to the others. The flow value |f| = c_{0}m implies that c_{0} units reach y_{j}, i.e. ∑_{(x,y_{j})∈E} f(x, y_{j}) = c_{0}. Note that y_{j} is reachable by an edge only from x_{1}, …, x_{n} and s. Since each of these edges has capacity 1, it follows that no more than c_{0} − 1 units reach y_{j}, which is a contradiction. Thus ζ is a fair surjection. It is easy to check that c(f) = c(ζ) + kΩ.

Since η is an optimal fair surjection, we thus have that c(f) ≥ c(η) + kΩ.

Now we show that c(f) ≤ c(η) + kΩ. We construct from a fair surjection η a flow f_{η} on network N as follows.

f_{η}(e) = \{ \begin{matrix}c_{0}, & if e = (y_{j}, t) where 1 ≤ j ≤ m; \\ 1, & if e = (s, x_{i}) where 1 ≤ i ≤ n, \\ & or e = (s, y_{j}) where 1 ≤ j ≤ m is such that |η^{−1}(s′_{j})| < c_{0}, \\ & or e = (x_{i}, y_{η(s_{i})}) where 1 ≤ i ≤ n; \\ 0, & otherwise. \end{matrix}

Clearly, f_{η} is an s-t flow of value c_{0}m and hence maximum. As readily checked, c(f_{η}) = c(η) + kΩ. Thus we get that c(f) ≤ c(η) + kΩ. The result follows. □

Theorem 4.6 The function d_{fs} is computable in polynomial time.

Proof. Consider sets S and S′. The network N can be easily constructed from S and S′ in polynomial time. Since all capacities are integer, a minimum integral s-t flow of value v = c_{0}m on N is computable in time

O(ve_{N}(log n_{N})/ max{log(e_{N}/n_{N}), 1}), n_{N} = |V |, e_{N} = |E|

[10, p. 92, Theorem 13]. The result follows. □

4.4 Computing the link distance d_{l}

It remains to show that the link distance function d_{l} is computable in polynomial time. As in the case of d_{s}, we reduce this problem to a perfect matching problem.

Let again S = {s_{1}, …, s_{n}} and S′ = {s′_{1}, …, s′_{m}}. We define a complete bipartite weighted graph G = (A ∪ B, E, w) as follows: A = {a_{1}, …, a_{n}}, B = {b_{1}, …, b_{m}}, and for each edge e = {a_{i}, b_{j}} of G, w(e) = Δ(s_{i}, s′_{j}). Intuitively, G is a graph in which each s_{i} ∈ S (resp. s′_{j} ∈ S′) is connected to every s′_{j} (resp. s_{i}) at the cost of the distance Δ(s_{i}, s′_{j}). Let G′ be a zero-weight copy of G, i.e., G′ = (A′ ∪ B′, E′, w′) is a complete bipartite weighted graph where A′ = {a′_{1}, …, a′_{n}}, B′ = {b′_{1}, …, b′_{m}}, (A ∪ B) ∩ (A′ ∪ B′) = ∅, and w′(e) = 0 for each edge e. From G and G′ we define the graph G′′ by taking the union of G and G′ and connecting every a_{i} and b_{j} to a′_{i} and b′_{j}, respectively, by weight equal to its nearest neighbor in G. That is,

G′′ = (V′′, E′′, w′′),

where

V′′ = A ∪ A′ ∪ B ∪ B′,
E′′ = E ∪ E′ ∪ {{a_{i}, a′_{i}}, {b_{j}, b′_{j}} : a_{i} ∈ A, b_{j} ∈ B},

w′′(e) = \{ \begin{matrix}w(e), & for e ∈ E; \\ w′(e), & for e ∈ E′; \\ Δ_{m}(s_{i}, S′), & for e = \{a_{i}, a′_{i}\}, 1 ≤ i ≤ n; \\ Δ_{m}(s′_{i}, S), & for e = \{b_{j}, b′_{j}\}, 1 ≤ j ≤ m. \end{matrix}

Figure 8 shows an example of the construction; S, S′, and Δ are as above. The set

[figure: 1; 2; 3; 3; 1; 1; b_{1}; a′_{3}; a_{3}; 0; 6; 2; 0; a′_{2}; a_{2}; a′_{1}; a_{1}; 0; 0; 0; 0; b′_{1}; b′_{2}; b_{2}; 3; 7; 5]

Figure 8: The graph G′′ for S = {s_{1}, s_{2}, s_{3}}, S′ = {s′_{1}, s′_{2}}. The bold edges constitute a minimum weight perfect matching.

of edges outlined in bold face constitute a perfect matching M of minimum weight; M has value w(M) = 6. Notice that the link measure between S and S′ amounts to the same value: the linking L = {(s_{1}, s′_{1}), (s_{2}, s′_{1}), (s_{3}, s′_{2})} is an optimal linking between S and S′ with cost c(L) = 6.

Lemma 4.7 Let L be an optimal linking between S and S′, and let M be a minimum weight perfect matching in G′′. Then c(L) = w(M).

Proof. We first show that w(M) ≤ c(L). We get from L a perfect matching M′ in G′′ whose weight is equal to the cost of L as follows. Let the centers of the stars of G(L) be cst(L) = {y_{1}, …, y_{k}}, and let x_{1}, …, x_{k} be arbitrary vertices from G(L) such that x_{i} is connected by an edge to y_{i}, for all i = 1, …, k. Then, define that M′ consists of the following edges:

(i) {a_{i}, b_{j}} and {a′_{i}, b′_{j}}, for all edges {v_{i}^{1}, v_{j}^{2}} of G(L) such that v_{i}^{1}, v_{j}^{2} ∉ {x_{1}, …, x_{k}};

(ii) {a_{i}, a′_{i}}, for every i = 1, …, n such that v_{i}^{1} ∈ {x_{1}, …, x_{k}};

(iii) {b_{j}, b′_{j}}, for every j = 1, …, m such that v_{j}^{2} ∈ {x_{1}, …, x_{k}}.

By Proposition 3.2, G(L) is the disjoint union of stars and lines. Hence, it is not hard to see that M′ is a perfect matching in G′′. Moreover, by the construction of G′′ and the definition of M′, it follows immediately from Proposition 3.3 that w(M′) = c(L). It follows that w(M) ≤ c(L).

Now we show that also w(M) ≥ c(L). From M we can get a linking L′ between S and S′ whose cost is equal to w(M) as follows. Define that L′ contains all pairs (v_{i}^{1}, v_{j}^{2}), for each i = 1, …, n and j = 1 …, m, such that one of the following conditions is satisfied:

(i) {a_{i}, b_{j}} ∈ M;

(ii) {a_{i}, a′_{i}} ∈ M and s′_{j} = μ(s_{i}, S′) (s′_{j} from S′ is closest to s_{i});

(iii) {b_{j}, b′_{j}} ∈ M and s_{i} = μ(s′_{j}, S).

Since M is a perfect matching in G′′, it is easy to see that L′ is indeed a linking between S and S′, and that c(L′) = w(M). Hence, it follows that c(L) ≤ w(M). The result follows. □

We remark that a modified version of the graph G′′ provides another possibility for computing the surjection measure. In fact, if all edges {b_{j}, b′_{j}} are removed from G′′, then the perfect matchings in the resulting graph G′′′ correspond to surjections between S and S′, and the cost of a minimum weight perfect matching in G′′′ equals the cost of an optimal surjection between S and S′. However, G′′′ is more complex than the graph G in Section 4.2, on which a perfect matching algorithm is expected to perform better in general.

Theorem 4.8 The distance function d_{l} is computable in polynomial time.

Proof. Consider sets S and S′. The graph G′′ for S and S′′ can be constructed in polynomial time. A minimum cost perfect matching in G′′ can be computed in polynomial time, cf. [10]; hence the result follows. □

The graph G′′ is bipartite by the partition of the vertex sets constituted by A∪B′ and A′ ∪ B. Therefore, a minimum cost perfect matching in G′′ can be computed in time

O (n·m·(n + m)·log(n + m)·(1/ max(1, log \frac{2n·m + n + m}{n + m})))

(cf. Proposition 4.1; |V_{1}| = n + m, |E| = 2nm + n + m).

Let us remark at the end of this section that in case Δ is a metric on B, the efficiency of the proposed algorithms might be improved by using metric matching techniques (cf. [23]). The network flow and matching problems constructed in this section involve additional vertices to which the underlying metric space B does not extend; thus, the constructions would have to be suitably adapted. Notice that the main goal of this section is showing that certain distance functions are computable in polynomial time and not intractable. We confined ourselves for this purpose to using standard methods.

[figure: a; b; c; d]

Figure 9: Violations of the triangle inequality (S_{1} = {a, c}, S_{2} = {d}, S_{3} = {b}).

5 From distance functions to metrics

In certain contexts, it is natural or desired that a measure of distance between point sets is a metric, i.e., it satisfies the postulates of a distance function and in addition the triangle inequality.

For example, suppose that the amount of work that has to be done to change a set into another should be reflected in the interdistance value attached to these point sets; for a concrete instance, assume that the points are strings. In this case, the triangle inequality is a reasonable postulate for a suitable distance measure, since changing a set S_{1} into a set S_{2} is not more expensive than the sum of changing S_{1} to S_{3} and changing S_{3} into S_{2}.

Each of the distance functions between two sets defined in the previous section, d_{md}, d_{s}, d_{fs}, and d_{l}, fails to satisfy the triangle inequality, as shown by the following example.

Example 5.1 Consider S_{1} = {a, c}, S_{2} = {d}, and S_{3} = {b} in Figure 9. Then d_{md}(S_{1}, S_{2}) = 6/2 = 3, d_{md}(S_{1}, S_{3}) = 3/2 and d_{md}(S_{3}, S_{2}) = 2/2 = 1; hence, d_{md}(S_{1}, S_{3})+d_{md}(S_{3}, S_{2}) = 5/2 < d_{md}(S_{1}, S_{2}), i.e., the triangle inequality fails. The same applies to the other distance functions d_{α}, for every α ∈ {s, fs, l}, for which we have d_{α}(S_{1}, S_{2}) = 4, d_{α}(S_{1}, S_{3}) = 2, and d_{α}(S_{3}, S_{2}) = 1. □^{6}

In this section we describe a simple construction that produces from a distance function a metric which has certain appealing properties. More precisely, given an arbitrary distance function d : P_{∅}(B)^{2} → ℜ^{+}, where B is finite, the construction produces a metric d^{ω} on P_{∅}(B). For the distance functions d_{md}, d_{s}, d_{fs}, and d_{l} the respective metrics coincide on singletons with the metric Δ on B.

Call any finite sequence P = (P_{1}, P_{2}, …, P_{m}), where m ≥ 2 and P_{i} ⊆ B, for all i with 1 ≤ i ≤ m, a path between P_{1} and P_{m}; the length of the path is m. We use P (S, S′) to denote the set of all paths between S and S′. The concatenation of paths P = (P_{1}, …, P_{m}) and P′ = (P_{m}, …, P_{n}) is the path P P′ = (P_{1}, …, P_{n}). The cost c_{d}(P) of P under a distance function d is defined by c_{d}(P) = ∑_{i=1}^{m−1} d(P_{i}, P_{i+1}). A path P ∈ P (S, S′) is called optimal under d (or d-optimal) iff c_{d}(P) = min{c_{d}(P′) : P′ ∈ P (S, S′)}.

6More complex examples show the failure of the triangle inequality for the versions of the measures from normalization by the size of the larger set.

Define the function d^{ω} : P_{∅}(B)^{2} → ℜ^{+} by

d^{ω}(S, S′) = min{c_{d}(P) : P ∈ P (S, S′)}.

We observe that d^{ω} has the following appealing properties. Let the functions f : P_{∅}(B) × P_{∅}(B) → ℜ^{+} (ℜ^{+} are the nonnegative reals) be partially ordered by f ≤ g iff f(S_{1}, S_{2}) ≤ g(S_{1}, S_{2}) for all S_{1}, S_{2}.

Theorem 5.1 Let d be a distance function on P_{∅}(B), where B is finite. Then,

(a) d^{ω} defines a metric on P_{∅}(B).

(b) d^{ω} is the unique maximum of the distance functions f : P_{∅}(B)^{2} → ℜ^{+} which satisfy

f(S, S′) = min(d(S, S′), min_{S′′}(f(S, S′′) + f(S′′, S′)) )  (1)

(c) d^{ω} is the unique maximum metric function f : P_{∅}(B)^{2} → ℜ^{+} with f ≤ d.

Proof. It is easy to see that d^{ω} is symmetric and that d^{ω}(S, S′) = 0 iff S = S′, hence d^{ω} is a distance function. Moreover, from the definition of d^{ω} it follows that the triangle inequality holds; hence (a) follows.

It is easy to see that d^{ω} satisfies Equation 1. We show that f(S, S′) ≤ d^{ω}(S, S′) by induction on the length of the shortest d-optimal path (P_{1}, …, P_{m}) ∈ P (S, S′). If m = 2, then d^{ω}(S, S′) = d(S, S′) and f(S, S′) ≤ d^{ω}(S, S′) holds. If m > 2, then d^{ω}(S, S′) = d(S, P_{2})+d^{ω}(P_{2}, S′), hence by the induction hypothesis and Equation 1, d^{ω}(S, S′) ≥ f(S, P_{2}) + f(P_{2}, S′) ≥ f(S, S′), and the statement holds. Consequently, f ≤ d^{ω} and d^{ω} is a unique maximum of the distance functions satisfying (1); thus (b) holds.

It remains to consider (c). Assume f is a metric such that f ≤ d and that d^{ω}(S, S′) < f(S, S′) for some S and S′. Now d^{ω}(S, S′) = ∑_{i=1}^{m−1} d(P_{i}, P_{i+1}) for some d-optimal path (P_{1}, …, P_{m}) ∈ P (S, S′). By the triangle inequality f(S, S′) ≤ ∑_{i=1}^{m−1} f(P_{i}, P_{i+1}) and by assumption f(P_{i}, P_{i+1}) ≤ d(P_{i}, P_{i+1}) for 1 ≤ i < m, thus we get f(S, S′) ≤ d^{ω}(S, S′), a contradiction. □

In the light of Theorem 5.1(c), we refer to d^{ω} as the metric infimum of d.

Recall that our motivation was to extend a distance function Δ on B to P_{∅}(B) so that Δ({x}, {y}) = Δ(x, y). Thus, if we want this distance function to be a metric, Δ must be a metric on B. If this is the case, then each of the metric infima of the distance functions d_{md}, d_{s}, d_{fs}, and d_{l} in Section 2 satisfies the property d^{ω}({x}, {y}) = Δ(x, y).

Proposition 5.2 Let d and d_{a} be distance functions on P_{∅}(B) such that d_{a} ≤ d and for all x, y ∈ B, d({x}, {y}) = Δ(x, y) and d_{a}^{ω}({x}, {y}) = Δ(x, y). Then, d^{ω}({x}, {y}) = Δ(x, y) for all x, y ∈ B.^{7}

Proof. From d_{a} ≤ d it follows easily that d_{a}^{ω} ≤ d^{ω}. Since d_{a}^{ω}({x}, {y}) = Δ(x, y), we have Δ(x, y) ≤ d^{ω}({x}, {y}). On the other hand, since d({x}, {y}) = Δ(x, y), it follows (cf. Theorem 5.1(b)) that d^{ω}({x}, {y}) ≤ Δ(x, y). The result follows. □

Corollary 5.3 Assume that the distance function Δ satisfies the triangle inequality, i.e., Δ is a metric on B. Then, for each α ∈ {md, s, fs, l}, we have d_{α}^{ω}({x}, {y}) = Δ(x, y) for all x, y ∈ B.

Proof. Choose the Hausdorff distance d_{h} for d_{a} (note that d_{h}^{ω} = d_{h}) and d_{α} for d.□

Let us have a closer look at the properties of different d^{ω} measures. Interestingly, the metric infima of the distance functions d_{s}, d_{fs}, d_{l} collapse to a single function.

Theorem 5.4 d_{s}^{ω} = d_{fs}^{ω} = d_{l}^{ω}.

Proof. Clearly, d_{l}^{ω} ≤ d_{s}^{ω} ≤ d_{fs}^{ω}. (Every surjection between S and S′ is a linking between S and S′).

Notice that in order to show d_{α}^{ω} ≤ d_{β}^{ω}, it suffices to show that for all S = {s_{1}, …, s_{n}} and S′ = {s′_{1}, …, s′_{m}} where 1 ≤ m ≤ n and d_{β}(S, S′) = d_{β}^{ω}(S, S′), there exists a path P = (P_{1}, …, P_{m}) ∈ P (S, S′) such that c_{d_{α}}(P) ≤ d_{β}(S, S′).

The claim d_{s}^{ω} ≤ d_{l}^{ω} is shown as follows. Let L be an optimal linking between S and S′ such that c(L) = d_{l}^{ω}(S, S′). The idea is that a linking can be represented by two surjections. We define from L the surjections η_{S} : S → R and η_{S′} : S′ → R to an intermediate set R. This set contains elements of S and S′ corresponding to the centers of stars of G(L) and the endpoints in V_{1} of lines of G(L), i.e.,

R = {s_{i} : v_{i}^{1} ∈ cst(L) ∩ V_{1} or deg(v_{i}^{1}, G(L)) = 1} ∪ {s′_{j} : v_{j}^{2} ∈ cst(L) ∩ V_{2}}.

7This proposition can be generalized by replacing ‘d({x}, {y}) = Δ(x, y) and d_{a}^{ω}({x}, {y}) = Δ(x, y)’ with the weaker condition ‘d({x}, {y}) ≤ Δ(x, y) and d_{a}^{ω}({x}, {y}) ≥ Δ(x, y)’.

The surjection η_{S} will map the elements of S that belong to a line of G(L) or to a S′-star of G(L) to the unique element they are linked by L. Similarly, η_{S′} maps members of S′ that belong to lines or S-stars of G(L) to the unique element L links them with. Formally, for all i and j with 1 ≤ i ≤ n, 1 ≤ j ≤ m,

η_{S}(s_{i}) = \{ \begin{matrix}s′_{k}, & if v_{i}^{1} is in a star of G(L) with center v_{k}^{2}, \\ & or if \{v_{i}^{1}, v_{k}^{2}\} is a line of G(L); \\ s_{i}, & otherwise. \end{matrix}

η_{S′}(s′_{j}) = \{ \begin{matrix}s_{k}, & if v_{j}^{2} is in a star of G(L) with center v_{k}^{1}, \\ & or if \{v_{k}^{1}, v_{j}^{2}\} is a line of G(L); \\ s′_{j}, & otherwise. \end{matrix}

Then η_{S} and η_{S′} are surjections which satisfy c(η_{S}) + c(η_{S′}) = c(L). Consequently, c_{d_{s}}(S, R, S′) ≤ c(L) = d_{l}^{ω}(S, S′). It follows that d_{s}^{ω} ≤ d_{l}^{ω}.

The fact that d_{fs}^{ω} ≤ d_{s}^{ω} can be shown similarly. The intuition is that a surjection can be decomposed into a sequence of surjections between sets whose cardinality differs only by one. Such surjections will be necessarily fair. Assume that η : S → S′ is an optimal fair surjection between S and S′ and that d_{s}(S, S′) = d_{s}^{ω}(S, S′). We show by induction on the number k of stars and lines of G(L), that there exists a path P = (P_{1}, …, P_{r}) ∈ P (S, S′) such that 0 ≤ |P_{i}| − |P_{i+1}| ≤ 1, 1 ≤ i < r, and c_{d_{fs}}(P) ≤ d_{s}(S, S′).

If k = 1, then m = 1, i.e. G(η) consists merely of one line or one star. The sequence Q = (Q_{1}, …, Q_{n+1}), where Q_{1} = S and Q_{i} = Q_{i−1} − {s_{i−1}} ∪ {s′_{1}}, for all i with 2 ≤ i ≤ n + 1, satisfies the properties of P. Indeed, Q ∈ P (S, S′), and clearly 0 ≤ |Q_{i}| − |Q_{i+1}| ≤ 1, for all i, 1 ≤ i ≤ n. Define η_{i} : Q_{i} → Q_{i+1}, 1 ≤ i ≤ n, by

η_{i}(x) = \{ \begin{matrix}s′_{1}, & if x = s_{i}; \\ x, & if x ∈ Q_{i} − \{s_{i}\}. \end{matrix}

Each η_{i} is a fair surjection, and ∑_{i=1}^{n} c(η_{i}) = c(η); hence, c_{d_{fs}}(Q) ≤ d_{s}(S, S′). Thus the statement holds for k = 1.

Now consider the case k > 1. Let S_{1} = S − η^{−1}(s′_{1}) and S′_{1} = S′ − {s′_{1}}. We construct a sequence of fair surjections that will ultimately link S and S′ by first decomposing an optimal surjection of η^{−1}(S′_{1}) to {s′_{1}} into a sequence of fair surjections (by the induction hypothesis). This sequence is extended to a sequence of fair surjections between S and S_{1} ∪ {s′_{1}}. The induction assumption is again applied, and we get a sequence of fair surjections from S_{1} ∪ {s′_{1}} to S′. Formally, denote by η[X] the restriction of η to X. We note first that

d_{s}(η^{−1}(s′_{1}), {s′_{1}}) = d_{s}^{ω}(η^{−1}(s′_{1}), {s′_{1}}) = c(η[η^{−1}(s′_{1})])

[figure: 11; 10; 01; 00; S_{1}; S_{4}; S_{3}; S_{2}; S_{1}; S_{4}; S_{3}]

Figure 10: Example showing that d_{md}^{ω} ≠ d_{l}^{ω}.

and

d_{s}(S_{1}, S′_{1}) = d_{s}^{ω}(S_{1}, S′_{1}) = c(η[S_{1}])

must hold by the assumption d_{s}(S, S′) = d_{s}^{ω}(S, S′). Let P′ = (P′_{1}, …, P′_{s}) ∈ P (η^{−1}(s′_{1}), {s′_{1}}) and P′′ = (P′′_{1}, …, P′′_{t}) ∈ P (S_{1}, S′_{1}) of the properties assured by the induction hypothesis on η^{−1}(s′_{1}), {s′_{1}} and S_{1}, S′_{1}, respectively. Let

Q′ = (S_{1} ∪ P′_{1}, …, S_{1} ∪ P′_{s}),
Q′′ = (P′′_{1} ∪ {s′_{1}}, …, P′′_{t} ∪ {s′_{1}}).

Note that S_{1} ∪ P′_{1} = S and S_{1} ∪ P′_{s} = P′′_{1} ∪ {s′_{1}}. Hence, Q = Q′Q′′ is a path in P (S, S′) and

c_{d_{fs}}(Q) = c_{d_{fs}}(Q′) + c_{d_{fs}}(Q′′)
≤ d_{s}(η^{−1}(s′_{1}), {s′_{1}}) + d_{s}(S_{1}, S′_{1})
= c(η[η^{−1}(s′_{1})]) + c(η[S_{1}]) = d_{s}(S, S′).

Clearly Q also satisfies the remaining property of P in the statement for S and S′. Hence, the statement holds on S, S′. It follows that d_{fs}^{ω} ≤ d_{s}^{ω}.

The proposition follows from d_{l}^{ω} ≤ d_{s}^{ω} ≤ d_{fs}^{ω} and d_{fs}^{ω} ≤ d_{s}^{ω} ≤ d_{l}^{ω}. □

One can find instances for which d_{l}^{ω} ≠ d_{md}^{ω}, however. For an example, consider the sets S_{1} = {00}, S_{2} = {01, 11}, S_{3} = {11}, S_{4} = {01} in Figure 10. Here it is assumed that B consists of the four binary strings 00, 01, 10, and 11 whose distance Δ is their Hamming distance. Then, d_{l}^{ω}(S_{1}, S_{2}) = d_{l}^{ω}(S_{1}, S_{3}) = 2. However, for the minimum distance measure we have d_{md}^{ω}(S_{1}, S_{3}) = 2, but d_{md}^{ω}(S_{1}, S_{2}) ≤ 3/2, since one can go from S_{2} to S_{1} by first going to S_{4} and then to S_{1}; we have d_{md}(S_{2}, S_{4}) = 1/2. This example shows that the behavior of the d_{l}^{ω} measure is more natural than that of the d_{md}^{ω} measure (at least in some situations). For this reason, we consider in the next section only the computation of the d_{l}^{ω} measure.

6 Computing the d_{l}^{ω} measure

Now let us consider the computational properties of the d_{l}^{ω} measure. A simple result is that under some general assumptions on the computational properties of Δ and B, the d_{l}^{ω} measure is computable.

Proposition 6.1 Assume that Δ is computable and that B is computable, i.e., all points of B can be effectively generated in finite time. Then d_{l}^{ω} is computable.

Proof. Compute d_{l}^{ω} by cycling through all paths of length at most 2^{|B|} and take the minimum of their costs. □

Computing d_{l}^{ω} appears to be more complex than computing d_{l}. We will show in this section that computing d_{l}^{ω} is NP-hard for a simple – and quite natural – instance. However, the associated recognition problem is in NP under very general conditions, which entails that computing d_{l}^{ω} is not much harder than the NP-complete problems.

6.1 Steiner forests and paths between sets

We need additional concepts. Let S be a nonempty subset of B. A weighted tree T = (V, E, w) such that V ⊆ B and w coincides with Δ is a Steiner tree for S if S ⊆ V; T is called optimal iff the weight w(T) is minimum over the weights of all Steiner trees for S.

We generalize Steiner trees as follows. A Steiner forest for S_{1}, S_{2} ⊆ B is a family F = {T_{i} : 1 ≤ i ≤ k} of pairwise disjoint weighted trees T_{i} = (V_{i}, E_{i}, w_{i}) such that V_{i} ⊆ B and w_{i} coincides with Δ for all i with 1 ≤ i ≤ k, and S_{1} ∪ S_{2} ⊆ ⋃_{i} V_{i} and S_{i} ∩ V_{j} ≠ ∅, for i = 1, 2 and all j with 1 ≤ j ≤ k. The weight w(F) of F is defined as the weight of the graph that is the union of all trees in F; F is optimal iff its weight is minimum over all Steiner forests for S_{1} and S_{2}.

Note that if F = {T }, then F is a Steiner forest for S and S′ iff T is a Steiner tree for S ∪ S′. In particular, if S′ = {x} and x ∈ S, then F is optimal iff T is optimal. The following holds for an optimal Steiner forest in the general case.

Proposition 6.2 Let F be an optimal Steiner forest for S, S′. Then each T = (V, E) ∈ F is an optimal Steiner tree for V ∩ (S ∪ S′).

Concerning the relation between Steiner forests and paths between sets, our first observation is that the cost of a path between sets S and S′ is an upper bound for the weight of an optimal Steiner forest for S and S′.

Lemma 6.3 Let P = (P_{1}, …, P_{m}) ∈ P (S, S′) be a d_{l}-optimal path and let F be an optimal Steiner forest for S, S′. Then w(F) ≤ c_{d_{l}}(P).

Proof. (Sketch) Take an arbitrary sequence L_{1},…, L_{m−1} of linkings L_{i} between P_{i} an P_{i+1}, and consider the undirected graph G whose edges correspond to the links in all L_{i}. Each connected component in G contains one point from S and one from S′. Thus any forest of spanning trees for the connected components in G is a Steiner forest for S, S′. It follows w(F) ≤ c_{d_{l}}(P). □

Conversely, our next considerations show that the weight of an optimal Steiner forest for S, S′ is an upper bound for the cost of any path between S and S′ under d_{l}. Consequently, the cost of a d_{l}-optimal path between S and S′ equals the weight of an optimal Steiner forest for S, S′.

6.2 Computing a path from a Steiner Tree

Given a Steiner tree T = (V, E, w) for S ∪ S′ ⊆ B, S, S′ ≠ ∅, such that all its leaves, i.e. vertices of degree 1 are in S ∪ S′, the algorithm path in Table 1 constructs a path P ∈ P (S, S′) such that c_{d_{l}}(P) ≤ w(T). The intuitive idea is that each step in the path takes one edge of the Steiner tree. We first do steps that remove each leaf of the tree that is in S. Then we select an arbitrary vertex x and an edge starting from that, and produce a next set on the path that in essence takes care of that edge.

Proposition 6.4 path(S, S′, T) computes P = (P_{1}, …, P_{m}) such that P ∈ P (S, S′) and c_{d_{l}}(P) ≤ w(T).

Proof. (Sketch) It is not hard to see that the first while terminates (since the number of edges in T decreases in each iteration), and one can show that upon termination T is a tree such that all its leaves are in S′. After this, we clearly have P_{m} ≠ ∅. The vertex x selected from P_{m} serves as the root node of the remaining tree T, whose edges are removed one by one in the iterations of the second while. An edge {x, y} can be removed only if x ∈ R, which holds after all edges on the path from the root to x have been removed. The second while terminates, again since the number of edges in T decreases in each iteration. Upon termination, P_{m} = S′ holds. Clearly, m = |E| + 1. It is easily checked that m = 1 iff S = S′ = {v} and T = ({v}, ∅, w) for some v, hence w(T) = 0. If m > 1, then for each i with 1 ≤ i < m there exists a linking L_{i} between P_{i} and P_{i+1} such that c(L_{i}) = Δ(x, y), where {x, y} is the edge that has been removed from T when constructing P_{i+1}. Consequently, path outputs on input S, S′ a path P ∈ P (S, S′) such that c_{d_{l}}(P) ≤ w(T). □

Algorithm path(S, S′, T)

input: Steiner tree T = (V, E, w) for S ∪ S′ ⊆ B,
S, S′ ≠ ∅, whose leaves are in S ∪ S′.
output: P = (P_{1}, …, P_{m}) ∈ P (S, S′) with c_{d_{l}} (P) ≤ w(T).

           /* Phase 1:  move along edges of leaf nodes x ∉ S′ */

P_{1} := S; m := 1;

while T has a leaf x ∉ S′ with an edge to y do

begin /* Link x to y */ P_{m+1} := (P_{m}\{x}) ∪ {y}; m := m + 1; remove x from T;

       end; /* All leaves of T are in S′ now */
           /* Phase 2:  move towards S′, and keep the reached nodes in R */

set R := {x} for any x ∈ P_{m}; while E ≠ ∅ do begin

select an x ∈ R with an edge to y; R := R ∪ {y};

if x ∉ S′ and x is a leaf of T then /* Link x to y */ P_{m+1} := (P_{m}\{x}) ∪ {y};

          /* Link x to x (cost 0) and y */ else P_{m+1} := P ∪ {y};

m := m + 1; remove edge {x, y} from T;

end; /* P_{m} = S′ now */

if m = 1 then output(P_{1}, P_{1}) else output(P_{1}, …, P_{m});

Table 1: Algorithm for computing from T a path between S and S′.

Lemma 6.5 Let F = {T_{i} = (V_{i}, E_{i}, w_{i}) : 1 ≤ i ≤ k} be an optimal Steiner forest for S, S′. Then there exists a path P ∈ P (S, S′) such that c_{d_{l}}(P) ≤ w(F).

Proof. (Sketch) This can be shown by induction on k. For k = 1, this follows from Proposition 6.4. In the general case, one can construct such a path by first going from S ∩ V_{1} to S′ ∩ V_{1} while keeping the points in S − V_{1} fixed, after that going from S ∩ V_{2} to S ∩ V′_{2} while keeping the points in S′ ∩ V_{1} and S − (V_{1} ∪ V_{2}) fixed and so on. The resulting path has cost c_{d_{l}}(P) ≤ w(F). □

Theorem 6.6 Let F be an optimal Steiner forest for S, S′ ⊆ B. Then w(F) = d_{l}^{ω}(S, S′).

Proof. Follows immediately from Lemmas 6.3 and 6.5. □

6.3 An algorithm for computing d_{l}^{ω} and its complexity

The structural result in Theorem 6.6, combined with Proposition 6.2 is exploited first by the algorithm dinflink in Table 2. The subroutine steiner(S, B) called by this algorithm returns the weight of an optimal Steiner tree for S in B.

Algorithm dinflink(S, S′)

input: S, S′ ⊆ B, with 1 ≤ |S| ≤ |S′|.
output: d_{l}^{ω}(S, S′).

     d := ∞; /* upper bound on d_{l}^{ω}(S, S′) */

for each partitioning B_{1}, …, B_{k} of S ∪ S′ such that 1 ≤ k ≤ |S|

and B_{i} ∩ S ≠ ∅, B_{i} ∩ S′ ≠ ∅ for 1 ≤ i ≤ k do

     begin  /* ∑_{i} w(T_{i}) of optimal Steiner trees T_{i} for B_{i} is ≥ d_{l}^{ω}(S, S′) */

w := 0;
for i = 1 to k do w := w + steiner(B_{i}, B);
d := min(d, w);

end;

       /* d has the cost of an optimal Steiner forest for S, S′ */

output(d);

Table 2: Algorithm for computing d_{l}^{ω}.

Proposition 6.7 dinflink computes d_{l}^{ω} correctly.

The generation of all B_{1}, …, B_{k}, for each k, causes exponential cost of dinflink. However, as we will show, even if there is only one possible choice, computing d_{l}^{ω} can be an NP-hard problem. dinflink reflects this by calls of steiner for NP-hard instances.

On the other hand, under very general conditions computing d_{l}^{ω} is not “much harder” than the NP-complete problems, as one can show using the Steiner forest characterization. Recall that our motivation for defining d_{l}^{ω} was to extend a distance measure on B to a metric on P_{∅}(B), which is only possible if Δ is a metric on B. In this case, the following holds on optimal Steiner trees.

Lemma 6.8 cf. [7] Let S ⊆ B be a nonempty subset of B. If Δ is a metric, then there exists an optimal Steiner tree (V, E, w) for S such that |V | ≤ 2|S| − 2.

Theorem 6.9 Assume that each element of B can be represented in polynomial size and time with respect to the size of the input to d_{l}^{ω}, and that Δ is a metric.^{8} Then deciding d_{l}^{ω}(S, S′) ≤ b, where b is a rational number, is in NP.

Proof. Let F = {T_{i} = (V_{i}, E_{i}, w_{i}) : 1 ≤ i ≤ k} be an optimal Steiner forest for S, S′. Then, k ≤ min(|S|, |S′|). Since T_{i} is an optimal Steiner tree for S_{i} = V_{i} ∩ (S ∪ S′) and Δ is a metric, by Lemma 6.8 we have |V_{i}| ≤ 2|S_{i}| − 2 for each i with 1 ≤ i ≤ k. Hence, the number of vertices in F, n_{v}, is bounded by

n_{v} = | ⋃_{i=1}^{k} V_{i}| ≤ 2 ∑_{i=1}^{k}(|S_{i}| − 2) = 2|S ∪ S′| − 2k ≤ 2|S ∪ S′| − 2.

Consequently, from Theorem 6.6 it follows that d_{l}^{ω}(S, S′) ≤ b iff there exists a Steiner forest F′ for S and S′ on at most n_{v} vertices. By our assumptions, the instance size of F′ is bounded by a polynomial in the input size. Hence, guessing F′, computing w(F′), and comparing this value to b is possible in polynomial time. □

Corollary 6.10 Computing d_{l}^{ω}(S, S′) in the setting of Theorem 6.9 is NP-easy.

Proof. d_{l}^{ω}(S, S′) can be computed with an oracle for deciding d_{l}^{ω}(S, S′) ≤ b in polynomial time, by doing a binary search over the range of possible values. □

Notice that Theorem 6.9 and Corollary 6.10 generalize from metrics Δ to distance functions under which the instance size of an optimal Steiner forest for S and S′ is bounded by a polynomial in the input size.

It is easy to see that computing d_{l}^{ω} is NP-hard even for simple cases.

Theorem 6.11 Deciding whether d_{l}^{ω}(S, S′) ≤ b is NP-hard for subsets S, S′ of the Euclidean integral plane with Manhattan metric and for integers b.

Proof. This is shown by a reduction of the GEOMETRIC STEINER TREE problem (GST) [8] in the integral plane under the Manhattan (rectilinear) metric Δ_{M}. GST is as follows: Given a finite set P = {p_{1}, …, p_{n}} of points in the integral plane and an integer a, decide whether there exists under Δ_{M} a Steiner tree T for P such that w(T) ≤ a. This problem is known to be NP-hard in the strong sense, i.e. even if all numbers are represented in unary notation [8]. It is easy to see that we may assume that in P only nonnegative coordinate values occur.

Now it suffices to note that there exists a Steiner tree T for P such that w(T) ≤ b if and only if d_{l}^{ω}(P, {p_{1}}) ≤ b. □

8Without this assumption on B, the result may not hold. E.g., if B consists of all Boolean formulas (likewise, first-order formulas, or trees) Φ of depth ≤ n on a given vocabulary, then the size of Φ is not necessarily polynomial in n or the size of other such formulas Φ_{1} and Φ_{2}.

7 Conclusion

We have considered the problem of extending a distance function (or even metric) between points to a distance function or metric between point sets. We have investigated different approaches for this, and have analyzed the computational complexity of the resulting functions.

In our analysis, we assumed that the underlying set of points B is finite. However, in many cases B might be infinite. Under certain conditions, the results from above can be extended to this case as well. The functions d_{md}, d_{f} , d_{fs}, and d_{l} work well on finite subsets of B, but might not converge to a real number if one of the arguments is infinite; it is not straightforward how to overcome this problem. The function d^{ω} from Section 5, appropriately adapted by taking for (S, S′) the infimum of {c_{d}(P) : P (S, S′)} rather than the minimum (which need not exist), yields a metric also for infinite B provided that no sequence of paths P^{1}, P^{2}, … between two different sets S and S′ exists whose costs c(P^{1}), c(P^{2}), … converge to 0. In particular, Theorem 5.1 remains true in this case, and the metric infima of d_{s}, d_{fs} and d_{l} on the finite subsets of B collapse. An important fact is, however, that d^{ω}(S, S′) may no longer take the cost of some optimal path between S and S′, but rather the limit of the cost values of an infinite sequence of paths. This makes exact computation difficult if not impossible. However, given e.g. that every set S has for every constant c > 0 only finitely many sets S′ with d(S, S′) < c and that d(S, S′) > α for some constant α > 0 whenever S and S′ are different, then d^{ω}(S, S′) takes the cost value of an optimal path.^{9} (This applies e.g. to the integral plane under a number of distance functions d on finite point sets from above.) Under this assertion, the computation of d^{ω}(S, S′) reduces to a finite subset B′ of B. For example, the computation of d_{l}^{ω}(S, S′) in the integral plane trivially reduces to B′ which contains only points x that are within distance d_{l}(S, S′) to some point in S ∪ S′. The algorithms in Section 6 can thus be readily applied.

Besides proper extensions of the above distance functions to infinite point sets, several open problems remain.

We know that d_{h}, d_{l}^{ω}, and d_{md}^{ω} are not equivalent, but it is not quite clear what the properties of these metrics really are. Also, it would be interesting to know whether d_{l}^{ω} or d_{md}^{ω} can be approximated in polynomial time with reasonable performance bounds.

Acknowledgments The authors would like to thank the referees for their comments and valuable suggestions that helped to improve the presentation of this paper.

9Examples show that neither of the two conditions can be dropped.

References

[1] H. Alt, K. Mehlhorn, H. Wagener, and E. Welzl. Congruence, similarity and symmetries of geometric objects. Discrete Comput. Geom., 3:237–256, 1988.

[2] M. R. Anderberg. Cluster Analysis for Applications. Academic Press, New York, 1973.

[3] C. Berge. Graphs and Hypergraphs. Elsevier Science Publishers B.V. (North-Holland), 1989.

[4] J. Dugundji. Topology. Allyn and Bacon, Inc., Boston, 1966.

[5] U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors. Advances in Knowledge Discovery and Data Mining. AAAI Press, 1995. To appear.

[6] P. Gärdenfors. Knowledge in Flux. Bradford Books, MIT Press, 1988.

[7] M. Garey, R. Graham, and D. Johnson. Some NP-complete Geometric Problems. In Proceedings STOC-78, pages 10–21, 1978.

[8] M. Garey and D. S. Johnson. Computers and Intractability – A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.

[9] D. Huttenlocher and K. Kedem. Efficiently Computing the Hausdorff Distance for Point Sets under Translation. In Proceedings of the Sixth ACM Symposium on Computational Geometry, pages 340–349, 1990.

[10] K. Mehlhorn. Graph Algorithms and NP-Completeness, volume 2 of Data Structures and Algorithms. Springer, 1984.

[11] S. Muggleton. Inductive Acquisition of Expert Knowledge. Addison Wesley, Reading, Massachusetts, 1990.

[12] B. K. Natarajan. Machine Learning: A Theoretical Approach. Morgan Kaufmann, San Mateo, CA, May 1991.

[13] I. Niiniluoto. Truthlikeness. D. Reidel Pub. Comp., Dordrecht, Holland, 1987.

[14] G. Oddie. Verisimilitude and Distance in Logical Space. In I. Niiniluoto and R. Tuomela, editors, The Logic and Epistemology of Scientific Change, pages 243–264. North-Holland, 1979. (Acta Philosophica Fennica 30).

[15] G. Oddie. Likeness to Truth. D. Reidel Pub. Comp., Dordrecht, Holland, 1986.

[16] G. Piatetsky-Shapiro and W. J. Frawley, editors. Knowledge Discovery in Databases. AAAI Press / The MIT Press, Menlo Park, CA, 1991.

[17] K. Popper. Some Comments on Truth and the Growth of Knowledge. In E. Nagel, P. Suppes, and A. Tarski, editors, Logic, Methodology, and Philosophy of Science, pages 285–292, 1962.

[18] K. Popper. A Note on Verisimilitude. The British Journal for the Philosophy of Science, 27:147–159, 1976.

[19] P. Z. Revesz. On the Semantics of Theory Change: Arbitration between Old and New Information. In Proceedings of the Twelth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pages 71–79, June 1993.

[20] H. Romerburg. Cluster Analysis for Researchers. Lifetime Learning, Belmont, CA, 1984.

[21] H. Toivonen, M. Klemettinen, P. Ronkainen, K. Hätönen, and H. Mannila. Pruning and grouping of discovered association rules. In MLnet Workshop on Statistics, Machine Learning, and Discovery in Databases, pages 47–52, Heraklion, Crete, Greece, April 1995.

[22] R. Tuomela. Verisimilitude and Theory-Distance. Synthese, 38:213–246, 1978.

[23] P. Vaiyda. Geometry Helps in Matching. In Proceedings of the Twentiest ACM Symposium on the Theory of Computing (STOC-88), pages 422–425, 1988.

[24] J. van Leeuwen. Graph Algorithms. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 10. Elsevier Science Publishers B.V. (North-Holland), 1990.

[25] M. Winslett. Updating Logical Databases. Cambridge University Press, 1990.

[26] S. Wrobel. On the Proper Definition of Minimality in Specialization and Theory Revision. In P. B. Brazdil, editor, Machine Learning: ECML-93. European Conference on Machine Learning, Lecture Notes in AI 667, pages 65–82. Springer-Verlag, 1993.