講演抄録/キーワード |
講演名 |
2010-01-25 11:30
ユークリッド空間及びノルム空間における地帯図 ○河村彰星(トロント大)・徳山 豪(東北大)・イルジ マトウシェク(カレル大/チューリヒ工科大) COMP2009-42 |
抄録 |
(和) |
地帯図はボロノイ図に似た概念であり,距離空間内の幾つかの集合(核と呼ぶ)が銘々に領土の拡大を図るときに達する平衡を表す.勢力域に関する距離の方程式を以て定義する.
浅野,マトウシェク,徳山はユークリッド平面において,核が点であるときに地帯図が唯一つ存在することを示した.レエム,ライクは任意の距離空間における任意の二つの核に対して地帯図の存在を示した.本稿では任意有限個の互に交らないコンパクトな核に対する地帯図の存在と唯一とを,任意次元のユークリッド空間において,またより一般に滑らかかつ膨らかなる有限次元ノルム空間において示す.本稿の証明は浅野らのものよりも一般に成立つのみならず単純でもある.ノルムが膨らかであるが滑らかでない場合に地帯図が唯一にならない例をも挙げる. |
(英) |
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 / / / / / / |
文献情報 |
信学技報, vol. 109, no. 391, COMP2009-42, pp. 23-28, 2010年1月. |
資料番号 |
COMP2009-42 |
発行日 |
2010-01-18 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-42 |