並列摘要
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.
並列關鍵字
boundary labeling參考文獻
延伸閱讀
- 林宇清（2013）。多元對位標記定位技術之研究〔碩士論文，國立臺中科技大學〕。華藝線上圖書館。https://doi.org/10.6826/NUTC.2013.00096
- 郭伊琳（2005）。國內公共指示性標誌系統分類之研究〔碩士論文，大同大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0081-0607200917235014
- 康德龍（2005）。最有利標多元尺度法評定方式之研究〔碩士論文，國立臺北科技大學〕。華藝線上圖書館。https://doi.org/10.6841/NTUT.2005.00009
- 葉季珊（2012）。On (2,1)-total labelings of 4-regular graphs〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu201200226
- 蔡宗翰（2009）。Primitive Boundary〔碩士論文，國立交通大學〕。華藝線上圖書館。https://doi.org/10.6842/NCTU.2009.00660