Intersection of convex objects in two and three dimensions

ABSTRACT

One of the basic geometric operations involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation in which the objects are given as input and their intersection is returned as output. For many applications, however, it may be assumed 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 algorithms are proposed requiring sublinear time for their solution in two and three dimensions.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BENTLEY, J. L., AND OTTMANN, T. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28 (Sept. 1979), 643-647.
• 3: BENTLEY, j. L., AND SHAMOS, M.I. Divide and conquer for linear expected time. Inf. Proc. Lett. 7 (1978), 87-9 I.
• 4: BENTLEY, J. L., HAKEN, O., AND HON, R. Fast geometric algorithms for VLSI tasks. In Proceedings of the Computational Conference, 198 l, pp. 88-92.
• 5: DOBKIN, D. P., AND KIRKPATRICK, O.G. Fast detection of polyhedral intersection. Theor. Comput. Sci. 27 (1983), 241-253.
• 6: DOBKIN, D. P., AND LIPTON, R.L. Multidimensional searching problems. SIAM J. Comput. 5, 2{ (June 1976), 181-186.
• 7: DOBKIN, D. P., AND MUNRO, J.I. Efficient uses of the past. In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE, New York, 1980, pp. 200-206.
• 8: DOaKIN, D. P., AND TOMLIN, D. Cartographic modelling techniques in environmental planning: An efficient system design. Unpublished manuscript.
• 9: KIEFER, J. Sequential minimax search for a maximum. Proc. Am. Math. Soc. 4 (1953), 502-506.
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: MULLER, D. E., AND PREPARATA, F.P. Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7 (1978), 217-236.
• 12: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 13: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• 14: Joseph F. Traub, Algorithms and Complexity: New Directions and Recent Results, Academic Press, Inc., Orlando, FL, 1976
• 15: 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]
• 16: Michael Ian Shamos, Computational geometry., 1978
• 17: SHAMOS, M. l., AND HOLY, D. Geometric intersection problems. In Proceedings of the 17th Annual IEEE Symposium on Foundations of Computer Science (Houston, Tex., Oct). IEEE, New York, 1976, pp. 208-215.

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification