NDLI: An empirical study of algorithms for point-feature label placement

Content Provider	ACM Digital Library
Author	Christensen, Jon Shieber, Stuart Marks, Joe
Copyright Year	1995
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.
Starting Page	203
Ending Page	232
Page Count	30
File Format	PDF
ISSN	07300301
e-ISSN	15577368
DOI	10.1145/212332.212334
Volume Number	14
Issue Number	3
Journal	ACM Transactions on Graphics (TOG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1995-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Automated cartography Heuristic search Label placement Simulated annealing Stochastic methods
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Empirical Study of Algorithms for Point Feature Label Placement (1994)

Tabu Search Heuristic For Point-Feature Cartographic Label Placement (2002)

Tabu Search Heuristic for Point-Feature . . . (2002)

An Empirical Study of Algorithms for Point-Feature Label Placement (1995)

An Effective Mixed Annealing/Heuristic Algorithm for Problems in Mechanical Design

An empirical study of algorithms for point-feature label placement (1995)

An Empirical Study of Algorithms for Point-Feature Label Placement (1995)

An evaluation of parallel simulated annealing strategies with application to standard cell placement

Drawing Inspiration From Human Design Teams for Better Search and Optimization: The Heterogeneous Simulated Annealing Teams Algorithm

An empirical study of algorithms for point-feature label placement

Similar Documents

An Empirical Study of Algorithms for Point Feature Label Placement (1994)

Tabu Search Heuristic For Point-Feature Cartographic Label Placement (2002)

Tabu Search Heuristic for Point-Feature . . . (2002)

An Empirical Study of Algorithms for Point-Feature Label Placement (1995)

An Effective Mixed Annealing/Heuristic Algorithm for Problems in Mechanical Design

An empirical study of algorithms for point-feature label placement (1995)

An Empirical Study of Algorithms for Point-Feature Label Placement (1995)

An evaluation of parallel simulated annealing strategies with application to standard cell placement

Drawing Inspiration From Human Design Teams for Better Search and Optimization: The Heterogeneous Simulated Annealing Teams Algorithm

An empirical study of algorithms for point-feature label placement