## Discretized Approaches to Schematization

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.

keywords: Computational Geometry, Graph Drawing, Geographical Information Analysis

### Conference Proceedings (peer-reviewed)

Maarten Löffler, Wouter Meulemans

Discretized Approaches to Schematization

Proc. 29th Canadian Conference on Computational Geometry

(to appear), 2017

back to list