1
$\begingroup$

I faced a problem that looks very hard, the problem is this:

We have 5 people putting dots on a whiteboard, each person uses colored dots with a different color (there are 5 colors, 1 for each person). My job is to find a cluster of points which contains 3 or more distinct colors. Also, we have some fixed radius $R$, and the distance for each point in a given cluster shouldn't be more than R. Also, there might be points that don't belong to any cluster.

What kind of approach can you suggest? At first, I tried the Multidimensional linear assignment problem, but it seems that this problem is NP-hard, so I want to solve it in a reasonable amount of time (I write code). What kind of solutions can you suggest? Maybe using the fact that this isn't a general problem, I mean we use 2D space where people take action, also there are only 5 people.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you only need to find one cluster ? That is, one ball of radius R which contains three colors ? $\endgroup$
    – Hugo Manet
    Feb 23, 2021 at 12:50
  • $\begingroup$ @HugoManet no, all the possible clusters where each cluster contains more than 2 distinct colors, and also distance between points in a each cluster is less than R $\endgroup$
    – dato nefaridze
    Feb 23, 2021 at 13:00
  • $\begingroup$ @HugoManet my goal is to find maximum number of clusters where: each cluster contains more than 2 distinct colors and distance between each point in a cluster is less than R $\endgroup$
    – dato nefaridze
    Feb 23, 2021 at 13:01
  • 1
    $\begingroup$ Please update your post with the exact question you are trying to solve. What you indicate in the comments is different from the actual post. We cannot help you solve your question unless we know what your question is. It's very frustrating to answer a question, only to have the poster retort with "oops, I forgot to mention X, Y and Z". We cannot read your mind! $\endgroup$
    – Yuval Filmus
    Feb 25, 2021 at 8:29

1 Answer 1

Reset to default
1
$\begingroup$

If you had as much people as number of people in your clusters (each people must have a dot in each cluster) then maybe you could hope for some divide-and-conquer strategy with polynomial runtime, because of greedy-like regularities. For example, in 1D and with 3 people only, after sorting the points along the axis a greedy sweeping algorithm yields an optimal solution ; with some tweaks maybe this kind of ideas could work in higher dimensions. But with some people who can not be part of a specific cluster, this doesn't seem to work anymore.

If I were you, I'd look for approximation algorithms (good ones are known for the 3d matching). Maybe some of them can yield good approximation factors with your problem's structure.

Improve this answer
$\endgroup$
6
  • $\begingroup$ okay thanks, I also think to use Dbscan, (clustering algorithm), what do you think? $\endgroup$
    – dato nefaridze
    Feb 23, 2021 at 13:46
  • $\begingroup$ Hum, you don't actually want to use a clustering algorithm. With your problem specification, there's no interest in having more than three points in a cluster. Any algorithm that allows this to happen probably goes in a bad direction. $\endgroup$
    – Hugo Manet
    Feb 23, 2021 at 13:58
  • $\begingroup$ actually my interest is to have more than (or equal) 3 points in each cluster $\endgroup$
    – dato nefaridze
    Feb 23, 2021 at 14:00
  • $\begingroup$ You necessarily have at least three point in each cluster (one for each color present), but if you add a fourth point to that cluster, the total number of cluster won't increase, so this is useless to you (at least, useless to the problem you described before). Maybe the maximum number of cluster isn't what you want for your application, though ? $\endgroup$
    – Hugo Manet
    Feb 23, 2021 at 14:09
  • 1
    $\begingroup$ The Wikipedia page will be a good start, there's a lot of references : en.wikipedia.org/wiki/3-dimensional_matching $\endgroup$
    – Hugo Manet
    Feb 23, 2021 at 15:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.