著者

金丸 直義 西関 隆夫 浅野 哲夫

雑誌

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

巻号頁・発行日

vol.1992, no.27(1991-AL-026), pp.25-32, 1992-03-23

---

本報告では,与えられた凸m角形内部のすべての整数格子点を列挙するO(+m+log )時間のアルゴリズムを与える.ここでKは列挙された格子点の個数であり,nは凸m角形の大きさ,すなわちm角形を包含する軸平行な長方形の垂直,水平な辺のうち短い方の長さである.さらに,m個の制約式を持つ2変数整数計画問題を解くO( log m+log )時間のアルゴリズムを与える.ここでnは計画問題の許容解空間である凸多角形の大きさを表す.このアルゴリズムは従来知られているアルゴリズムより単純であり,時間計算量も改善している.