Problem Detail: 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.
Asked By : Rajesh Golani
Answered By : Juho
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18852
