  Let $P$ be a set of $n$ colored points in the plane. Introduced by Hart
(1968), a consistent subset of $P$, is a set $S\subseteq P$ such that for every
point $p$ in $P\setminus S$, the closest point of $p$ in $S$ has the same color
as $p$. The consistent subset problem is to find a consistent subset of $P$
with minimum cardinality. This problem is known to be NP-complete even for
two-colored point sets. Since the initial presentation of this problem, aside
from the hardness results, there has not been a significant progress from the
algorithmic point of view. In this paper we present the following algorithmic
results:
  1. The first subexponential-time algorithm for the consistent subset problem.
  2. An $O(n\log n)$-time algorithm that finds a consistent subset of size two
in two-colored point sets (if such a subset exists). Towards our proof of this
running time we present a deterministic $O(n \log n)$-time algorithm for
computing a variant of the compact Voronoi diagram; this improves the
previously claimed expected running time.
  3. An $O(n\log^2 n)$-time algorithm that finds a minimum consistent subset in
two-colored point sets where one color class contains exactly one point; this
improves the previous best known $O(n^2)$ running time which is due to Wilfong
(SoCG 1991).
  4. An $O(n)$-time algorithm for the consistent subset problem on collinear
points; this improves the previous best known $O(n^2)$ running time.
  5. A non-trivial $O(n^6)$-time dynamic programming algorithm for the
consistent subset problem on points arranged on two parallel lines.
  To obtain these results, we combine tools from planar separators,
additively-weighted Voronoi diagrams with respect to convex distance functions,
point location in farthest-point Voronoi diagrams, range trees, paraboloid
lifting, minimum covering of a circle with arcs, and several geometric
transformations.
