Two-dimensional point set pattern matching with horizontal scaling

This paper focuses on two-dimensional point set pattern matching with horizontal scaling. Given a dataset S of n points and a pattern P of m points, the task is to find occurrences of P in S . The pattern may be horizontally scaled using a constant value. This problem is relevant in symbolic music information retrieval when each point is interpreted as a musical note and the pattern is a melody that is searched for. The best known general algorithm for the problem works in O ( n 2 m ) time. In this paper we show that the 3SUM problem can be reduced to this problem, and present a new algorithm that works in O ( n 2 ) time on typical inputs.