2018/11/15 by Manos Kamarianakis, Manos N. Kamarianakis, Kamarianakis, Manos N. · 1 citation
Computer Science · Mathematics · #65D99 (Primary) 68W30 #68Q25 (Secondary) #68U05 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #cs.CG #msc:65D99 #msc:68Q25 #msc:68U05 #msc:68W30
paper · pdf · doi:10.48550/arxiv.1811.06504
A simpler version of this paper was accepted at "The Sixth International Conference on Analytic Number Theory and Spatial Tessellations" held in Kyiv, Ukraine at September 2018
openalex publication_date 2018/11/15 · arxiv created 2018/11/16 · arxiv updated 2018/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper 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 Si, Sj,Sk,Sl,Sm that define an edge eijklm in the 3D Apollonius diagram, and a sixth query site Sq, the predicate determines the portion of eijklm that will disappear in the Apollonius diagram of the six sites due to the insertion of Sq. Our focus is on the algorithmic analysis of the predicate with the aim to minimize its algebraic degree. We decompose the main predicate into three sub-predicates, which are then evaluated with the aid of four 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. Among the tools we use is the 3D inversion transformation. In the scope of this paper and due to space limitations, only non-degenerate configurations are considered, i.e. different Voronoi vertices are distinct and the predicates never return a degenerate answer. Most of our analysis is carried out in the inverted space, which is where our geometric observations and analysis is captured in algebraic terms.