Gary L. Miller
Skip Abstract Section
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 Γ, there is a sphere S that intersects at most O(k1/dn1−1/d) balls of Γ and divides the remainder of Γ 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.
- ALON, N., SEYMOUR, P., AND THOMAS, R. 1990. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing (Baltimore, Md., May 14-16). ACM, New York, pp. 293-299.]] Google Scholar
Digital Library
- ANDREEV, E.M. 1970a. On convex polyhedra in Lobacevskii space. Math. USSR Sbornik 10, 3, 413-440.]]Google ScholarCross Ref
- ANDREEV, E.M. 1970b. On convex polyhedra of finite volume in Lobacevskii space. Math. USSR Sbornik, 12, 2, 270-259.]]Google ScholarCross Ref
- BENTLEY, J.L. 1980. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (Apr.), 214-229.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- CLARKSON, K., EPPSTEIN, D., MILLER, G., STURTIVANT, C., AND TENG, S.-H. 1993. Approximating center points with iterated radon points. In Proceedings of 9th Annual ACM Symposium on Computational Geometry (San Diego, Calif., May 19-21). ACM, New York, pp. 91-98.]] Google ScholarDigital Library
- CONWAY, J. H., AND SLOANE, N. J.A. 1988. Sphere Packings, Lattices and Groups. Springer-Verlag, New York.]] Google ScholarDigital Library
- CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R.L. 1990. Introduction to Algorithms. MIT Press, Cambridge, Mass.]] Google ScholarDigital Library
- 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.]]Google Scholar
- DE FRAYSSEIX, H., PACH, J., AND POLLACK, R. 1988. Small sets supporting F#ry embeddings of planar graphs. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, pp. 426-433.]] Google ScholarDigital Library
- EDELSBRUNNER, H. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag, New York.]] Google ScholarDigital Library
- EPPSTEIN, D., AND ERICKSON, J. 1994. Iterated nearest neighbors and finding minimal polytopes. Disc. Comput. Geometry, 11, (3), 321-350.]]Google ScholarDigital Library
- EPPSTEIN, D., MILLER, G. L., AND TENG, S.-H. 1993. A deterministic linear time algorithm for geometric separators and its applications. In Proceedings of 9th Annual ACM Symposium on Computational Geometry (San Diego, Calif., May 19-21). ACM, New York, pp. 99-108.]] Google ScholarDigital Library
- F#.RY, I. 1948. On straight line representing of planar graphs. Acta. Sci. Math. 24, 229-233.]]Google Scholar
- FRIEZE, A., MILLER, G., AND TENG, S.-H. 1992. Separator-based parallel divide and conquer in computational geometry. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (San Diego, Calif., June 29-July 1). ACM, New York, pp. 422-430.]] Google ScholarDigital Library
- GILBERT, J. R., MILLER, G. L., AND TENG, S.-H. 1997. Geometric mesh partitioning: Implementation and experiments. SIAM J. Sci. Comput., to appear.]] Google ScholarDigital Library
- GILBERT, J. R., HUTCHINSON, J. P., AND TARJAN, R.E. 1984. A separation theorem for graphs of bounded genus. J. Algorithms 5, 391-407.]] Google ScholarDigital Library
- GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.]]Google Scholar
- 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.]]Google Scholar
- HAUSSLER, D., AND WELZL, E. 1987. e-net and simplex range queries. Disc. Comput. Geometry 2, 127-151.]]Google ScholarDigital Library
- JORDAN, C. 1869. Sur les assemblages de lignes. J. Reine Angew. Math. 70, 185-190.]]Google ScholarCross Ref
- KABATIANSKY, G. A., AND LEVENSHTEIN, V.I. 1978. Bounds for packings on a sphere and in space. Prob. Per. Info. 14, 1, 3-25.]]Google Scholar
- KOEBE, P. 1936. Kontaktprobleme der konformen Abbildung. Ber. Verh. Sdchs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse 88, 141-164.]]Google Scholar
- LEIGHTON, F.T. 1983. Complexity Issues in VLSI. Foundations of Computing. MIT Press, Cambridge, Mass.]]Google Scholar
- LEISERSON, C.E. 1983. Area-Efficient VLSI Computation. Foundations of Computing. MIT Press, Cambridge, Mass.]] Google ScholarDigital Library
- LINIAL, N., LONDON, E., AND RABINOVICH, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215-245.]]Google ScholarCross Ref
- LIPTON, R. J., AND TARJAN, R.E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, (Apr.), 177-189.]]Google ScholarCross Ref
- LIPTON, R. J., ROSE, D. J., AND TARJAN, R. E. 1979. Generalized nested dissection. SIAM J. Numer. Anal. 16, 346-358.]]Google ScholarDigital Library
- MILLER, G. L., TENG, S.-H., AND VAVASIS, S.A. 1991. An unified geometric approach to graph separators. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 538-547.]] Google ScholarDigital Library
- 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.]]Google Scholar
- MILLER, G. L., TENG, S.-H., THURSTON, W., AND VAVASIS, S.A. 1997. Geometric separators for finite element meshes. SIAM J. Sci. Comput., to appear.]] Google ScholarDigital Library
- MILLER, G. L., AND THURSTON, W. 1990. Separators in two and three dimensions. In Proceedings of the 22th Annual ACM Symposium on Theory of Computing, (Baltimore, Md., May 14-16). ACM, New York, pp. 300-309.]] Google ScholarDigital Library
- MILLER, G. L., AND VAVASIS, S.A. 1991. Density graphs and separators. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan. 28-30). ACM, New York, pp. 331-336.]] Google ScholarDigital Library
- MOHAR, B. 1993. A polynomial time circle packing algorithm. Disc. Comput. Geom. 241-250.]] Google ScholarDigital Library
- PACH, J., AND AGARWAL, P. 1995. Combinatorial Geometry. Wiley-Interscience, New York.]]Google Scholar
- PLOTKIN, S., RAO, S., AND SMITH, W. D. 1994. Shallow excluded minors and improved graph decomposition. In Proceedings at the 5th Symposium Discrete Algorithms. SIAM, New York, pp. 462-470.]] Google ScholarDigital Library
- PREPARATA, F. P., AND SHAMOS, M.I. 1985. Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer-Verlag, New York.]] Google ScholarDigital Library
- SOMMERVILLE, D. M.Y. 1958. An Introduction to the Geometry of n Dimensions. Dover, New York.]]Google Scholar
- SPIELMAN, D. A., AND TENG, S.-H. 1996a. Disk packings and planar separators. In Proceedings of 12th Annual ACM Symposium on Computational Geometry (Philadelphia, Pa., May 24-26). ACM, New York, pp. 349-359.]] Google ScholarDigital Library
- SPIELMAN, D. A., AND TENG, S.-H. 1996b. Spectral partitioning works: planar graphs and finite element meshes. UCB//CSD-96-898, U.C. Berkeley, Berkeley, California.]] Google ScholarDigital Library
- TENG, S.-H. 1991. Points, Spheres, and Separators: A unified geometric approach to graph partitioning. Ph.D. dissertation. CMU-CS-91-184. School of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa.]] Google ScholarDigital Library
- 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.]]Google Scholar
- THOMASSEN, C. 1980. Planarity and duality of finite and infinite graphs. J. Combin. Theory, Series B 29, 244-271.]]Google ScholarCross Ref
- TOUSSAINT, G. 1988. A graph-theoretical primal sketch. In Computational Morphology, G. Toussaint, ed., Elsevier-North Holland, Amsterdam, The Netherlands, pp. 229-260.]]Google Scholar
- THURSTON, W.P. 1988. The geometry and topology of 3-manifolds. Princeton University Notes, Princeton, N.J.]]Google Scholar
- TUTTE, W.T. 1960. Convex representations of graphs. Proc. London Math. Soc. 10, 3, 304-320.]]Google ScholarCross Ref
- TUTTE, W.T. 1963. How to draw a graph. Proc. London Math. Soc. 13, 3, 743-768.]]Google ScholarCross Ref
- UNGAR, P. 1951. A theorem on planar graphs. J. London Math Soc. 26, 256-262.]]Google ScholarCross Ref
- VALIANT, L. G. 1981. Universality consideration in VLSI circuits. IEEE Trans. Comput. 30, 2 (Feb.). 135-140.]]Google Scholar
- 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.]]Google ScholarCross Ref
- VAVASIS, S. A. 1991. Automatic domain partitioning in three dimensions. SIAM J. Sci. Stat. Comput. 12, 950-970.]]Google ScholarDigital Library
- WYNER, A. D. 1965. Capabilities of bounded discrepancy decoding. Bell System Tech. J. 44, 1061-1122.]]Google ScholarCross Ref
- ZIEGLER, G.M. 1988.Lectures on polytopes. In Graduate Texts in Mathematics, vol. 152. Springer- Verlag, New York.]]Google Scholar
Index Terms
- Separators for sphere-packings and nearest neighbor graphs
Recommendations
Graph layouts via layered separators
A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets such that no two edges that are in the same set are nested with respect to the vertex ordering. A k-track layout of a graph consists of a ...
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingIn this paper, we address two longstanding questions about finding good separators in graphs of bounded genus and degree: 1. It is a classical result of Gilbert, Hutchinson, and Tarjan [12] that one can find asymptotically optimal separators on these ...
I/O-Efficient Planar Separators
We present I/O-efficient algorithms for computing optimal separator partitions of planar graphs. Our main result shows that, given a planar graph $G$ with $N$ vertices and an integer $r > 0$, a vertex separator of size O$(N / \sqrt{r})$ that partitions $...
Comments