What data structures exist for fast calculation of distances between multi-dimensional points
I'm not sure what you mean by 'overlapping points', and even less clear how you construct a 2D scatter plot from 4D data unless by doing some kind of projection. Having said that, what I think you're looking for is a dynamic near-neighbor data structure. Specifically, you want a data structure that processes queries of the form "Who's my nearest neighbor in the current set" and "insert a point into the current set"

While there's a ton of work on different kinds of near-neighbor structures, your particular situation (dynamic 4D points) suggests at least starting with a grid-based structure. Make (4D) buckets based on segmenting the coordinates, and hash the points in, and then for a query you can do a spiral search (or something similar) around the cell your query lies in. 

The next idea would be to build a generalized quad tree data structure (a compressed quad tree) or even something involving space-filling curves, if this first approach doesn't yield the performance you need. There are even more powerful methods, but I wouldn't recommend looking into them till you've exhausted the simple approaches. 

Bottom line: "dynamic" and "nearest-neighbor" and "low dimensional" are your google friends.