Sweepline the music!

Esko Ukkonen, Kjell Lemström, and Veli Mäkinen

The problem of matching sets of points or sets of horizontal line segments in plane under translations is considered. For finding the exact occurrences of a point set of size m within another point set of size n we give an algorithm with running time O(mn), and for finding partial occurrences an algorithm with running time O(mn log m). To find the largest overlap between two line segment patterns we develop an algorithm with running time O(mn log (mn)). All algorithms are based on a simple sweepline traversal of one of the patterns in the lexicographic order. The motivation for the problems studied comes from music retrieval and analysis.