THE COMPLEXITY OF COMPUTING MINIMUM SEPARATING POLYGONS

Suppose that S and T are two sets of points in the plane. A separating polygon separating S from T is a simple polygonal circuit P for which every point of S is interior or on the boundary of P, and every point of T is exterior or on the boundary of P. Let D (P) denote the perime ter of a polygon P, that is, the sum of the Euclidean lengths of the e dges 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 of computing a minimum separating polygon has been studied in various fo rms in connection with applications to computer vision and collision a voidance. In this note we show that the version of the problem where S and T are finite sets of points is NP-hard.