Geometric complexity

ABSTRACT

The complexity of a number of fundamental problems in computational geometry is examined and a number of new fast algorithms are presented and analyzed. General methods for obtaining results in geometric complexity are given and upper and lower bounds are obtained for problems involving sets of points, lines, and polygons in the plane. An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.

REFERENCES

• 1: Über Tschebyschefsche Annäherungsmethoden. Math. Ann. 57 (1903) pp. 509-540.
• 2: R. Duda and P. Hart. Pattern Classification and Scene Analysis. Wiley, 1973. p. 378.
• 3: M. Shamos. On computing the area of a plane polygon. Submitted for publication.
• 4: R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Info. Proc. Lett. 1(1972) pp.132-133.
• 5: The proof of this theorem was suggested by Daniel J. Hoey.
• 6: Yaglom and Boltyanskii. Convex Figures. Holt, Rinehart, and Winston, 1961.
• 7: Michael Ian Shamos, Computational geometry., 1978
• 8: M. Gemignani. On Finite Subsets of the Plane and Simple Closed Polygonal Paths. Math. Mag. Jan.- Feb. 1966. pp.38-41.
• 9: The kernel algorithm is due to Stanley C. Eisenstat.
• 10: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 11: After G. Voronoi. Consult C.A.Rogers, Packing and Covering. Cambridge University Press, 1964.
• 12: M. Shamos and D. Hoey. Closest-point Problems. In preparation.
• 13: This is an application of a technique of Dobkin and Lipton, Sixth SIGACT Symposium.
• 14: This method of attack was suggested by David Dobkin.
• 15: B. Dasarathy and L. White. Some maximin and pattern classifier problems: theory and algorithms. Talk presented at the Computer Science Conference, February, 1975.
• 16: For a lucid discussion of the power of geometric construction tools, see H. Eves, A survey of geometry, Allyn and Bacon, 1972.
• 17: Lemoine, Géométrographie, 1907.
• 18: D. Hilbert. Foundations of Geometry, 1899. Edited and reprinted by Open Court, 1971.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory