The Computational Complexity of Cartographic Label Placement

DSpace/Manakin Repository

The Computational Complexity of Cartographic Label Placement

Citable link to this page

 

 
Title: The Computational Complexity of Cartographic Label Placement
Author: Marks, Joe; Shieber, Stuart Merrill ORCID  0000-0002-7733-8195

Note: Order does not necessarily reflect citation order of authors.

Citation: Marks, Joe and Stuart Shieber. 1991. The Computational Complexity of Cartographic Label Placement. Harvard Computer Science Group Technical Report TR-05-91.
Full Text & Related Files:
Abstract: We examine the computational complexity of cartographic label placement, a problem derived from the cartographer's task of placing text labels adjacent to map features in such a way as to minimize overlaps with other labels and map features. Cartographic label placement is one of the most time-consuming tasks in the production of maps. Consequently, several attempts have been made to automate the label-placement task for some or all classes of cartographic features (punctual, linear, or areal features), but all previously published algorithms for the most basic task--point-feature-label placement--either exhibit worst-case exponential time complexity, or incorporate incomplete heuristics that may fail to find an admissible labeling even when one exists. The computational complexity of label placement is therefore a matter of practical significance in automated cartography. We show that admissible label placement is NP-complete, even for very simple versions of the problem. Thus, no polynomial time algorithm exists unless P = N P . Similarly, we show that optimal label placement can be solved in polynomial time if and only if P = N P , and this result holds even if we require only approximately optimal placements. The results are especially interesting because cartographic label placement is one of the few combinatorial problems that remains NP-hard even under a geometric (Euclidean) interpretation. The results are of broader practical significance, as they also apply to point-feature labeling in non-cartographic displays, e.g., the labeling of points in a scatter plot.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:24019781
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters