High-Level Filtering for Arrangements of Conic Arcs

$A(C)$ is the subdivision the set induces on the plane
into vertices, edges and faces. Many computational
geometry algorithms involve the construction and
maintenance of planar arrangements. A general, robust
arrangement software package for conic arcs covers
most practical cases of planar arrangement that appear
in literature. A common approach to implementing
robust geometric algorithms is to use an exact
algebraic number type --- yet this may lead to very
slow, inefficient programs. Furthermore, while the
computation of the primitives needed for the
construction of arrangements of conic arcs is a
well-defined problem with a closed-form solution, it
is impossible to fully apply it when using the
existing machinery for exact computation.

To overcome these obstacles, a simple technique for
filtering the computations involved in the arrangement
construction is suggested: when constructing an
arrangement vertex we keep track of the steps that
have led to it construction --- this history can be
used for answering predicates very efficiently,
compared to a naive exact implementation. The construction
history also allows us to calculate some arrangement
vertices exactly, while others are only approximately
computed. We can later refine the approximate
computations in cases of ambiguity using the
construction history of the relevant vertices. Since
such cases are relatively rare, the resulting
algorithm is both efficient and robust.