Computational Geometry in a Curved World (thesis)
Report ID: TR-094-87Author: Souvaine, Diane L.
Date: 1986-10-00
Pages: 67
Download Formats: |PDF|
Abstract:
Computational geometry as a field deals with the algorithmic aspects of all geometric problems. But the majority of the results obtained heretofore have been focused on objects defined with straight lines and flat faces, in part because a computational geometry of curved objects seemed significantly more complex. The major result of this dissertation is to show that curved objects can indeed be processed efficiently. We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, the splinegon and the splinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexity O(f(n)), the comparable splinegon algorithm has time complexity at worst O(Kf(n)) where K represents a constant number of calls to a series of primitive procedures on individual curved edges. These techniques apply also to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others. (Note: thesis copy is two pages per sheet.)