二又二分之一維之邊界標示

Abstract

邊界標示是一種使用大型標籤來標示地圖上稠密資訊的視覺化技術，當中地圖上每一 個點特徵會被一條正交線性線連接至地圖邊界外的標籤。盡我們所知的，過去圖形繪 製演算法與電腦圖學之文獻僅考慮平面地圖與平面標籤之二維邊界標示，或僅延伸將 平面地圖改為三維模型之邊界標示，目前為止尚無探討將標籤延伸至三維空間之研 究。然而由於三維邊界標示仍有其定義上之困難度，因此為了縮短二維與三維邊界標 示研究之差距，本計畫將定義二又二分之一維邊界標示，當中標籤可置放在三維空間 中不同於地圖之平面上。由於該定義可分為許多變形，故本計畫擬分別從演算法設計 與分析、啟發式演算法設計、與互動介面系統實作三方向來研究所有可能變形之最佳 化問題。本計畫首先從理論研究的角度來探討各種變形最佳化問題是否存在多項式時 間演算法，找出並證明NP-Complete 問題，並針對難解的問題提出近似演算法。接著， 本計畫將針對較複雜的變形問題，使用混整數規劃或模擬退火法來設計啟發式演算 法。計畫最後將實作所設計之多項式時間演算法與啟發式演算法，開發並整合在一個 互動平板系統，讓使用者可藉由觸碰與滑動的操作來與多維地圖邊界標示作互動。為 增加應用性，進一步設計將地圖置換成三維模型之系統。

Boundary labeling is a map visualization technique that uses large textual labels to highlight dense information on a map, in which each point feature is connected to a label placed on the boundary of the map by a rectilinear line. To the best of our understanding, the previous works from graph drawing algorithms and computer graphics only considered 2D boundary labeling or just made an extension that replaces the 2D map to a 3D model, and so far there have been no previous works with extension to 3D boundary labeling. However, it is difficult to define 3D boundary labeling, and hence, in order to shorten the gap of the studies between 2D and 3D boundary labeling, this project will define the so-called 2.5D boundary labeling, in which labels can be placed on the planes different from the plane accommodating the map. Since the labeling definition has many variants, this project will investigate the optimization problems in all possible variants respectively according to design and analysis of algorithms, design of heuristics, and implementation of interaction system. From theoretical aspect, this project will first investigate whether there exist polynomial-time algorithms among all problem variants, find and prove NP-complete problems, and propose approximation algorithms for those intractable problems. Subsequently, this project will focus on how to use mixed-integer programming or simulated annealing to design heuristics for complicated problem variants. Finally, this project will implement the proposed polynomial-time algorithms and heuristics, develop and integrate them to an interactive pad system, so that users can use touch and scroll operations to manipulate and interact with the 2.5D boundary labeling. Furthermore, we will design the system that replaces 2D maps by 3D models, to inspire more applications.