Computational geometry in a curved world

David P. Dobkin, Diane L. Souvaine

Research output: Contribution to journalArticle

31 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)421-457
Number of pages37
JournalAlgorithmica
Volume5
Issue number1
DOIs
StatePublished - Mar 1 1990

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Computational geometry
  • Convexity
  • Curve algorithm
  • Intersection
  • Kernel
  • Monotonicity
  • Splinegon
  • diameter decomposition

Fingerprint Dive into the research topics of 'Computational geometry in a curved world'. Together they form a unique fingerprint.

  • Cite this