著者

浅野 哲夫 ムルツァー ウォルフガング ロウテ ギュンター ワング ヤジュン

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.110, no.232, pp.1-7, 2010-10-08

---

本報告では定数作業領域あるいは対数記憶領域と呼ばれる制約のある計算モデル上で効率よく実行できる幾何問題に対するアルゴリズムを提案する.まず最初に平面上に与えられた点集合に対するデローネイ三角形分割を描くアルゴリズムから始め,それをボロノイ図を描く問題に応用する.これらの問題に対しては,O(n)の記憶領域を用いることができるならΘ(n log n)時間のアルゴリズムが知られているが,本報告で述べるアルゴリズムはO(1)の作業領域だけを用いてO(n^2)時間で実行できるものである.さらに,これらのアルゴリズムを用いて,平面上に与えられた点集合に対するユークリッド最小木を求める効率の良いアルゴリズムも与える.