| 講演名 | 2010-01-25 ユークリッド空間及びノルム空間における地帯図 河村 彰星, 徳山 豪, マトウシェク イルジ, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 地帯図はボロノイ図に似た概念であり,距離空間内の幾つかの集合(核と呼ぶ)が銘々に領土の拡大を図るときに達する平衡を表す.勢力域に関する距離の方程式を以て定義する.浅野,マトウシェク,徳山はユークリッド平面において,核が点であるときに地帯図が唯一つ存在することを示した.レエム,ライクは任意の距離空間における任意の二つの核に対して地帯図の存在を示した.本稿では任意有限個の互に交らないコンパクトな核に対する地帯図の存在と唯一とを,任意次元のユークリッド空間において,またより一般に滑らか且つ膨らかなる有限次元ノルム空間において示す.本稿の証明は浅野らのものよりも一般に成立つのみならず単純でもある.ノルムが膨らかであるが滑らかでない場合に地帯図が唯一にならない例をも挙げる. |
| 抄録(英) | Zone diagram is a variation on the classical concept of a Voronoi diagram. Given n sites in a metric space that compete for territory, the zone diagram is an equilibrium state in the competition. Formally it is defined as a fixed point of a certain "dominance" map. Asano, Matousek, and Tokuyama proved the existence and uniqueness of a zone diagram for point sites in Euclidean plane, and Reem and Reich showed existence for two arbitrary sites in an arbitrary metric space. We establish existence and uniqueness for n disjoint compact sites in a Euclidean space of arbitrary (finite) dimension, and more generally, in a finite-dimensional normed space with a smooth and rotund norm. The proof is considerably simpler than that of Asano et al. We also provide an example of non-uniqueness for a norm that is rotund but not smooth. Finally, we prove existence and uniqueness for two point sites in the plane with a smooth (but not necessarily rotund norm. |
| キーワード(和) | タルスキの不動点定理 / 地帯図 |
| キーワード(英) | Tarski fixed point theorem / zone diagrams |
| 資料番号 | COMP2009-42 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2010/1/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ユークリッド空間及びノルム空間における地帯図 |
| サブタイトル（和） | |
| タイトル（英） | Zone Diagrams in Euclidean Spaces and in Other Normed Spaces |
| サブタイトル（和） | |
| キーワード(1)（和/英） | タルスキの不動点定理 / Tarski fixed point theorem |
| キーワード(2)（和/英） | 地帯図 / zone diagrams |
| 第 1 著者 氏名（和/英） | 河村 彰星 / Akitoshi Kawamura |
| 第 1 著者 所属（和/英） | トロント大学計算機科学科 Department of Computer Science, University of Toronto |
| 第 2 著者 氏名（和/英） | 徳山 豪 / Takeshi Tokuyama |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 3 著者 氏名（和/英） | マトウシェク イルジ / Jiri Matousek |
| 第 3 著者 所属（和/英） | プラハ・カレル大学応用数学科・理論計算機科学科:スイス聯邦工科大学チューリヒ校理論計算機科学科 Department of Applied Mathematics and Institute of Theoretical Computer Science, Charles University:Institute of Theoretical Computer Science, ETH Zurich |
| 発表年月日 | 2010-01-25 |
| 資料番号 | COMP2009-42 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 391 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |