Many-to-One Boundary Labeling
Date Issued
2006
Date
2006
Author(s)
Kao, Hao-Ren
DOI
en-US
Abstract
Boundary labeling is an important variant of information visualization which has found many applications in the real world. A conventional boundary labeling scheme connects one site to a unique label placed on the boundary of the drawing. In certain applications of boundary labeling, however, several sites may be required to connect to an identical label in a picture with abundant numbers of sites and labels.
In this thesis, we consider the crossing minimization problem for boundary labeling of multi-site connecting to one label, i.e. the problem of finding a leader and label placement, such that the number of total crossings is minimized. We show that the one-sided labeling problem and the two-sided labeling problem for type-opo leaders (rectilinear lines with either zero or two bends) are NP-complete. We also give approximation algorithms and greedy heuristics for the problems. For all the problems in this thesis, we assume that the connecting label port is a fixed port, i.e. the point where each leader is connected to the label is fixed. We also prove that the one-sided labeling problem for type-po leaders (rectilinear lines with either zero or one bend) is NP-complete and give a heuristic algorithm for it. Finally we study the leader length minimization problem for multi-site-to-one-label boundary labeling and present an O(n2log3n) algorithm.
Subjects
邊界標記
boundary labeling
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93921024-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):65159af483b16dc7c3a181432f37a535