抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
半代数的範囲探索問題において,著者らは,一定複雑性半代数集合のファミリーからの任意のクエリ範囲のために,R ̄ds.t.におけるnポイントを前処理し,範囲を横断するすべてのポイントを,効率的に報告または計数することができた。範囲がシンプリスから成るとき,S(n)空間を用いて問題を解決でき,S(n)Q ̄d(n)=O(n ̄d)によるQ(n)クエリ時間を用いて,このトレードオフは,ほとんど緊密であった。結果的に,O(n ̄1-1/d)クエリー時間とO(n ̄d)空間をO(log ̄dn)クエリー時間を使用する高速クエリ構造でO(n)空間を使用する低空間構造が存在する。しかし,一般的な半代数的範囲に対しては,低空間解のみが知られているが,最良解はシンプレックスクエリと同じトレードオフ曲線に整合する。同一が高速クエリケースに対して行うことができるが,この未解決問題は未解決のままであることが推測された。ここでは,この予想を修正した。半胴体範囲探索と関連問題に対する最初の非自明な下限を与えた。Q(n)クエリ時間を持つ2つの同心円の間の点を報告するための任意のデータ構造は,Q(n)=O(log ̄O(1)n),Ω(n ̄3-o(1))空間を用いて,S(n)=Ω(n ̄3-o(1)/Q(n) ̄5)空間を使用しなければならないことを示した。また,a_0,a_Δがクエリ時間で与えられるY=Σ_i=0 ̄Δa_iX ̄iの2つの多項式の間の点を報告する問題を研究した。S(n)=Ω(n ̄Δ+1-o(1)/Q(n) ̄Δ ̄2+Δ)を示した。Q(n)=O(log ̄O(1)n)に対しては,Ω(n ̄Δ+1-o(1))空間を用いる必要がある。二重半代数スタビング問題に対して,線形空間において,2Dリングスタビングを解決する任意のデータ構造は,Ω(n ̄2/3)クエリ時間を用いる必要があることを示した。これは線形化上限とほぼ一致した。一般的な半代数スラブスタビング問題に対して,再び,ほとんど厳密な下限を示した。【JST・京大機械翻訳】
