Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
An empirical study of algorithms for point-feature label placement
Christensen J., Marks J., Shieber S. ACM Transactions on Graphics14 (3):203-232,1995.Type:Article
Date Reviewed: Aug 1 1996

Point feature label placement (PFLP), a complex and usually NP-hard problem, is essential for automated cartography. Most approaches, other than arbitrary algorithms that might result in overlapping labels, are based on exhaustive search, greedy algorithms, forms of gradient descent where an initial configuration is improved iteratively, mathematical programming, or stochastic approaches. Gradient descent algorithms are shown to give good results, but can become trapped in local minima.

This valuable paper describes the AI stochastic approach of simulated annealing, which adds to gradient descent by allowing the algorithm to jump out of the local minima that can appear. In simulated annealing, the stochastic element is gradually reduced to zero over the iterations, and gradient descent remains. The results show that this approach is superior in terms of speed and the quality of the resulting map, especially in search spaces with complex terrains. The graphs comparing alternative PFLP algorithms are useful on their own.

The authors argue that their approach is among the easiest to implement in terms of lines of code. They maintain that it also separates the combinatorial-optimization and candidate-position-selection parts of the PFLP problem, which makes it easy to customize further.

Reviewer:  J. R. Geissman Review #: CR119833 (9608-0633)
Bookmark and Share
Cartography (I.2.1 ... )
Geometric Algorithms, Languages, And Systems (I.3.5 ... )
Heuristic Methods (I.2.8 ... )
Screen Design (H.5.2 ... )
Computational Geometry And Object Modeling (I.3.5 )
Problem Solving, Control Methods, And Search (I.2.8 )
Would you recommend this review?
Other reviews under "Cartography": Date
On the problem of placing names in a geographic map
Freeman H., Ahn J. International Journal of Pattern Recognition and Artificial Intelligence 1(1): 121-140, 1987. Type: Article
Jun 1 1988
A Prolog rule-based system for cartographic name placement
Cook A., Jones C. Computer Graphics Forum 9(2): 109-126, 1990. Type: Article
Jan 1 1992
An Interpretation System for Land Register Maps
Boatto L., Consorti V., Del Buono M., Melcarne F., Meucci M., Morelli A., Mosciatti M., Scarci S., Tucci M. Computer 25(7): 25-33, 1992. Type: Article
Nov 1 1993

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy