This paper presents a unified representation scheme for the implicit equations of points, lines, and circles. An associated set of geometric algorithms operates successfully on degenerate and nearly degenerate geometry, and when necessary produces degenerate geometric results. Computation errors are interpreted geometrically in order to establish preconditions for reliable results and requirements on the resolution of computer arithmetic. The algorithms thus provide a basis for the wide range of geometric constructions required by computer-aided drafting and design systems.

An algorithm is described for the decomposition of a bounded concave region of E2 space into a settheoretic combination of convex regions.This algorithm finds the convex hull of the region and then recurses to find the convex hulls of the difference between the original region and its convex hull, until such regions are convex.It exhibits a linear-time complexity for regions whose difference with their convex hull consists of only convex inner regions, a quadratic worst-case complexity, and an average complexity a little worse than linear.