1
$\begingroup$

Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\{c_1, c_2, c_3\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some of $n$ points such that from each color, $c_i$ ($1 \leq i \leq 3$), there is at least one point in one of chosen intervals.

I assume if the number of colors was a parameter of the problem (like $n$), it could be proved that it is in NP. Then by reducing Set Cover to the above problem, it would actually become an NP-Complete problem too. But I hope by setting a restriction on number of colors (here number of colors is restricted to $3$) the problem can be solved in polynomial time, yet I have not found any polynomial solutions.

$\endgroup$
7
  • $\begingroup$ intervals should cover all the n points? $\endgroup$ Jan 22 at 16:10
  • $\begingroup$ no, not necessarily. They can cover a subset of $n$ points; but they must cover all colors. @InuyashaYagami $\endgroup$ Jan 22 at 16:18
  • 1
    $\begingroup$ If I am understanding it correctly. The minimum number of intervals can be either $1$, $2$, or $3$? $\endgroup$ Jan 22 at 16:36
  • $\begingroup$ I'm not sure I understand your problem. You state that you are looking for a collection of length 1 intervals, of minimum size, such that each interval contains points of all colors. It could be that there is no such collection, for example if one of the points is at distance 10 from all other points. $\endgroup$ Jan 22 at 16:47
  • $\begingroup$ Yes you're right. At most, you can construct 3 intervals each containing only points of one color. At first, I did not realize that. Thank you. @InuyashaYagami $\endgroup$ Jan 22 at 16:53

1 Answer 1

1
$\begingroup$

The trivial solution concluded from the comments is as follows.
Order (~$O(n\log{n})$) the given points as $P=[p_1,...,p_n]$, such that $$i < j \iff p_i < p_j$$. By iterating from $p_1$ to $p_n$ in $O(n^2)$ find all possible intervals of length 1 store them as a tuple of $(\text{subarray of points they contain}, \#\text{unique colors they contain})$.
As the minimum number of intervals can be either.

  • 1: one interval with $\#\text{unique colors they contain}=3$,
  • 2: two intervals one with $\#\text{unique colors they contain}=2$ and one with $\#\text{unique colors they contain}=1$ (with no common color between two intervals),
  • 3: three intervals each with $\#\text{unique colors they contain}=1$ with (no common color).

Check cases 1, 2, and 3 (each in $O(n^2)$) one after another. in worst case the problem can be solved with 3 intervals and in $O(n^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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