Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the 6th Asia-Pacific Symposium on Visualisation, APVIS 2007
DOI: 10.7155/jgaa.00170
Efficient Labeling of Collinear Sites
Vol. 12, no. 3, pp. 357-380, 2008. Regular paper.
Abstract In this paper we study the map labeling problem where the sites to
be labeled are restricted to a line L. Previous models studied in
the map labeling literature fail to produce label placements (i.e.
place each label next to the site it describes) without label
overlaps for certain instances of the problem with dense point sets.
To address this problem, we propose a new approach according to
which, given n sites each associated with an axis-parallel
rectangular label, we aim to place the labels in distinct positions
on the "boundary" of L so that they do not overlap and do
not obscure the site set, and to connect each label with its
associated site through a leader such that no two leaders
intersect.
We evaluate our labeling model under two minimization criteria:
(i) total leader length and (ii) total number of leader bends. We
show that both problems are NP-complete if the labels can be
placed on both sides of L, while we present polynomial time
algorithms for the case where the labels can be placed on only one
side of L.
|
Submitted: May 2007.
Reviewed: August 2007.
Revised: January 2008.
Reviewed: March 2008.
Revised: July 2008.
Accepted: August 2008.
Final: September 2008.
Published: October 2008.
Communicated by
Seok-Hee Hong
|
Journal Supporters
|