Exact Computation of Arrangements of Rotated Conics
Eric Berberich, Manuel Caroli, Nicola Wolpert · Max Planck Institute for Plasma Physics · 2007
Transformations of geometric objects, like translation and rotation, are fundamental operations in CAD-systems. Rotations trigger the need to deal with trigonometric functions, which is hard to achieve when aiming for exact and robust implementation. We show how we efficiently compute the planar arrangement of conics rotated by angles that can be constructed with straightedge and compass. Well-known examples are multiples of $45{^{\circ}}$, $30{^{\circ}}$, and $15{^{\circ}}$. The main problem one has to solve is root-isolation of univariate polynomials $p(x)\in \mathbb{Q}(\sqrt{c_1})\ldots(\sqrt{c_d})[x]$, for which we use a modified version of the Descartes method. For $d=1$, %In the case $p(x)\in \mathbb{Q}(\sqrt{c})[x]$ we additionally present a new method that isolates the real roots of $p$ by using root isolation for polynomials $q(x)\in\mathbb{Q}[x]$ only. We show results of our benchmark experiences comparing both methods.