  To produce cartographic maps, simplification is typically used to reduce
complexity of the map to a legible level. With schematic maps, however, this
simplification is pushed far beyond the legibility threshold and is instead
constrained by functional need and resemblance. Moreover, stylistic geometry is
often used to convey the schematic nature of the map. In this paper we explore
discretized approaches to computing a schematic shape $S$ for a simple polygon
$P$. We do so by overlaying a plane graph $G$ on $P$ as the solution space for
the schematic shape. Topological constraints imply that $S$ should describe a
simple polygon. We investigate two approaches, simple map matching and
connected face selection, based on commonly used similarity metrics.
  With the former, $S$ is a simple cycle $C$ in $G$ and we quantify resemblance
via the Fr\'echet distance. We prove that it is NP-hard to compute a cycle that
approximates the minimal Fr\'echet distance over all simple cycles in a plane
graph $G$. This result holds even if $G$ is a partial grid graph, if area
preservation is required and if we assume a given sequence of turns is
specified.
  With the latter, $S$ is a connected face set in $G$, quantifying resemblance
via the symmetric difference. Though the symmetric difference seems a less
strict measure, we prove that it is NP-hard to compute the optimal face set.
This result holds even if $G$ is full grid graph or a triangular or hexagonal
tiling, and if area preservation is required. Moreover, it is independent of
whether we allow the set of faces to have holes or not.
