(54.236.58.220) 您好!臺灣時間:2021/03/08 09:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:施牧發
研究生(外文):Ceesay, Mustapha
論文名稱:帶有兩或三個叉子齒指引線的多重堆疊邊界標記
論文名稱(外文):Multi-stack Boundary Labeling with Two or Three Prong Leaders
指導教授:潘雙洪
指導教授(外文):Poon, Sheung Hung
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊系統與應用研究所
學門:電算機學門
學類:系統設計學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:71
中文關鍵詞:連接線標籤正交地圖NPC
外文關鍵詞:LeaderLabelProngOrthogonalmapNP-complete
相關次數:
  • 被引用被引用:0
  • 點閱點閱:38
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
Boundary labeling deals with labeling point of interest in a visually improved way.
We assume that the features that we want to label can b e represented by points, line segments or simple close polygons. The features are inscribed in an axis parallel rectangle R with no two features sharing the same x or y-coordinate. Labels are
placed at the boundary of the axis parallel rectangle in its
2^n sides where 0 ≤ n ≤ 2. These labels will contain textual information that will describe the features. We want labels that do not overlap and are large enough to be readable. Even simple formulations of this problem are NP-complete.

In this thesis, our objective is to minimize the total leader length and the total number of leader crossings. Our main result is a polynomial time algorithm for crossing-free labeling. We use a sweep line algorithm and dynamic programming
to meet our objectives.

In the algorithm three points will be attached to one horizontal line which runs from the left side of the label to vertically top or bottom of the x−coordinate of the minimum of the three points. Then vertical lines called prong attach each of the point to the horizontal. In theory in order to have a good looking labeling, we make the points to be a multiples of three. Likewise if two points per line are used, we make sure the points are even numbers. If three points are labeled at a time we use three stack at the boundary of R likewise for two points, we use two stacks.

We also analyzed the NP completeness of this boundary labeling problem.
1 Introduction 1
1.1 Related work . . . . . . . . . . . . . . . . . . . 2
1.2 Motivation . . . . . . . . . . . . . . . . . . . . 6
1.3 Preliminary . . . . . . . . . . . . . . . . . . . . 6
1.4 Problem Definition . . . . . . . . . . . . . . . . 9
1.5 Our Contribution . . . . . . . . . . . . . . . . . . 10
1.6 Outline . . . . . . . . . . . . . . . . . . . . . . 10
2 NP-completeness of crossing minimization . . . 11
2.1 Uniform labels, fixed ports with two points per leader . 11
2.2 Chapter Summary . . . . . . . . . . . . . . . . . . 17
3 Minimizing total numb er of crossings . 18
3.1 Minimizing total number of crossing by sorting . . . 18
3.1.1 Uniform labels, fixed ports with two points per leader .18
3.1.2 Uniform labels, fixed ports with three points per leader .19
3.2 Minimizing total number of crossing by swapping . . . 20
3.2.1 Uniform labels, fixed ports with two points per leader . 21
3.2.2 Uniform labels, fixed ports with three points per leader . 21
3.3 Crossing-free labeling . . . . . . . . . . . . 23
3.4 Chapter Summary . . . . . . . . . . . . .25
4 Minimizing the total leader length . 26
4.1 Uniform labels, sliding ports, two points per leader . . 26
4.2 A sweep line algorithm . . . . . . . . . . . . .27
4.2.1 Two points per leader with sliding ports . . . . . 28
4.2.2 Three points per leader with sliding ports . . . . . 35
4.3 Chapter Summary . . . . . . . . . . . . . . . 44
5 Implementation . 46
5.1 Two stacks maps of our algorithm . . . . . . . .46
5.1.1 Counties in Taiwan . . . . . . . . . . 46
5.1.2 Counties in Italy . . . . . . . . . . . . 48
5.1.3 Counties in UK . . . . . . . . . . . . .50
5.1.4 Countries in Africa . . . . . . . . . . . . 52
5.1.5 States in USA . . . . . . . . . . . . . 54
5.1.6 Counties in Europe . . . . . . . . . . 55
5.2 Three stacks maps of our algorithm . . . . . . . . . . 57
5.2.1 Counties in Taiwan . . . . . . . . . . . . . . 57
5.2.2 Countries in Africa . . . . . . . . . . 58
5.2.3 Counties in Italy . . . . . . . . . . . . . . . 60
5.2.4 Counties in UK . . . . . . . . . . . . . . . 61
5.2.5 States in USA . . . . . . . . . . . . . . . . . . 62
5.2.6 Countries in Europe . . . . . . . . . . . . . . . . 63
5.3 Chapter summary . . . . . . . . . . . . . . . . 65
6 Conclusion and Future work . 66
6.1 Conclusion . . . . . . . . . . . . . . . . . . . 66
6.2 Future work . . . . . . . . . . . . . . . . . . 68
Bibliography 70

[1] M. Bekos, M. Kaufmann, M. Nollenburg, and A. Symvonis. Boundary labeling with octilinear leaders. Algorithmica, pages 57:436–461, 2010.

[2] M. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. On multi-stack boundary labeling problems. Proc. of the 10th WSEAS International Conference on Computers, Vouliagmeni, Athens, Greece, July 2006.

[3] M. A. Bekos, S. Cornelsen, M. Fink, S. Hong, M. Kaufmann, M. Nollenburg, I. Rutter, and A. Symvonis. Many-to-one boundary labeling with backbones. Graph Drawing 2013, LNCS 8242:244–255, 2013.

[4] M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Multi-stack boundary labeling problems. In FSTTCS, pages 81–92, 2006.

[5] M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Polygon labeling of minimum leader length. pages 15–21, volume 60 of CRPIT, 2006. Proc of the Asian Pacific Symposium on Information Visualization 2006 (APVIS2006).

[6] M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Area-feature boundary labeling. The Computer Journal, 53(6):827–841, 2010.

[7] M. A. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. pages 49–59, 2004.

[8] M. Benkert, H. Haverkort, M. Kroll, and M. Nollenburg. Algorithms for multicriteria boundary labeling. Journal of Graph Algorithms and Applications, 13(3):289–317, 2009.

[9] A. Gemsa, J. H. Haunert, and M. Nollenburg. Boundary labeling algorithms for panorama images. In GIS, pages 289–298, 2011.

[10] H. J. Kao, C. C. Lin, and H. C. Yen. Many-to-one boundary labeling. Journal of Graph Algorithms and Applications, pages 319–356, 2008.

[11] M. Kaufmann. On map labeling with leaders. In Efficient Algorithms, pages 290–304, 2009.

[12] P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Multi-side boundary labeling. pages 463–474, volume 8037 of Lecture Notes Computer Science., 2014. Proc. 13th International Symposium on Algorithms and Data Structure.(WADS’13).

[13] C. C. Lin. Crossing-free many-to-one boundary labeling with hyperleaders. In Proc. of 3rd IEEE Pacific Visualization Symposium (Pacific Vis.2010), IEEE Press:185–192, 2010.

[14] C. C. Lin, S. H. Poon, S. Takahashi, H. Y. Wu, and H. C. Yen. One-and-a-halfside boundary labeling. In COCOA, pages 387–398, 2011.

[15] C. C. Lin, H. Y. Wu, and H. C. Yen. Boundary labeling in text annotation. pages 110–115, IEEE CS Press, 2009. Proc of 13th International Conference on Information Visualization (IV09).

[16] K. Nakajima, S. Masuda, T. Fujisawa, and T. Kashiwabara. Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers, pages 124–127, 1990.

[17] M. Nollenburg, V. Polishchuk, and M. Sysikaski. Dynamic one-sided boundary labeling. In GIS, pages 310–319, 2010.

[18] M. Nollenburg and V. P. M. Sysikaski. Dynamic one-sided boundary labeling. 2006.

[19] D. papadopoulos and A Symvonis. Combining traditional map labeling with boundary labeling. In SOFSEM, pages 111–122, 2011.

[20] F. Wagner. Approximate map labeling is in Ω (nlogn). B 93-18, December 1993.

[21] F. Wagner. Approximate map labeling is in Ω (nlogn). Information Processing Letters, pages 161–165, 1994.

[22] F. Wagner and A. Wolf. Map labeling heuristics: Provably good and practically useful. In ACM Press, pages 109–118, 1995.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔