2016/06/21 by Wouter Meulemans, Meulemans, Wouter
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Visualization and Analytics #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1606.06488
Part of these results supersede those in arXiv:1306.2827
arxiv created 2016/06/21 · openalex publication_date 2016/06/21 · arxiv updated 2016/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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échet distance. We prove that it is NP-hard to compute a cycle that approximates the minimal Fréchet 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.