Computing Topological Transition Sets for Line-Line-Circle Trisectors in $R^3$
This work addresses the problem of efficiently constructing mixed-object Voronoi diagrams in computational geometry, representing an incremental advancement beyond quadric-only methods.
The paper tackles the challenge of computing Voronoi diagrams for mixed geometric objects in 3D by developing an exact verification framework to characterize parameter space connectivity, specifically analyzing the trisector of two skew lines and one circle, and identifies bifurcation values at k=0 and k=1 as topological transition walls.
Computing the Voronoi diagram of mixed geometric objects in $R^3$ is challenging due to the high cost of exact geometric predicates via Cylindrical Algebraic Decomposition (CAD). We propose an efficient exact verification framework that characterizes the parameter space connectivity by computing certified topological transition sets. We analyze the fundamental non-quadric case: the trisector of two skew lines and one circle in $R^3$. Since the bisectors of circles and lines are not quadric surfaces, the pencil-of-quadrics analysis previously used for the trisectors of three lines is no longer applicable. Our pipeline uses exact symbolic evaluations to identify transition walls. Jacobian computations certify the absence of affine singularities, while projective closure shows singular behavior is isolated at a single point at infinity, $p_{\infty}$. Tangent-cone analysis at $p_{\infty}$ yields a discriminant $Î_Q = 4ks^2(k-1)$, identifying $k=0,1$ as bifurcation values. Using directional blow-up coordinates, we rigorously verify that the trisector's real topology remains locally constant between these walls. Finally, we certify that $k=0,1$ are actual topological walls exhibiting reducible splitting. This work provides the exact predicates required for constructing mixed-object Voronoi diagrams beyond the quadric-only regime.