Ham-sandwich cuts in Rd

ABSTRACT

Lo and Steiger resolved the complexity question for computing a planar ham-sandwich cut by giving an optimal linear-time algorithm. We show how to generalize the ideas to every fixed dimension d > 2 by describing an algorithm that computes a ham-sandwich cut in Rd in time O(nd–1–a(d)), for some a(d) > 0 (going to zero as d increases). For d = 3,4, the running time is almost proportional to ed–1(n;n/2), where dd(k;n) denotes the maximal number of k-sets over sets of n points in Rd, and with the current best bounds, we get O(n3/2 log2 n/log n) running time for d = 3 and O(n8/3+&egr;) for d=4. We also give a linear time algorithm for three dimensional ham-sandwich cuts when the three sets are suitably separated.

REFERENCES

• 1: P. Agarwal and J. Matougek. Dynamic half-space range reporting and its applications. Manuscript, 1991.
• 2: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 3: J. Akiyama and N. Alon. Disjoint Simplices and Geometric Hypergraphs. Annals of the New York Academy of Sciences, vo1555, 1-3, 1989.
• 4: N. Alon, I. B#ny, Z. FiireAi, and D. Kleitman. Point selections and weak e-nets for convex hulls. Manuscript, 1991.
• 5: Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991 [doi>10.1007/BF02574700]
• 6: M. Atallah. A Matching Problem in the Plane. J. Comp. Syst. Sciences 3, 63-70, 1985.
• 7: Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989 [doi>10.1137/0218055]
• 8: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: H. Edelsbrunner , R. Waupotitsch, Computing a ham-sandwich cut in two dimensions, Journal of Symbolic Computation, v.2 n.2, p.171-178, June 1986 [doi>10.1006/jsco.1998.0247]
• 11: H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
• 12: H. Edelsbnmner and E. Welzl. Constructing Belts in Two-Dimensional Arrangements with Applications. SIAM J. Computing 15, 271-284, 1986.
• 13: Chi-Yuan Lo and W.L. Steiger. An Optimal Time Algorithm for Ham-Sandwich Cuts in the Plane. Proc. Second Canad. Conf. on Computational Geom., 5-9, 1990.
• 14: Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
• 15: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• 16: N. Megiddo. Partitioning with Two Lines in the Plane. J. Algorithms 6, 430-433, 1985.
• 17: J. Path, W. Steiger, and E. Szemer#i. An Upper Bound on the Number of Planar k-Sets. Proc. 30th IEEE Symposium on Foundations of Computer Science, 72-79, 1989.
• 18: D. Willard. Polygon Retrieval. SIAM j. Comp. 11,149-165, 1982.
• 19: R.T. #.ivaljevi6 and S.T. Vredica. The Colored Tverberg Problem and Complexes of Injective Functions. To appear, 1991.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory