Discretized Approaches to Schematization

Abstract

For both the Fréchet distance and the symmetric difference, we show that finding the simple polygon $S$ restricted to a grid that best resembles a simple polygon $P$ is NP-complete, even if: (1) we require that $S$ and $P$ have equal area; (2) we require turns to occur in a specified sequence for the Fréchet distance; (3) we permit $S$ to have holes for the symmetric difference.