Abstract
One of the fundamental concepts in computational geometry is deducing the combinatorial structure, or interactions, of a group of static geometric objects. In two dimensions, the objects in question include, but are not limited to: points, lines, line segments, polygons, and non-linear curves. There are various properties of interest describing a collection of such objects; examples include: distances, adjacencies, and most notably, intersections of these objects. Well studied, robust, and highly efficient algorithms exist for linear geometry and parametric curves. Problems involving non-linear, implicit, and high-dimensional objects however are an active area of research. Algebraic curves and algebraic surfaces arise frequently in numerous applications: GIS software, CAD software, VLSI design, computational chemistry and biology, dynamics, and robotics. We present a novel algorithm for finding all intersections of two semi-algebraic curves in a convex polygonal region and describe its prospective analog in 3 dimensions. We "encase'' the curves in the convex region by repeatedly splitting the region until each cell contains at most two intersecting segments, thus detecting and isolating all of the intersections. The advantage of using encasement is that the running time is proportional to the size of the convex region when it is small and yet comparable to existing techniques when it is large.