I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it.

Let $C$ and $P$ be two sets of point in the plane , such that k = $|C|$ and $n = |P|$. let $r = max_{p\in P}min_{ c \in C } \|c-p\|$ be the cover radius of $P$ by $C$ give a $\mathcal{O}(n+k\log n)$ expected time algorithm that output a number $\alpha$ such that $r \leq \alpha \leq 10r$

Any hint for that?

  • $\begingroup$ While I don't immediately see the answer myself, a good place to start is to have another look at the preceding chapter and determine which techniques seem appropriate for this problem. Try to identify a problem in the chapter similar to this problem and see if you can adapt the techniques used. If you're still stuck at that point, please explain here what you've tried and why it doesn't work. That way, we can more easily provide a suitable hint. $\endgroup$ – Discrete lizard May 27 '19 at 19:12

Your Answer

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

Browse other questions tagged or ask your own question.