Paper Info
Title
Heuristics for cartographic label placement problems
Abstract
The cartographic label placement problem is an important task in automated cartography and Geographical Information Systems. Positioning the texts requires that overlap among texts should be avoided, that cartographic conventions and preference should be obeyed. This paper examines the point-feature cartographic label placement problem (PFCLP) as an optimization problem. We formulate the PFCLP considering the minimization of existing overlaps and labeling of all points on a map. This objective improves legibility when all points must be placed even if overlaps are inevitable. A new mathematical formulation of binary integer linear programming that allows labeling of all points is presented, followed by some Lagrangean relaxation heuristics. The computational tests considered instances proposed in the literature up to 1000 points, and the relaxations provided good lower and upper bounds.
Year
DOI
Venue
2006
10.1016/j.cageo.2005.10.004
Computers & Geosciences
Keywords
Field
DocType
Label placement,Modeling,Lagrangean relaxation,Lagrangean/Surrogate relaxation,Heuristic
Legibility,Information system,Geographic information system,Heuristic,Computer science,Algorithm,Minification,Heuristics,Linear programming,Optimization problem,Cartography
Journal
Volume
Issue
ISSN
32
6
0098-3004
Citations 
PageRank 
References 
8
0.57
12
Authors
2
Name
Order
Citations
PageRank
Glaydston Mattos Ribeiro120213.79
Luiz Antonio Nogueira Lorena249836.72