We present an extension of snap roundingfrom straight-line segments (see Guibas and Marimont, 1998)to Bézier curves of arbitrary degree, and thus the first method for geometric roundingof curvilinear arrangements.Our algorithm takes a set of intersecting Bézier curvesand directly computes a geometric rounding of their true arrangement, without the need of representing the true arrangement exactly.The algorithm's output is a deformation of the true arrangementthat has all Bézier control points at integer pointsand comes with the same geometric guarantees as instraight-line snap rounding: during rounding, objects do not movefurther than the radius of a pixel, and features of thearrangement may collapse but do not invert.

An algorithm is presented for the geometric analysis of an algebraic curve f(x, y) = 0 in the real affine plane. It computes a cylindrical algebraic decomposition (CAD) of the plane, augmented with adjacency information. The adjacency information describes the curve's topology by a topologically equivalent planar graph. The numerical data in the CAD gives an embedding of the graph.

We give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials A(X) = Εni=0 aiXi with integer coefficients |ai| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(logn), and we use it to derive the best known bit complexity bound for the integer case.

The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quarter million of segmentsin the final arrangement.