Abstract
<p>An algorithm and implementation is given for constructing the arrangement of<br />
algebraic surfaces in a bounding box. The input is a bounding box B and a set F of<br />
trivariate polynomials with floating point (double precision) coefficients. The arrange-<br />
ment is a subdivision of B into connected sets of dimension 0 (vertices), 1 (edges),<br />
2 (facets), and 3 (cells) induced by the algebraic surfaces f (x, y, z) = 0, f ∈ F. A<br />
k-dimensional set is a maximal connected subset of B, intersected by 3 − k surfaces<br />
in F. The input is required to be generic (in general position), and so the intersec-<br />
tion of k > 3 surfaces is empty. Non generic input is handled by perturbation. The<br />
incidence graph is also determined. All components are split into simply connected<br />
subsets: loop edges are split into two or more segment edges and facets are split<br />
to eliminate holes and handles. Hence, the semi-algebraic sets and their connected<br />
subsets defined by the polynomials in B are determined. The resulting arrangement<br />
data structure provides traversal and point location. The method uses a combination<br />
of numerical (binary space partition, interval arithmetic, extended precision float-<br />
ing point, curve tracing) and algebraic (Descartes’ rule of signs and Morse theory)<br />
methods to compute the arrangement while ensuring that its combinatorial structure<br />
is correct. The computational bottleneck, finding all zeros of three polynomials, is<br />
sped up through a GPU subroutine that prunes away large subsets guaranteed not tocontain zeros.<br />
Like other subdivision approaches, it avoids computing complex zeros<br />
or zeros outside the box.</p>