Abstract
在一蜂巢式無線電網路系統中，蜂巢之佈局乃在於埋設六角形細胞(hexagonal cell)於某動態用戶的需求區域，例如一些城市和道路。每一六角形細胞中至少含有一個轉接控制站 (base site)，在需求區域中的動態用戶利用無線電頻道透過控制站的轉接與另一用戶通話。在平面上給定 n個實體 (可為多邊形或點) 的集合N 及P 個半徑為r 之六角形的集體M ，佈局函數L(M,N)是一種放置此 P個六角形於平面上，且使得所有 N中之n 個實體皆為六角形覆蓋之方法。進一步定義此佈局L(M,N)的相對應無向圖形 L(M,N)=(V,E),圖形中每一頂點為六角形的中心點，二頂點間距離小於 r 者構成圖形的一邊。蜂巢佈局問題的幾何意義乃在於決定所給定的實體集合 N及六角形集合 M，是否存在一種佈局L(M,N)，使得其相對應的圖形 L(M,N) 是相連的 (2-相連的，3-相連的) 。在平面上給定n 個半徑為 r之六角形集合M 及一含有P 點的集合 N，放置函數A(N,M)是一種將 P個點置於平面之上，且使得所有 M中六角形內部皆含有至少一點的方法。進一步定義此放置函數A(N,M)的相對應無向圖形 A(N,M)=(V,E),圖形中每一頂點相對於一個放置點，二頂點間距離小於 r 者構成圖形的一邊。控制站放置問題的幾何意義乃在於給定平面上六角形集合 M及點集合 N，決定是否存在一種放置方法A(N,M)，使得每一個六角形內部至少含有一放置站，且其相對應圖形是相連的 (2-相連的)。吾人證明了上述二類五個問題都是NP-hard 問題。這些證明是利用3-Satisfiability問題來縮換(reduce)的。