Computing convolutions by reciprocal search

ABSTRACT

In this paper we show how certain geometric convolution operations can be computed efficiently. Here “efficiently” means that our algorithms have running time proportional to the input size plus the output size. Our convolution algorithms rely on new optimal solutions for certain reciprocal search problems, such as finding intersections between “blue” and “green” intervals, and overlaying convex planar subdivisions.

REFERENCES

• 1: Bentley, J.L., and Ottmaan, T.A., Algorithm for r~porting and counting geometric intersections. IEEE Trans. Computers, C-28, 9, 1979, 643-647.
• 2: Chaze!le, B., Filtering search: a new approach to query-answering. SIAM J. on Computing, 1985.
• 3: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 4: Grfinbaum, B., Convex Polytopem. Interscience, 1967.
• 5: Guibas, L.J., Ramshaw, L., and $tolfi, J., A kinetic framework for computational geometry. Proc. 24th iEEE Syrup. FOCS, 1983, 100-111.
• 6: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 7: 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]
• 8: Spanier, E.,H., Algebraic Topology. Springer, 1966.

INDEX TERMS

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory, Verification