講演名 2010-01-25
距離等分の存在
今井 桂子, 河村 彰星, 徳山 豪, マトウシェク イルジ, レエム ダニエル,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 距離空間内の空でない二集合P,Qから等距離にある点の全体をP,Q間の距離二等分という.列 C_1,…,C_であって各C_iがC_とC_との距離二等分であるもの(但しC_0=P,C_k=Qと考える)をP,Q間の距離k等分という.この概念は回路設計についての村田の問をもとに浅野,マトウシェク,徳山が導入し,PとQとがユークリッド平面内の点でありkが3であるときに限りその存在と唯一とを既に示した.本稿ではより一般に固有測地空間内の空でなく交らない二閉集合間に距離k等分が存在することを示す(一意性は不明).証明においては,二集合間のk階層という概念を定義し,その存在をタルスキ不動点定理によって示す.これはレエム,ライクが似た問題に対して用いた手法である.
抄録(英) The bisector of two nonempty sets P and Q in R^d is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k〓2 is an integer, is a (k-1)-tuple (C_1,C_2,...,C_) such that C_i is the bisector of C_ and C_ for every i=1,2,...,k-1, where C_0= P and C_k=Q. This notion, for the case where P and Q are points in R^2, was introduced by Asano, Matousek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance trisector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any (finite) dimension (uniqueness remains open), or more generally, in proper geodesic spaces. The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski fixed point theorem, by a method introduced by Reem and Reich for a slightly different purpose.
キーワード(和) 距離等分 / タルスキの不動点定理
キーワード(英) distance k-sectors / Tarski fixed point theorem
資料番号 COMP2009-41
発行日

研究会情報
研究会 COMP
開催期間 2010/1/18(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Theoretical Foundations of Computing (COMP)
本文の言語 JPN
タイトル(和) 距離等分の存在
サブタイトル(和)
タイトル(英) Distance k-Sectors Exist
サブタイトル(和)
キーワード(1)(和/英) 距離等分 / distance k-sectors
キーワード(2)(和/英) タルスキの不動点定理 / Tarski fixed point theorem
第 1 著者 氏名(和/英) 今井 桂子 / Keiko Imai
第 1 著者 所属(和/英) 中央大学理工学部情報工学科
Department of Information and System Engineering, Chuo University
第 2 著者 氏名(和/英) 河村 彰星 / Akitoshi Kawamura
第 2 著者 所属(和/英) トロント大学計算機科学科
Department of Computer Science, University of Toronto
第 3 著者 氏名(和/英) 徳山 豪 / Takeshi Tokuyama
第 3 著者 所属(和/英) 東北大学大学院情報科学研究科
Graduate School of Information Sciences, Tohoku University
第 4 著者 氏名(和/英) マトウシェク イルジ / Jiri Matousek
第 4 著者 所属(和/英) プラハ・カレル大学応用数学科
Department of Applied Mathematics, Charles University
第 5 著者 氏名(和/英) レエム ダニエル / Daniel Reem
第 5 著者 所属(和/英) イスラエル工科大学数学科
athematics, The Technion-Israel Institute of Technology
発表年月日 2010-01-25
資料番号 COMP2009-41
巻番号(vol) vol.109
号番号(no) 391
ページ範囲 pp.-
ページ数 6
発行日