Next: MINIMUM NUMERICAL TAXONOMY
Up: Miscellaneous
Previous: MAXIMUM FREQUENCY ALLOCATION
  Index
- 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
[374].
- 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].
Viggo Kann
2000-03-20