论文标题
3D Apollonius图的谓词
Predicates of the 3D Apollonius Diagram
论文作者
论文摘要
In this thesis we study one of the fundamental predicates required for the construction of the 3D Apollonius diagram (also known as the 3D Additively Weighted Voronoi diagram), namely the EDGECONFLICT predicate: given five sites $S_i, S_j,S_k,S_l,S_m$ that define an edge $e_{ijklm}$ in the 3D Apollonius diagram, and第六个查询站点$ s_q $，谓词确定$ e_ {ijklm} $的部分，该部分将由于插入$ s_q $而在六个站点的Apollonius图中消失。我们的重点是对谓词的算法分析，目的是最大程度地减少其代数程度。我们将主要谓词分解为子序列物，然后在其他原始操作的帮助下进行评估。我们表明，回答任何子示例物和原语所需的最高代数程度，因此，当三角甲构成hausdorff dimension 1时，我们的主要谓词在非分级配置中为10。 insphere谓词与否。我们使用的工具包括3D反转转换和所谓的定性符号扰动方案。我们的大多数分析都是在倒空间中进行的，这是我们的几何观察和分析以代数术语捕获的地方。
In this thesis we study one of the fundamental predicates required for the construction of the 3D Apollonius diagram (also known as the 3D Additively Weighted Voronoi diagram), namely the EDGECONFLICT predicate: given five sites $S_i, S_j,S_k,S_l,S_m$ that define an edge $e_{ijklm}$ in the 3D Apollonius diagram, and a sixth query site $S_q$, the predicate determines the portion of $e_{ijklm}$ that will disappear in the Apollonius diagram of the six sites due to the insertion of $S_q$. Our focus is on the algorithmic analysis of the predicate with the aim to minimize its algebraic degree. We decompose the main predicate into sub-predicates, which are then evaluated with the aid of additional primitive operations. We show that the maximum algebraic degree required to answer any of the sub-predicates and primitives, and, thus, our main predicate is 10 in non-degenerate configurations when the trisector is of Hausdorff dimension 1. We also prove that all subpredicates developed can be evaluated using 10 or 8-degree demanding operations for degenerate input for these trisector types, depending on whether they require the evaluation of an intermediate INSPHERE predicate or not. Among the tools we use is the 3D inversion transformation and the so-called qualitative symbolic perturbation scheme. Most of our analysis is carried out in the inverted space, which is where our geometric observations and analysis is captured in algebraic terms.
