請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/3943完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞 | |
| dc.contributor.author | Chia-Han Chung | en |
| dc.contributor.author | 鍾家涵 | zh_TW |
| dc.date.accessioned | 2021-05-13T08:38:58Z | - |
| dc.date.available | 2016-06-11 | |
| dc.date.available | 2021-05-13T08:38:58Z | - |
| dc.date.copyright | 2016-06-11 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-05-07 | |
| dc.identifier.citation | [1] On simultaneous planar graph embeddings. Computational Geometry, 36(2):117 – 130, 2007.
[2] M. A. Bekos, M. Kaufmann, M. Nollenburg, and A. Symvonis. Boundary labeling with octilinear leaders. Algorithmica, 57(3):436–461, 2009. [3] M.A.Bekos,M.Kaufmann,A.Symvonis,andA.Wolff.Boundarylabeling:Models and efficient algorithms for rectangular maps. Computational Geometry, 36(3):215 – 236, 2007. [4] M. Benkert, H. J. Haverkort, M. Kroll, and M. Nollenburg. Algorithms for multi- criteria one-sided boundary labeling. In Graph Drawing, 15th International Sympo- sium, GD 2007, pages 243–254, 2007. [5] T. Biedl, F. J. Brandenburg, and X. Deng. On the complexity of crossings in permu- tations. Discrete Mathematics, 309(7):1813–1823, 2009. 13th International Sympo- sium on Graph Drawing, 2005. [6] T.Blasius,S.G.Kobourov,andI.Rutter.Simultaneousembeddingofplanargraphs. In Handbook of Graph Drawing and Visualization, chapter 11. CRC Press, 2013. [7] C. Demetrescu and I. Finocchi. Breaking cycles for minimizing crossings. Journal of Experimental Algorithmics, 6, 2001. [8] C. Erten, S. G. Kobourov, V. Le, and A. Navabi. Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers, chap- 39 ter Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes, pages 437–449. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. [9] A. Gemsa, J.-H. Haunert, and M. Nollenburg. Boundary-labeling algorithms for panorama images. In Proceedings of the 19th ACM SIGSPATIAL International Con- ference on Advances in Geographic Information Systems, GIS ’11, pages 289–298. ACM, 2011. [10] N. Heinsohn, A. Gerasch, and M. Kaufmann. Boundary labeling methods for dy- namic focus regions. In Visualization Symposium (PacificVis), pages 243–247. IEEE, 2014. [11] Z.-D. Huang, S.-H. Poon, and C.-C. Lin. Algorithms and Computation: 8th Inter- national Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Pro- ceedings, chapter Boundary Labeling with Flexible Label Positions, pages 44–55. Springer International Publishing, Cham, 2014. [12] M. Junger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications, pages 1–25, 1997. [13] K.G.KakoulisandI.G.Tollis.Labelingalgorithms.InHandbookofGraphDrawing and Visualization, chapter 15. CRC Press, 2013. [14] P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Algorithms and Data Structures: 13th International Symposium, WADS 2013, Lon- don, ON, Canada, August 12-14, 2013. Proceedings, chapter Two-Sided Boundary Labeling with Adjacent Sides, pages 463–474. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. [15] P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Multi-sided boundary labeling. Algorithmica, pages 1–34, 2015. [16] K.-C. Lin, H.-J. Kao, and H.-C. Yen. Many-to-one boundary labeling. Journal of Graph Algorithms and Applications, 12, 2008. 40 [17] X. Munoz, W. Unger, and I. Vrt’o. One sided crossing minimization is np-hard for sparse graphs. In Graph Drawing, volume 2265 of Lecture Notes in Computer Science, pages 115–123. Springer Berlin Heidelberg, 2002. [18] M. Nollenburg, V. Polishchuk, and M. Sysikaski. Dynamic one-sided boundary labeling. In Proceedings of the 18th SIGSPATIAL International Conference on Ad- vances in Geographic Information Systems, GIS ’10, pages 310–319. ACM, 2010. [19] K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hi- erarchical system structures. IEEE Transactions on Systems, Man & Cybernetics, 11(2):109–125, 1981. [20] F. Wagner and A. Wolff. A practical map labeling algorithm. Computational Geom- etry, 7(5–6):387 – 404, 1997. 11th ACM Symposium on Computational Geometry. [21] A. Wolff. Graph drawing and cartography. In Handbook of Graph Drawing and Visualization, chapter 23. CRC Press, 2013. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/3943 | - |
| dc.description.abstract | In boundary labeling, each feature point is connected to a label placed
on the boundary of a rectangular image by a leader, which may be a rectilinear or a straight line segment. Currently, all the research about boundary labeling focuses on how to generate label placements for one image with high readability. However, there may be a series of related images, which share all, or parts of the same feature and label set, need to be labeled. If we calculate label placements for each image separately, it is hard to keep track of the relationship between images. To overcome the above difficulty, in this thesis we propose a new problem called simultaneous boundary labeling. We keep the relationship between images by limiting common features and labels of a series of images in the same place, and find a common label placement for all images with minimal leader crossing number and minimal total leader length to increase the readability. We design some heuristic algorithms when there are two related images need to be labeled and show the problem to be NP-complete when there are more than four images in the series. The leader length minimization problem can be solved by a weighted bipartite matching algorithm. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-13T08:38:58Z (GMT). No. of bitstreams: 1 ntu-105-R02921073-1.pdf: 4310448 bytes, checksum: 4a596176a2a02b679387967d365fd1fb (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 誌謝i
摘要ii Abstract iii 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Preliminaries 6 2.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Simultaneous boundary labeling 13 3.1 type-s leader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 type-po leader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 type-opo leader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 Extension of simultaneous boundary labeling for two images 32 5 Conclusion and Future Work 37 Bibliography 39 | |
| dc.language.iso | en | |
| dc.subject | barycenter algorithm | zh_TW |
| dc.subject | boundary labeling | zh_TW |
| dc.subject | crossing minimization | zh_TW |
| dc.subject | bipartite matching | zh_TW |
| dc.subject | simultaneous graph drawing | zh_TW |
| dc.title | 同步邊界標籤之演算法設計與分析 | zh_TW |
| dc.title | Algorithm Design and Analysis for Simultaneous
Boundary Labeling | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王勝德,林春成,郭斯彥,雷欽隆 | |
| dc.subject.keyword | simultaneous graph drawing,boundary labeling,crossing minimization,bipartite matching,barycenter algorithm, | zh_TW |
| dc.relation.page | 41 | |
| dc.identifier.doi | 10.6342/NTU201600238 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2016-05-07 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf | 4.21 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。