有關平面上水平及鉛直線段之范諾氏圖的研究

Abstract

在本範論文中，我們研究一組彼此不相交之水平及鉛直線段的范諾氏圖，而線段間之 距離是以L1度量為準。我們提出一種能在０（NlogN ）時間建立范諾氏圖之演算法。 這演算法是利用分割再合併的技巧。它可以很容易地推廣到目的物是一組彼此不相交 之矩形族。 許多涉及一組彼此不相交之水平及鉛直線段（或矩形）的鄰近問題，譬如：最近鄰近 物搜尋的問題，最近配對的問題，最小展樹的問題等，均可藉此演算法有效地被解決 。