JS - Thin number of points based on density

Question

Say I have an array as follows (each small array is [x, y]):

var myPoints = [[25, 28], [26, 26], [70, 40], [50, 50], [300, 300], [285, 350], [1000, 1000]];

Let's say I need to thin the array down to 4 points. (this is a small example, my acutal array has thousands of points) How could I go about thinning the array based on density so more points are removed from areas with points closer together and less points are removed from areas with lower density?

In this case (reducing the above array from 8 to 4 items) I would expect the returned array to look something like the following:

var thinnedPoints = [[25, 28], [70, 40], [300, 300], [1000, 1000]];

My idea on how to approach this would be to generate a dictionary that maps the point to it's minimum distance to another point (e.g. a point close to another point would have a small minimum distance) then sort the dictionary based on ascending minimum distance, then remove every n'tn item of the dictionary.

The problem with this approach is I don't know how to efficiently generate the distance to closest other point value for each point.

Is there an efficient way to generate those values or maybe is there another way to approach this density based thinning problem?

Thanks!

Answer 1

It seems you want to solve either a P-center problem or a P-median problem.

From Approximability Results for the p-Center Problem by Stefan Buettcher,

The p-Center problem, also known as the Min-Max Multicenter problem or the Facility Location problem, is a famous problem from operations research. Informally, it is the problem of placing fire stations in a city so that the maximum time to reach any point in the city is minimized.

From Methods for Solving the p-Median Problem: An Annotated Bibliography by J. Reese,

The p-median problem is simply stated as: Given a graph or a network G = (V, E), find Vp ⊆ V such that |Vp| = p, where p may either be variable or fixed [...], and that the sum of the shortest distances from the vertices in {V\Vp} to their nearest vertex in Vp is minimized.

Both problems are NP-complete in general, so there is no (known) way to solve them in polynomial time. But there are various heuristics you could try.