Crossing-free many-to-one boundary labeling with hyperleaders

Chun-Cheng Lin*

*此作品的通信作者

研究成果: Conference contribution同行評審

26 引文 斯高帕斯(Scopus)

摘要

In boundary labeling, each point site is uniquely connected to a label placed on the boundary of an enclosing rectangle by a leader, which may be a rectilinear or straight line segment. Most of the results reported in the literature for boundary labeling deal with the so-called one-to-one boundary labeling, i.e., different sites are labelled differently. In certain applications of boundary labeling, however, more than one site may be required to be connected to a common label. In this case, the presence of crossings among leaders often becomes inevitable such that the labeling often has a high degree of confusion in visualization. In this paper, for multisite-to-one-label boundary labeling, crossings among leaders are avoided by substituting hyperleaders for leaders and by applying dummy labels (i.e., copies/duplicates of labels). Minimizing the number of dummy labels becomes a critical design issue as dummy labels are not required in the initial setting. Therefore, we consider the problem of minimizing the number of dummy labels for multisite-to-one-label boundary labeling, i.e., finding the placements of labels and hyperleaders such that the total number of dummy labels is minimized and there are no crossings among hyperleaders. Furthermore, after the number of dummy labels is determined, minimizing the total hyperleader length as well as the bends of hyperleaders is also concerned in postprocessing procedure. In this paper, we present polynomial time algorithms for the above one-side and two-side labeling schemes, and show their correctness from a theoretical point of view. In addition, we provide a simulated annealing algorithm for the four-side labeling schemes with objective to minimize the total number of dummy labels as well as the total leader length. Experimental results show that our four-side solutions look promising, as compared to the optimal solutions.

原文English
主出版物標題IEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings
頁面185-192
頁數8
DOIs
出版狀態Published - 6 5月 2010
事件IEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Taipei, Taiwan
持續時間: 2 3月 20105 3月 2010

出版系列

名字IEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings

Conference

ConferenceIEEE Pacific Visualization Symposium 2010, PacificVis 2010
國家/地區Taiwan
城市Taipei
期間2/03/105/03/10

指紋

深入研究「Crossing-free many-to-one boundary labeling with hyperleaders」主題。共同形成了獨特的指紋。

引用此