著者

桜井 裕邦 今井 桂子

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1999, no.26, pp.47-52, 1999-03-15

参考文献数

9

---

本稿では3次元における凸多面体の表面に沿った近似最短経路問題に対し,HershbergerとSuriの2倍近似アルゴリズム[5]を計算機実験にて評価をおこなう.ChenとHanはO(n^2)時間で正確な距離を見つけるアルゴリズム[3]を示した.また,近似最短経路問題においては,単純なO(n)時間での近似アルゴリズムが[5]にて提案され,そのアルゴリズムは最適な距離の高々2倍の距離を与える.本稿ではこれらのアルゴリズムを実装し,理論値と実際の性能との比較をおこなう.In this paper, we consider the shortest path problem between two points on the surface of a convex polytope in three dimensions. Chen and Han presented an algorithm for determining the exact shortest path in O(n^2) time. For the approximate shortest path problem, a simple O(n) approximation algorithm are proposed in [5], and the algorithm produces a path of length at most 2 times the optimal. We implement these alogorithms and compare their theoretical and practical performances.