@inproceedings{eme-ber-sag-09-aa-cyldec,
  author = {Emeliyanenko, Pavel and Berberich, Eric and Sagraloff, Michael},
  title = {Visualizing Arcs of Implicit Algebraic Curves, Exactly and Fast},
  booktitle = {Proceedings of the },
  booktitle = {Selected papers from the 5th International Symposium on Visual Computing (ISVC)},
  howpublished = {Online document.},
  location = {Las Vegas, US},
  series = {Lecture Notes in Computer Science},
  pages = {608–619},
  year = 2009,
  month = dec,
  doi = {10.1007/978-3-642-10331-5_57},
  comment = {The problem is identifying the individual arcs of algebraic implicit curves on the plane and approximating each arc by a polylines with a prescribed Hausdorff error. The arcs are identified by computing a cylindrical algebraic decomposition.  Subdivides the plane into boxes until the arc(s) appear to be $x$-monotonic in each box. FInds a point on each arc and then follows the arc by continuation.  Uses AA (called ``advanced IA'') for testing boxes.  Shits to improved AA bounds (``quadratic forms'' QF and ``modified AA'' MAA) when simple AA has problems.  Uses a single new noise for each internal variable for all approx and rounding errors.  Notes that one can evaluate the derivative of $f$ to decide whether $f(x)$ is monotonic in an interval, in which case the exact IA range is trivially computed.  Claims that the arcs are rendered precisely even if they pass arbitrarily close to each other.},
  abstract = {Given a Cylindrical Algebraic Decomposition [2] of an implicitly defined algebraic curve, visualizing distinct curve arcs is not as easy as it stands because, despite the absence of singularities in the interior, the arcs can pass arbitrary close to each other. We present an algorithm to visualize distinct arcs of algebraic curves efficiently and precise (at a given resolution), irrespective of how close to each other they actually pass. Our hybrid method inherits the ideas of subdivision and curve-tracking methods. With an adaptive mixed-precision model we can render the majority of curves using machine arithmetic without sacrificing the exactness of the final result. The correctness and applicability of our algorithm is borne out by the success of our web-demo presented in [11].}
}