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