# Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

The title may be a bit confusing but the problem is this;

Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is;

-> Pick one point from each group (we will have 4 points at the end)

• whose pairwise distance is larger than a threshold and
• sum of pairwise distances is maximized.

For realization of parameters; group size is number of people in a scene, and points in a group is possible locations of each person. Point size can be increased to tens or hundreds for better estimation depending on computing resources but people count possible will not be larger than 20 or 30.

I hope, I could explained the question clear enough. If not, I will try to clarify better.

Thanks

• There are only $5^4 = 625$ possible choices. Just try all of them. – Yuval Filmus Nov 14 '18 at 22:18
• @Yuval Filmus A generalized answer will be better. Group and point size can vary, so it may become inefficient to check all possible choices. – UnfoX Nov 14 '18 at 22:20
• The answer could depend on the magnitude of your parameters. Do you expect both the number of groups and their size to grow to infinity? If so, do you expect them to be of comparable magnitude? – Yuval Filmus Nov 14 '18 at 22:21
• No, they will not grow to infinity. For realization of parameters; group size is number of people in a scene, and points in a group is possible locations of each person. Point size can be increased to tens or hundreds for better estimation depending on computing resources but people count possible will not be larger than 20 or 30. – UnfoX Nov 14 '18 at 22:25
• You should update your question with all this information. – Yuval Filmus Nov 14 '18 at 22:26