WEKO3
-
RootNode
アイテム
多角形内部の格子点列挙と2変数整数計画問題への応用
https://ipsj.ixsq.nii.ac.jp/records/32547
https://ipsj.ixsq.nii.ac.jp/records/32547470d2755-38d7-411b-9f1b-0aef4015e242
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL91026004.pdf (1.2 MB)
|
Copyright (c) 1992 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1992-03-23 | |||||||
| タイトル | ||||||||
| タイトル | 多角形内部の格子点列挙と2変数整数計画問題への応用 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Efficient Enumeration of Grid Points in a Polygon and its Application to Integer Programming | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東北大学工学部通信工学科 | ||||||||
| 著者所属 | ||||||||
| 東北大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 大阪電気通信大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Electorical Communications Faculty of Engineering, Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Engineering Faculty of Engineering, Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Electro - Communication University | ||||||||
| 著者名 |
金丸, 直義
西関, 隆夫
浅野, 哲夫
× 金丸, 直義 西関, 隆夫 浅野, 哲夫
|
|||||||
| 著者名(英) |
Naoyoshi, Kanamaru
Takao, Nishizeki
Tetsuo, Asano
× Naoyoshi, Kanamaru Takao, Nishizeki Tetsuo, Asano
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本報告では，与えられた凸m角形内部のすべての整数格子点を列挙するO（+m+log ）時間のアルゴリズムを与える．ここでKは列挙された格子点の個数であり，nは凸m角形の大きさ，すなわちm角形を包含する軸平行な長方形の垂直，水平な辺のうち短い方の長さである．さらに，m個の制約式を持つ2変数整数計画問題を解くO（ log m+log ）時間のアルゴリズムを与える．ここでnは計画問題の許容解空間である凸多角形の大きさを表す．このアルゴリズムは従来知られているアルゴリズムより単純であり，時間計算量も改善している． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper presents an algorithm for enumerating all the integer-grid points in a given convex m-gon in O(K+m+log n) time where K is the number of such grid points and n is the dimension of the m-gon, i.e., the shorter length of the horizontal and vertical sides of an axis-parallel rectangle enclosing the m-gon. Furthermore the paper gives a simple algorithm which solves a two-variable integer programming problem with m constraints in O(m log m+log n) time where n is the dimension of a convex polygon corresponding to the feasible solution space. This improves the best known algorithm in complexity and simplicity. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1992, 号 27(1991-AL-026), p. 25-32, 発行日 1992-03-23 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
