抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
明度およびスパース性は,ユークリッド(1+ε)スパンナーに対する2つの自然パラメータである。古典的結果は,次元d_∈Nと|≦0が一定であるとき,d空間におけるn点のあらゆる集合Sが,O(n)エッジを有する(1+ε)-スパンナーを,定数d→∞Nに対するΔλ_0への依存性に関するS.Tight限界のユークリッドMSTのそれに比例する重みが,最近だけ確立されたことを示した。LeとSolomon(FOCS 2019)はSteiner点が(1+ε)-スパンナーの明度およびスパース性を大幅に改善できることを示した。それらは,すべてのd≧1のd空間における最小スパース性に対して,次元d≧3,およびO(ε ̄-(d-1))/2)の最小明度に対して,O(ε ̄-(d+1)/2)の上限を与えた。それらは平面(d=2)でのみ下限を得た。また,LeとSolomon(ESA2020)は,平面における明度O(ε ̄-1logΔ)のSteiner(1+ε)-スパンナーを構築し,そこでは,π ̄*(√n)は,一対の点の間の最大と最小距離の間の比として定義した。本研究では,ユークリッドSteiner(1+ε)-スパンナーの明度およびスパース性に関するいくつかの限界を改善した。新しい幾何学的解析を用いて,著者らは,すべてのd≧2のユークリッドd空間におけるそのようなスパンナーのスパース性のために,明度およびΩ(ε ̄-(d-1)/2)に対するΩ(ε ̄-d/2)の下限を確立した。ユークリッド平面におけるn点に対する明度O(ε ̄-1logn)のSteiner(1+ε)-スパンナーを構築するために,この下限解析から幾何学的洞察を用いた。【JST・京大機械翻訳】