Colored intersection searching via sparse rectangular matrix multiplication

ABSTRACT

In a Batched Colored Intersection Searching Problem (CI), one is given a set of n geometric objects (of a certain class). Each object is colored by one of c colors, and the goal is to report all pairs of colors (c₁,c₂) such that there are two objects, one colored c₁ and one colored c₂, that intersect each other. We also consider the bipartite version of the problem, where we are interested in intersections between objects of one class with objects of another class (e.g., points and halfspaces).In a Sparse Rectangular Matrix Multiplication Problem (SRMM), one is given an n₁×n₂ matrix A and an n₂×n₃ matrix B, each containing at most m non-zero entries, and the goal is to compute their product AB.In this paper we present a technique for solving CI problems over a wide range of classes of geometric objects. The basic idea is first to use some decomposition method, such as geometric cuttings, to represent the intersection graph of the objects as a union of bi-cliques. Then, in each of these bi-cliques, contract all vertices of the same color. Finally, use an algorithm for sparse matrix multiplication (adapted from Yuster and Zwick [20]) to compute the union of the bi-cliques. We apply the technique to segments in R¹, to segments in R², to points and halfplanes in R², and, more generally, to points and halfspaces in R^d, for any fixed d. However, the technique extends to colored intersection searching in any class (or pair of classes) of geometric objects of constant descriptive complexity.In particular, using our technique we obtain an algorithm that reports all the pairs of intersecting colors for n points and n halfplanes in R², that are colored by c colors, in O(n^4/3c^0.46) time when n ≥ c^1.44, and in O(n^1.04c^0.9 + c²) time when n≤c^1.44.The algorithms that we give for CI use the algorithm for SRMM as a black box, which means that any improved algorithm for SRMM immediately leads to an improved algorithm for all colored intersection problems that our method applies to. We also show that the complexity of computing all intersecting colors in a set of segments on the real line is identical, up to a polylogarithmic multiplicative factor, to the complexity of SRMM with the appropriate parameters.

REFERENCES

• 1: Pankaj K. Agarwal , Sergey Bereg , Ovidiu Daescu , Haim Kaplan , Simeon Ntafos , Binhai Zhu, Guarding a terrain by two watchtowers, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064145]
• 2: Boaz Ben-Moshe , Paz Carmi , Matthew J. Katz, Computing all large sums-of-pairs in Rⁿ and the discrete planar two-watchtower problem, Information Processing Letters, v.89 n.3, p.137-139, 14 February 2004 [doi>10.1016/j.ipl.2003.07.008]
• 3: P. Bozanis, N. Kitsios, C. Makris, and A. K. Tsakalidis. Red-blue intersection reporting for objects of non-constant size. Comput. J., 39(6):541--546, 1996.
• 4: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993
• 5: B. Chazelle. Handbook of Data Structures and Applications, chapter 25, Cuttings, pages 25.1--25.10. CRC Press, 2005.
• 6: Henry Cohn , Robert Kleinberg , Balazs Szegedy , Christopher Umans, Group-theoretic Algorithms for Matrix Multiplication, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.379-388, October 23-25, 2005 [doi>10.1109/SFCS.2005.39]
• 7: Henry Cohn , Christopher Umans, A Group-Theoretic Approach to Fast Matrix Multiplication, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.438, October 11-14, 2003
• 8: Don Coppersmith, Rectangular matrix multiplication revisited, Journal of Complexity, v.13 n.1, p.42-49, March 1997 [doi>10.1006/jcom.1997.0438 ]
• 9: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 10: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 11: J. Erickson. New lower bounds for hopcroft's problem. Discrete and Computational Geometry, 16(4):389--418, 1996.
• 12: P. Gupta, R. Janardan, and M. Smid. Handbook of Data Structures and Applications, chapter 64, Computational geometry: generalized intersection searching, pages 64.1--64.17. {CRC Press, 2005.
• 13: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476 ]
• 14: Erich Kaltofen, An output-sensitive variant of the baby steps/giant steps determinant algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.138-144, July 07-10, 2002, Lille, France [doi>10.1145/780506.780524]
• 15: Dieter Kratsch , Jeremy Spinrad, Between O(nm) and O(n^α), Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 16: Lillian Lee, Fast context-free grammar parsing requires fast boolean matrix multiplication, Journal of the ACM (JACM), v.49 n.1, p.1-15, January 2002 [doi>10.1145/505241.505242]
• 17: Patrick Bouthemy , Edouard François, Motion segmentation and qualitative dynamic scene analysis from an image sequence, International Journal of Computer Vision, v.10 n.2, p.157-182, April 1993 [doi>10.1007/BF01420735]
• 18: Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning functions of k relevant variables, Journal of Computer and System Sciences, v.69 n.3, p.421-434, November 2004 [doi>10.1016/j.jcss.2004.04.002]
• 19: V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354--356, 1969.
• 20: R. Yuster and U. Zwick. Fast sparse matrix multiplication. In Proc. Europ. Sympos. Algorithms (ESA), pages 604--615, 2004.
• 21: Raphael Yuster , Uri Zwick, Answering distance queries in directed graphs using fast matrix multiplication, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.389-396, October 23-25, 2005 [doi>10.1109/SFCS.2005.20]

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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations

General Terms:
Algorithms, Theory

Keywords:
colored intersection searching, generalized intersection searching, matrix multiplication, range searching