Suppose given $n$ pair of points $P=\{(p_1,q_1),\dots,(p_n,q_n)\}$ in the plane that each pair $(p_i,q_i)\in \mathbb{R}^2$ can't belong to the same group. We want to partition points into $K$ groups such that we minimize function $f:x\rightarrow \mathbb{R}$. So we try to find an efficient algorithm. We want a running time of $O(n^3)$ or better.

My attempt: I find a black box that can partition $2n$ points in the plane in $O(n\log n)$ and minimize $f(n)$, without any constraint. But at this step a get stuck that how I can use black box?

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – Nathaniel
    Jan 10, 2022 at 6:10
  • $\begingroup$ Hint: each call of the black box algorithm split the dataset in two. So, you can build a k-d tree or a quadtree and run the algorithm on each split. This means you can solve this in $O(n^2\log n)$ or $O(n^3)$ (I think n^3 would be more practical, as it's easier to make robust) $\endgroup$
    – Discrete lizard
    Jan 10, 2022 at 8:44
  • $\begingroup$ Is $f$ a function of two groups of points to nonnegative numbers? Or two groups of the same number of points? $\endgroup$
    – John L.
    Jan 11, 2022 at 15:59
  • $\begingroup$ Does the black box partition $2n$ points into two groups of $n$ points? $\endgroup$
    – John L.
    Jan 11, 2022 at 16:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.