  We give the first polynomial-time approximation schemes (PTASs) for the
following problems: (1) uniform facility location in edge-weighted planar
graphs; (2) $k$-median and $k$-means in edge-weighted planar graphs; (3)
$k$-means in Euclidean spaces of bounded dimension. Our first and second
results extend to minor-closed families of graphs. All our results extend to
cost functions that are the $p$-th power of the shortest-path distance. The
algorithm is local search where the local neighborhood of a solution $S$
consists of all solutions obtained from $S$ by removing and adding
$1/\epsilon^{O(1)}$ centers.
