Balanced Line Separators of Unit Disk Graphs

• Item type: SIG Technical Reports(1)
• 公開日: 2018-03-01
• タイトル: Balanced Line Separators of Unit Disk Graphs
• タイトル / 言語: en
• タイトル: Balanced Line Separators of Unit Disk Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Ben-Gurion University of the Negev
• 著者所属: National Institute of Informatics／JST, ERATO, Kawarabayashi Large Graph Project
• 著者所属: Ben-Gurion University of the Negev
• 著者所属: Tohoku University
• 著者所属: The University of Electro-Communications／RIKEN Center for Advanced Intelligence Project
• 著者所属: National Institute of Informatics／JST, ERATO, Kawarabayashi Large Graph Project
• 著者所属: National Institute of Informatics／JST, ERATO, Kawarabayashi Large Graph Project
• 著者所属: The University of Electro-Communications
• 著者所属: Ben-Gurion University of the Negev
• 著者所属(英): en
• 著者所属(英): Ben-Gurion University of the Negev
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project
• 著者所属(英): en
• 著者所属(英): Ben-Gurion University of the Negev
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications / RIKEN Center for Advanced Intelligence Project
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Ben-Gurion University of the Negev
• 著者名: Paz, Carmi; Man, Kwun Chiu; Matthew, J. Katz; Matias, Korman; Yoshio, Okamoto; Andre, Van Renssen; Marcel, Roeloffzen; Taichi, Shiitada; Shakhar, Smorodinsky
• 著者名(英): Paz, Carmi; Man, Kwun Chiu; Matthew, J. Katz; Matias, Korman; Yoshio, Okamoto; Andre, Van Renssen; Marcel, Roeloffzen; Taichi, Shiitada; Shakhar, Smorodinsky
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of n unit disks in the plane there exists a line l such that l intersects at most O (√(m + n) log n) disks and each of the halfplanes determined by l contains at most 2n / 3 unit disks from the set, where m is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting O (√m + n) disks exists, but each halfplane may contain up to 4n / 5 disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in n exists when we look at disks of arbitrary radii, even when m = 0. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size O (√m) ).
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of n unit disks in the plane there exists a line l such that l intersects at most O (√(m + n) log n) disks and each of the halfplanes determined by l contains at most 2n / 3 unit disks from the set, where m is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting O (√m + n) disks exists, but each halfplane may contain up to 4n / 5 disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in n exists when we look at disks of arbitrary radii, even when m = 0. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size O (√m) ).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-167, 号 5, p. 1-3, 発行日 2018-03-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会