Detection is easier than computation (Extended Abstract)

ABSTRACT

Perhaps the most important application of computer geometry involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation where the objects are given as input and their intersection is returned as output. However, for many applications, we may assume that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. For this problem, none of the previous lower bounds are valid and we propose algorithms requiring sublinear time for their solution in 2 and 3 dimensions.

REFERENCES

• 1: Bentley, J. and Ottmann,Th., Algorithms for reporting and counting geometric intersections, Carnegie-Mellon University, August 1978.
• 2: Forrest, A.R., Private communication to David Dobkin, March 29, 1979.
• 3: Kiefer, J., Sequential Minimax Search for a Maximum, Proc. Amer. Math. Soc. 4 (1953), 502–506.
• 4: Muller, D. and Preparata, F., Finding the intersection of 2 convex polyhedra, Tech. Report Univ. of Illinois, Urbana, Ill., Oct. 1977.
• 5: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 6: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 7: Shamos, M. and Hoey, D., Geometric Intersection Problems, Proc. of the 17th Annual Symp. on Found. of Comp. Sci. (1976), 208–215.
• 8: Tomlin, D., private communication to David Dobkin.

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.1 Models of Computation

General Terms:
Algorithms, Theory