Next: MINIMUM NUMERICAL TAXONOMY Up: Miscellaneous Previous: MAXIMUM FREQUENCY ALLOCATION Index

### MINIMUM RED-BLUE SEPARATION

- INSTANCE: Finite sets R and B of points in the Euclidean plane.

- SOLUTION: A simple polygon P that separates the red points (points in R) from the blue points (points in B).

- MEASURE: Euclidean length of the perimeter of P.

- Good News: Approximable within [354].

- Comment: Variation in which the objective function is the combinatorial size of the separating polygon, that is, the number of vertices in the polygon, is approximable within [2].