I have a motion signal that you can think of as a sequence of pairs (x,y); what would be the best approach to decimate this sequence at real time? I haven't found anything similar on the web and I'm still learning about dsp.
Use predictive coding. If your predictor manages to guess current position based on previous recorded positions with reasonable accuracy — you can omit the recording of current position. Same predictor will also help you to reconstruct the original path.
What predictor you should use is based on the tracked object's nature. You may use a Kalman filter for example. Or you may use something really simple such as 'assume object always stays at the same place. If we are moving — record it'. Or 'assume object always travels along the straight line', etc.
If your predictor will do a good job, you can additionally use Huffman coding — small corrections of prediction errors will have shorter bit sequences, significant corrections — longer bit sequences. It will save you a huge amount of space with near-to-perfect reconstruction.
If the (x,y) are in depended you could decimate each separately. may be the best way for you will be to run a rough low pass filter (-.5, 1, -.5) or more aggressive one and than select every other value. If you do not know enough about characteristics of the 2D signal, you might benefit from attempting several tests with various filters before decimation. Just remember that a basic assumption is that your signal is in the lower end of the spectrum.