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 members of a set of primitive procedures on individual curved edges. These techniques also apply 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.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics
- Computational geometry
- Curve algorithm
- diameter decomposition