WEKO3
インデックスリンク
アイテム
Partial construction of an arrangement of lines and its application to optimal partitioning of bichromatic point set
https://doi.org/10.24517/00063365
https://doi.org/10.24517/000633651f4c8bfc-28e3-4705-a60f-f2095a5550a0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-ASANO-T-77-595-600.pdf (187.1 kB)
|
.png)
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-07-22 | |||||||
| タイトル | ||||||||
| タイトル | Partial construction of an arrangement of lines and its application to optimal partitioning of bichromatic point set | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| ID登録 | ||||||||
| ID登録 | 10.24517/00063365 | |||||||
| ID登録タイプ | JaLC | |||||||
| 著者 |
Asano, Tetsuo
× Asano, Tetsuo× Tokuyama, Takeshi |
|||||||
| 著者別表示 |
浅野, 哲夫
× 浅野, 哲夫
|
|||||||
| 提供者所属 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 金沢大学 | |||||||
| 書誌情報 |
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E77-A, 号 4, p. 595-600, 発行日 1994 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 0916-8508 | |||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1745-1337 | |||||||
| NCID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA10826239 | |||||||
| 出版者 | ||||||||
| 出版者 | Institute of Electronics, Information and Communication, Engineers, IEICE | |||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | This paper presents an efficient algorithm for construction at-most-k levels of an arrangement of n lines in the plane in ime O(nk + nlogn), which is optimal since Ω(nk) line segments are included there. The algorithm can sweep the at-most-k levels of the arrangement using O(n) space. Although Everett recently gave an algorithm for constructing the at-most-k levels with the same time complexity independently, our algorithm is superior with respect to the space complexity as a sweep algorithm. Then, we apply the algorithm to a bipartitioning problem of a bichromatic point set. | |||||||
| 権利 | ||||||||
| 権利情報 | Copyright © Institute of Electronics, Information and Communication, Engineers, IEICE | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | https://www.ieice.org/jpn/trans_online/ | |||||||
| 関連名称 | https://www.ieice.org/jpn/trans_online/ | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | http://www.ieice.org/eng/index.html | |||||||
| 関連名称 | http://www.ieice.org/eng/index.html | |||||||
