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
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.