Separators for sphere-packings and nearest neighbor graphs

ABSTRACT

A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system &Ggr;, there is a sphere S that intersects at most O(k1/dn1−1/d) balls of &Ggr; and divides the remainder of &Ggr; into two parts: those in the interior and those in the exterior of the sphere S, respectively, so that the larger part contains at most (1−1/(d+2))n balls. This bound of (O(k1/dn1−1/d) is the best possible in both n and k. We also present a simple randomized algorithm to find such a sphere in O(n) time. Our result implies that every k-nearest neighbor graphs of n points in d dimensions has a separator of size O(k1/dn1−1/d). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space.

REFERENCES

• 1: N. Alon , P. Seymour , R. Thomas, A separator theorem for graphs with an excluded minor and its applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.293-299, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100254]
• 2: ANDREEV, E.M. 1970a. On convex polyhedra in Lobacevskii space. Math. USSR Sbornik 10, 3, 413-440.
• 3: ANDREEV, E.M. 1970b. On convex polyhedra of finite volume in Lobacevskii space. Math. USSR Sbornik, 12, 2, 270-259.
• 4: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 5: CLARKSON, K. 1983. Fast algorithm for the all-nearest-neighbors problem. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 226-232.
• 6: K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161004]
• 7: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: DANZER, L., FONLUPT, J., AND KLEE, V. 1963. Helly's theorem and its relatives. In Proceedings of Symposia in Pure Mathematics, vol. 7. American Mathematical Society, 7:101-180.
• 10: Hubert de Fraysseix , János Pach , Richard Pollack, Small sets supporting fary embeddings of planar graphs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.426-433, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62254]
• 11: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 12: EPPSTEIN, D., AND ERICKSON, J. 1994. Iterated nearest neighbors and finding minimal polytopes. Disc. Comput. Geometry, 11, (3), 321-350.
• 13: David Eppstein , Gary L. Miller , Shang-Hua Teng, A deterministic linear time algorithm for geometric separators and its applications, Proceedings of the ninth annual symposium on Computational geometry, p.99-108, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161005]
• 14: F#.RY, I. 1948. On straight line representing of planar graphs. Acta. Sci. Math. 24, 229-233.
• 15: Alan M. Frieze , Gary L. Miller , Shang-Hua Teng, Separator based parallel divide and conquer in computational geometry, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.420-429, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141934]
• 16: John R. Gilbert , Gary L. Miller , Shang-Hua Teng, Geometric Mesh Partitioning: Implementation and Experiments, SIAM Journal on Scientific Computing, v.19 n.6, p.2091-2110, Nov. 1998 [doi>10.1137/S1064827594275339]
• 17: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 18: GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.
• 19: GUIBAS, L., PACH, J., AND SHARIR, M. 1994. Sphere-of-influence graphs in higher dimensions. In Intuitive Geometry, K. Boroczky and G. Fejes Toth, eds. Colloquia Mathematica Societatis J. Bolyai, vol. 63. North-Holland, Amsterdam, The Netherlands, pp. 131-137.
• 20: HAUSSLER, D., AND WELZL, E. 1987. e-net and simplex range queries. Disc. Comput. Geometry 2, 127-151.
• 21: JORDAN, C. 1869. Sur les assemblages de lignes. J. Reine Angew. Math. 70, 185-190.
• 22: KABATIANSKY, G. A., AND LEVENSHTEIN, V.I. 1978. Bounds for packings on a sphere and in space. Prob. Per. Info. 14, 1, 3-25.
• 23: KOEBE, P. 1936. Kontaktprobleme der konformen Abbildung. Ber. Verh. Sdchs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse 88, 141-164.
• 24: LEIGHTON, F.T. 1983. Complexity Issues in VLSI. Foundations of Computing. MIT Press, Cambridge, Mass.
• 25: Charles Eric Leiserson, Area-Efficient VLSI Computation, MIT Press, Cambridge, MA, 1997
• 26: LINIAL, N., LONDON, E., AND RABINOVICH, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215-245.
• 27: LIPTON, R. J., AND TARJAN, R.E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, (Apr.), 177-189.
• 28: LIPTON, R. J., ROSE, D. J., AND TARJAN, R. E. 1979. Generalized nested dissection. SIAM J. Numer. Anal. 16, 346-358.
• 29: Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
• 30: MILLER, G. L., TENG, S.-H., THURSTON, W., AND VAVASIS, S.A. 1993. Automatic mesh partitioning. In Sparse Matrix Computations: Graph Theory Issues and Algorithms, A. George, J. Gilbert, and J. Liu, eds. IMA Volumes in Mathematics and Its Applications. Springer-Verlag, New York.
• 31: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
• 32: G. L. Miller , W. Thurston, Separators in two and three dimensions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.300-309, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100255]
• 33: Gary L. Miller , Stephen A. Vavasis, Density graphs and separators, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.331-336, January 28-30, 1991, San Francisco, California, United States
• 34: MOHAR, B. 1993. A polynomial time circle packing algorithm. Disc. Comput. Geom. 241-250.
• 35: PACH, J., AND AGARWAL, P. 1995. Combinatorial Geometry. Wiley-Interscience, New York.
• 36: Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
• 37: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 38: SOMMERVILLE, D. M.Y. 1958. An Introduction to the Geometry of n Dimensions. Dover, New York.
• 39: Daniel A. Spielman , Shang-Hua Teng, Disk packings and planar separators, Proceedings of the twelfth annual symposium on Computational geometry, p.349-358, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237404]
• 40: Daniel A. Spielman , Shang Teng, Spectral Partitioning Works: Planar Graphs and Finite Element Meshes, University of California at Berkeley, Berkeley, CA, 1996
• 41: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 42: TENG, S.-H. 1994. Combinatorial aspects of geometric graphs. MIT Tech. Rep. TR-612. May. In Lecture Notes in Computer Science. Springer-Verlag, New York.
• 43: THOMASSEN, C. 1980. Planarity and duality of finite and infinite graphs. J. Combin. Theory, Series B 29, 244-271.
• 44: TOUSSAINT, G. 1988. A graph-theoretical primal sketch. In Computational Morphology, G. Toussaint, ed., Elsevier-North Holland, Amsterdam, The Netherlands, pp. 229-260.
• 45: THURSTON, W.P. 1988. The geometry and topology of 3-manifolds. Princeton University Notes, Princeton, N.J.
• 46: TUTTE, W.T. 1960. Convex representations of graphs. Proc. London Math. Soc. 10, 3, 304-320.
• 47: TUTTE, W.T. 1963. How to draw a graph. Proc. London Math. Soc. 13, 3, 743-768.
• 48: UNGAR, P. 1951. A theorem on planar graphs. J. London Math Soc. 26, 256-262.
• 49: VALIANT, L. G. 1981. Universality consideration in VLSI circuits. IEEE Trans. Comput. 30, 2 (Feb.). 135-140.
• 50: VAPNIK V, N. AND CHERVONENKIS, A. YA. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory Prob. Appl. 16, 264-280.
• 51: Stephen A. Vavasis, Automatic domain partitioning in three dimensions, SIAM Journal on Scientific and Statistical Computing, v.12 n.4, p.950-970, July 1991 [doi>10.1137/0912051]
• 52: WYNER, A. D. 1965. Capabilities of bounded discrepancy decoding. Bell System Tech. J. 44, 1061-1122.
• 53: ZIEGLER, G.M. 1988.Lectures on polytopes. In Graduate Texts in Mathematics, vol. 152. Springer- Verlag, New York.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Theory

Keywords:
centerpoint, computational geometry, graph algorithms, graph separators, partitioning, point location, probabilistic method, rndomized algorithm, sphere-preserving mapping