Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

4 Hausdorff Distance and Melodic Weight

As mentioned in the Introduction, one of the principal objectives of Mazzola and Zahorka (1996) (see also Buteau, 1997; Buteau and Mazzola, 2000; Buteau, 2001) was the definition of a melodic weight which, in turn, could be applied to shape computer performances of a piece according to the analytical insights encoded therein. Briefly, Mazzola and Zahorka start from a chosen paradigmatic group and a mapping to a Gestalt space which is supposed to be equipped with a (pseudo-)metric. Then they define a topology on sets of subsets of the melody under consideration, and associate with each subset of the melody an integer by counting certain super- and subsets of neighborhoods of elements in the corresponding orbit. Finally, the melodic weight of every tone of the melody is, basically, obtained by adding these numbers for subsets containing it. The resulting numerical function, called the melodic weight associated with the prescribed data, measures the “importance” of the tone with respect to the chosen melodic (or symmetry) paradigm. Here, we will take up this line of thought and modify it in accordance with the specific framework introduced above. In the terminology of Mazzola and Zahorka (1996), we are dealing with the rigid Gestalt determined by the Euclidean plane $2 (R ,deucl)$ . However, the set distance to be used in the sequel will be the Hausdorff distance. As a measure of “resemblance”, this distance plays a prominent role in the field of matching and analysis of patterns in finite point sets (see, e.g. Alt and Guibas, 1999).

Definition 8 Let $A$ and $B$ be non-empty, bounded subsets of the Euclidean plane $2 (R ,deucl)$ . Then the one-sided distance from $A$ to $B$ is defined by

d(A)(B) = supa (- Ainfb (- B deucl(a,b).

The Hausdorff distance of the sets $A$ and $B$ is the larger one of both one-sided set distances:

dH(A, B) = max{d(A)(B),d(B)(A)}.

Proposition 4 The Hausdorff distance $dH$ is a metric on the set of all non-empty, compact subsets of $2 R$ .

The proof of this proposition in the general case of compact subsets of $Rn$ can be found in Hausdorff (1914 = 2002). Since we are dealing exclusively with finite sets, the above formula simplifies to

dH(A,B) = max{max min deucl(a,b),maxmin deucl(a,b)} a (- A b (- B b (- B a (- A = max{maa (- xA d(a,B),mba (- xB d(b,A)}

for non-empty, finite sets $A,B < R2$ , where, e.g., $d(a,B)$ denotes the usual distance of the point $a$ from the set $B$ . This immediately leads to the following fact.

Lemma 1 Let $A$ and $B$ be non-empty, finite sets in $2 R$ and $e$ a positive real number. Then $d(A)(B) < e$ holds, if and only if for each element $a$ of $A$ there is an element $b$ in $B$ , such that $deucl(a,b) < e$ .