Two-Label Minimum Consistent Subsets

Let E be a set of labeled points in Euclidean space. A subset C of E is said to be a consistent subset of E if it has the property that for any point e epsilon E/C, the closest point in C to e has the same label as e. We show that the problem of computing a minimum cardinality consistent subset of a set of labeled points in the plane is NP-complete even when restricted to the case where there are only two possible labels.