Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

I would like to make $d(X,Y)$ minimum possible. Which algorithm should i use for choosing points $y_1, ..., y_M$ ?

Thanks in advance.

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

  • $\begingroup$ What have you tried? What approaches have you considered, and why did you reject them? What algorithmic design paradigms have you tried, and what happened when you tried them? Have you tried solving some special cases? $\endgroup$ – D.W. Mar 14 '16 at 2:45
  • $\begingroup$ I tried brute force and dynamic programming. But the first was certainly to slow and in second approach my algorithm wasn't correct. $\endgroup$ – Igor Mar 14 '16 at 11:02

Your problem is known as the unweighted one-dimensional $k$-center problem. See for example a recent paper by Chen, Li and Wang.

  • $\begingroup$ Thank you very much for your answer. But what if i want to know only the optimal value of d(X,Y) without actually constructing Y? Does it simplify the case? $\endgroup$ – Igor Mar 14 '16 at 2:26
  • $\begingroup$ @Igor, your question asked about choosing the points rather than about minimizing d(X,Y), and it seems like this answers the question that was asked. When you have a follow-up question, rather than posting a comment it's usually better to ask a new question (after thinking hard about it and seeing what you can come up with on your own). $\endgroup$ – D.W. Mar 14 '16 at 2:47

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.