|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/4894
|
| タイトル: | Shattering a set of objects in 2D |
| 著者: | Nandy, Subhas C.
Asano, Tetsuo
Harayama, Tomohiro |
| キーワード: | Duality
topological line sweep
separator
shattering |
| 発行日: | 2002-10-15 |
| 出版者: | Elsevier |
| 誌名: | Discrete Applied Mathematics |
| 巻: | 122 |
| 号: | 1-3 |
| 開始ページ: | 183 |
| 終了ページ: | 194 |
| DOI: | 10.1016/S0166-218X(01)00315-8 |
| 抄録: | In this paper, we propose an algorithm for shattering a set of disjoint line segments of arbitrary length and orientation placed arbitrarily on a 2D plane. The time and space complexities of our algorithm are O(n^2) and O(n), respectively. It is an improvement over the O(n^2 log n) time algorithm proposed in [7]. A minor modification of this algorithm applies when objects are simple polygons, keeping the time and space complexities invariant. |
| Rights: | NOTICE: This is the author's version of a work accepted for publication by Elsevier. Subhas C. Nandy, Tetsuo Asano and Tomohiro Harayama, Discrete Applied Mathematics, 122(1-3), 2002, 183-194, http://dx.doi.org/10.1016/S0166-218X(01)00315-8 |
| URI: | http://hdl.handle.net/10119/4894 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| C2220.pdf | | 198Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
