Publication Date

2017-12-20

Availability

Open access

Embargo Period

2017-12-20

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science (Arts and Sciences)

Date of Defense

2017-11-15

First Committee Member

Victor J Milenkovic

Second Committee Member

Hüseyin Koçak

Third Committee Member

Elisha Sacks

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.

Keywords

computational geometry; arrangements; algebraic curves; algorithms; intersections; polynomial systems

Share

COinS