Loading article…
計算幾何学において、べき乗図はラゲール・ボロノイ図、ディリクレ・セル複体、ラディカル・ボロノイ分割、またはディリクレ・セル分割とも呼ばれ、ユークリッド平面を円の集合から定義される多角形セルに分割したものである。与えられた円Cのセルは、 Cまでのべき乗距離が他の円までのべき乗距離よりも小さいすべての点から構成される。べき乗図は一般化されたボロノイ図の一種であり、すべての円の半径が等しい場合の円中心のボロノイ図と一致する。[1] [2] [3] [4]
意味
Cが円でP がC の外側の点である場合、Cに関するPのべき乗は、 PからCと接する点Tまでの線分の長さの2乗です。同様に、P が円の中心からd の距離にあり、円の半径がrである場合、（ピタゴラスの定理により）べき乗はd 2 − r 2です。同じ式d 2 − r 2は、 Cの内側か外側かに関係なく、平面内のすべての点に拡張できます。つまり、C上の点はべき乗がゼロで、 C の内側の点はべき乗が負です。[2] [3] [4]
n個の円の集合C iのべき乗図は、平面をn 個の領域R i (セルと呼ばれる) に分割したもので、円C iがPのべき乗を最小化する円であるときはいつでも、点P はR iに属する。[2] [3] [4]
n = 2の場合 、べき乗図は 2 つの半平面で構成され、 2 つの円の根軸または弦と呼ばれる線で区切られます。根軸に沿って、両方の円のべき乗は等しくなります。より一般的には、どのべき乗図でも、各セルR iは凸多角形、つまり円C iの根軸で囲まれた半空間と他の円の交差です。セルの 3 つ組は図の頂点で交わり、頂点はセルが頂点で交わる 3 つの円の根軸中心です。[2] [3] [4]
関連する構造
べき乗図は、点群のボロノイ図の重み付け形式と見ることができる。点群は平面をセルに分割したもので、そのセル内の 1 つのサイトが他のすべてのサイトよりも近い。重み付けボロノイ図の他の形式には、加重ボロノイ図 (各サイトの距離に重みが加算されてから他のサイトとの距離と比較する) や乗重ボロノイ図 (サイトの重みが距離に乗算されてから他のサイトとの距離と比較する) がある。これとは対照的に、べき乗図では、各円の中心をサイトと見なし、各円の半径の 2 乗を重み (ユークリッド距離の 2 乗から減算されてから他の距離の 2 乗と比較する) と見ることができる。すべての円の半径が等しい場合、この減算は比較に何の違いも生じず、べき乗図はボロノイ図と一致する。[3] [4]
平面べき乗図は、重み付けされていない3次元ボロノイ図の平面断面として解釈することもできます。この解釈では、断面平面の円の中心の集合は、3次元ボロノイサイトの垂直投影であり、各円の2乗半径は、定数Kから断面平面からの対応するサイトまでの距離の2乗を引いた値であり、Kはこれらの半径がすべて正になるように十分に大きい値に選択されます。[5]
ボロノイ図と同様に、べき乗図は任意の次元のユークリッド空間に一般化できます。d次元のn個の球のべき乗図は、 d + 1次元のn個の上向き半空間の集合の交差と組み合わせ的に同等であり 、その逆も同様です。[3]
アルゴリズムとアプリケーション
2次元のべき乗図は、O( nlogn ) の 時間で実行されるアルゴリズムによって構築できる。[2] [3]より一般的には、高次元の半空間交差との等価性のため、d次元のべき乗図（d >2の場合）は、時間で実行されるアルゴリズムによって構築できる。[3]
べき乗図は、球体の和集合の体積を計算する効率的なアルゴリズムの一部として使用できます。各球体をべき乗図のセルと交差させることで、その球体の和集合全体への寄与がわかり、そこからべき乗図の複雑さに比例した時間で体積を計算できます。[6]
べき乗図の他の応用としては、点が円の和集合に属するかどうかをテストするためのデータ構造[2]、円の和集合の境界を構築するためのアルゴリズム[2]、および球の集合内で最も近い2つの球を見つけるためのアルゴリズム[ 7]などがあります。また、半離散最適輸送問題[8]を解くためにも使用され、初期宇宙の再構築[9]や流体力学[10]など、数多くの応用があります。
歴史
Aurenhammer (1987) は、べき乗距離の定義を 19 世紀の数学者Edmond LaguerreとGeorgy Voronoyの研究に遡らせています。[3] Fejes Tóth (1977) はべき乗図を定義し、それを使用して、 n 個の円板の結合の境界は常に最大 2 n個の点光源で照らされることができることを示しました。[11]べき乗図は、文献では「ラゲール-ボロノイ図」、「ディリクレ セル コンプレックス」、「ラジカル ボロノイ分割」、「セクション ディリクレ分割」などの別名で登場しています。[12]
参考文献
- ^ Linhart、J. (1981)、「Dirichletsche Zellencomplexe mit maximaler Ekenzahl」、Geometriae Dedicata、11 (3): 363–367、doi :10.1007/BF00149360、MR 0627538、S2CID 120072781。
- ^ abcdefg 今井宏;伊里、正夫。室田一雄 (1985)、「ラゲール幾何学におけるボロノイ図とその応用」、SIAM Journal on Computing、14 (1): 93–105、doi :10.1137/0214006、MR 0774929。
- ^ abcdefghi Aurenhammer, F. (1987)、「電力図：特性、アルゴリズム、アプリケーション」、SIAM Journal on Computing、16 (1): 78–96、doi :10.1137/0216006、MR 0873251。
- ^ abcde Edelsbrunner, Herbert (1987)、「13.6 べき乗図」、組み合わせ幾何学におけるアルゴリズム、EATCS理論計算機科学モノグラフ、第10巻、Springer-Verlag、pp. 327–328。
- ^ アッシュ、ピーター F. Bolker、Ethan D. (1986)、「Generalized Dirichlet tessellations」、Geometriae Dedicata、20 (2): 209–243、doi :10.1007/BF00164401、MR 0833848、S2CID 120383767。
- ^ Avis, David ; Bhattacharya, Binay K.; Imai, Hiroshi (1988)、「球の和集合の体積の計算」(PDF)、The Visual Computer、3 (6): 323–328、doi : 10.1007/BF01901190。
- ^ Guibas, Leonidas ; Zhang, Li (1998)、「ユークリッド近接図とべき乗図」、第 10 回カナダ計算幾何学会議。
- ^ Aurenhammer, F.; Hoffmann, F.; Aronov, B. (1998年1月). 「ミンコフスキー型定理と最小二乗クラスタリング」. Algorithmica . 20 (1): 61–76. doi :10.1007/PL00009187. ISSN 0178-4617. S2CID 5409198.
- ^ Levy, Bruno; Mohayaee, Roya; von Hausegger, Sebastian (2021-07-13). 「初期宇宙のユニークな再構築のための高速半離散最適輸送アルゴリズム」. Monthly Notices of the Royal Astronomical Society . 506 (1): 1165–1185. arXiv : 2012.09074 . doi : 10.1093/mnras/stab1676 . ISSN 0035-8711.
- ^ Lévy, Bruno (2022年2月). 「自由境界を持つ定体積ラグランジアンメッシュの部分最適輸送」. Journal of Computational Physics . 451 : 110838. arXiv : 2106.03936 . Bibcode :2022JCoPh.45110838L. doi :10.1016/j.jcp.2021.110838. S2CID 235406800.
- ^ Fejes Tóth、L. (1977)、「凸面ディスクの照明」、Acta Mathematica Academiae Scientiarum Hungaricae、29 (3–4): 355–360、doi :10.1007/BF01895856、MR 0464065、S2CID 122510545。
- ^ Aurenhammer, F.; Imai, H. (1988)、「ボロノイ図間の幾何学的関係」、Geometriae Dedicata、27 (1): 65–75、doi :10.1007/BF00181613、MR 0950323。