An empirical study of algorithms for point feature label placement

DSpace/Manakin Repository

An empirical study of algorithms for point feature label placement

Citable link to this page

 

 
Title: An empirical study of algorithms for point feature label placement
Author: Christensen, Jon; Shieber, Stuart ORCID  0000-0002-7733-8195 ; 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:
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
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters