I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized.
For example, subject to the constraint that paired people are within d=10 miles of each other, I might find 742 pairs from a list of n=3000 people's locations.
alright to assume the world is a 2D Euclidean plane
alright to assume n < 100000
the distance constraint can be relaxed, for example to a cost function with a high value after 10
as in real life, people cluster in cities, so there might be many people "0 miles apart" in New York City while people in Wyoming are few and far apart.
any leads on the same problem above but for triplets would be great. That is, the same problem, but instead of two you take three people and group them together, preferably with the constraint still being that the three are contained in a d-diameter disc, though other similar constraints are fine.
A simple approach
calculate all-pairs distances.
in the process create an array of pairs sorted from closest to farthest
in the process, for each person, store a list of people within d miles
greedily pair together the closest unpaired people
repeat the following until no progress has been made for a certain number of loops
find an unpaired person p_1 with closest person p_2 <= d miles of them. person p_2 is currently paired to person p_3.
unpair p_2 and p_3 and pair p_1 and p_2. If any exist, pair p_3 to a closest person p_4 that is unpaired and within d miles.
I'm sure there are many interesting approaches to this problem, and would any love input on what research/search terms I could look into to learn more about it, any ideas for algorithms to solve this, and possibly bounds on how well the above algorithm would work on the problem.