An empirical study of algorithms for point feature label placement
| Title: | An empirical study of algorithms for point feature label placement |
| Author: |
Christensen, Jon; Shieber, Stuart; Marks, Joe
Note: Order does not necessarily reflect citation order of authors. |
| Citation: | Stuart M. Shieber, Jon Christensen, and Joe Marks. An empirical study of algorithms for point feature label placement. Transactions on Graphics, 14(3), July 1995. |
| Full Text & Related Files: |
AnEmpiricalStudy.pdf (755.5Kb; PDF) 
|
| Abstract: | A major factor affecting the clarity of graphical displays that include text labels is the degree to which labels obscure display features (including other labels) as a result of spatial overlap. Point-feature label placement (PFLP) is the problem of placing text labels adjacent to point features on a map or diagram so as to maximize legibility. This problem occurs frequently in the production of many types of informational graphics, though it arises most often in automated cartography. In this paper we present a comprehensive treatment of the PFLP problem, viewed as a type of combinatorial optimization problem. Complexity analysis reveals that the basic PFLP problem and most interesting variants of it are NP-hard. These negative results help inform a survey of previously reported algorithms for PFLP; not surprisingly, all such algorithms either have exponential time complexity or are incomplete. To solve the PFLP problem in practice, then, we must rely on good heuristic methods. We propose two new methods, one based on a discrete form of gradient descent, the other on simulated annealing, and report on a series of empirical tests comparing these and the other known algorithms for the problem. Based on this study, the first to be conducted, we identify the best approaches as a function of available computation time. |
| Published Version: | http://dx.doi.org/10.1145/212332.212334 |
| 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:2032678 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5133]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
