Degeneracy control in geometric programs

Degenerate geometric data (e.g., three points on a line, four points on a circle) is known to create all sorts of special cases, some easy and some complicated, that have to be considered in implementations of geometric algorithms. Traditionally, the designers of algorithms coped with these difficulties by assuming special cases away, and left it to the unfortunate implementer to deal with data that would not satisfy the assumption.This thesis discusses several issues related to the phenomenon of degeneracy itself, and a symbolic perturbation scheme that allows programs to work on degenerate data as if it were nondegenerate. The topics covered are the likelihood of a special case, the computational overhead induced by the symbolic perturbation scheme and ways to reduce it, examples of applications, extensions and modifications of the scheme.U of I OnlyETDs are only available to UIUC Users without author permissio