Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points are inside the cycle and the blue points are outside the cycle, or vice versa. This problem is called the red blue separation problem.

I am trying to reduce the Traveling Salesman Problem (TSP) to this but I am getting nowhere. Can you please help me with this? Any help is appreciated.

  • 1
    $\begingroup$ If you're doing an algorithm class, I'd be surprised if they ask you for an NP-completeness proof; where I study, those usually are the exam material of complexity classes. Nevertheless, this doesn't sound like TSP to me. You basically want the minimum circumference of a polygon covering all blue or all red vertices. $\endgroup$ – G. Bach Dec 11 '13 at 1:01
  • $\begingroup$ Thanks for the reply guys. I am trying to do it by reducing TSP problem. My idea is , for every instance in TSP we will look for the closest pair - one red point and one blue point and the path will be the one separating these closest reb-blue pair. Is this a correct idea ? $\endgroup$ – Rajesh Golani Dec 11 '13 at 3:55

A separating polygon separating a set of points $S$ from a set of points $T$ is a simple polygonal circuit $P$ for which every point of $S$ is interior or on the boundary of $P$, and every points of $T$ is exterior or on the boundary of $P$. Let $D(P)$ denote the perimeter of a polygon $P$, that is, the sum of the Euclidean lengths of the edges of $P$. If $P$ is a separating polygon for $S$ and $T$ with minimum value of $D(P)$, then $P$ is called a minimum separating polygon.

The problem you describe is known as the minimum separating polygon problem (MSP), formally:

Instance: Two finite point sets $S$ and $T$, and an integer $k$.

Question: Is there a separating polygon $P$ for the sets $S$ and $T$ such that $D(P) \leq k$?

MSP is NP-hard. The hardness was first shown by Eades and Rappaport by a reduction from TSP, see [1], Section 2 for the reduction.

[1] Eades, Peter, and David Rappaport. "The complexity of computing minimum separating polygons." Pattern Recognition Letters 14.9 (1993): 715-718.


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.