Algorithms for computing geometric measures of melodic similarity

Two algorithms to find the minimum area between two given orthogonal melodies, M_a and M_b, of size n and m, respectively (n > m) are presented. Both algorithms can be used for cyclic melodies as well as in the context of retrieving short patterns from a database. The algorithms are described for the case where the melodies are cyclic. The first algorithm assumes that the Θ direction is fixed, and it runs in O(n) time. The second algorithm finds the minimum area when both the z and Θ relative positions can be varied. It is proved that it runs in O(nmlogn) time. In each case, it is assumed that the edges defining M_a and M_b are given in the order in which they appear in melodies. Finally, natural extensions are discussed both for the polygonal description of melodies and for different types of queries.