Cutting dense point sets in half

ABSTRACT

A halving hyperplane of a set S of n points in Rd contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most &dgr;n1/d, &dgr; some constant. Such a set S is called dense. In d=2 dimensions, the number of halving lines for a dense set can be as much as &OHgr;(nlogn), and it cannot exceed O(n5/4/log*n). The upper bound improves over the current best bound of O(n3/2/log*n) which holds more generally without any density assumption. In d=3 dimensions we show that O(n7/3) is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to d≥4 dimensions, where it leads to O(nd−2/d) as an upper bound for the number of halving hyperplanes.

REFERENCES

• 1: R. Alexander. Geometric methods in the study of irregularities of distribution. Combinatorica 10 (1990), 115-136.
• 2: N. Alon , M. Katchalski , W. R. Pulleyblank, The maximum size of a convex polygon in a restricted set of points in the plane, Discrete & Computational Geometry, v.4 n.3, p.245-251, March 1989
• 3: N Alon , M A Perles, On the intersection of edges of a geometric graph by straight lines, Discrete Mathematics, 60, p.75-90, June/July 1986 [doi>10.1016/0012-365X(86)90004-X ]
• 4: 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
• 5: I. Bárány , Z. Füredi , L. Lovász, On the number of halving planes, Proceedings of the fifth annual symposium on Computational geometry, p.140-144, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73849]
• 6: Robert L. Cook, Stochastic sampling in computer graphics, ACM Transactions on Graphics (TOG), v.5 n.1, p.51-72, Jan. 1986 [doi>10.1145/7529.8927]
• 7: B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
• 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: Tamal K. Dey , Herbert Edelsbrunner, Counting triangle crossings and halving planes, Proceedings of the ninth annual symposium on Computational geometry, p.270-273, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161148]
• 10: D. Eppstein. Improved bounds for intersecting triangles and halving planes. Rept. 91-60, Dept. Comput. Sci., Univ. California at irvine, 1991.
• 11: H. Edelsbrunner and E. Welzl. On the number of line separations of a finite set in the plane. J. Combin. Theory, Set. A 38 (1985), 15-29.
• 12: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 13: P. Erd6s, L. Lovgsz, A. Simmons and E. G. Straus. Dissection graphs of planar point sets. In A Survey of Combinatorial Theory, ed. J. N. Srivastava et al., 139- 149, North-Holland, Amsterdam, 1973.
• 14: J. E. Goodman , R. Pollack , B. Sturmfels, Coordinate representation of order types requires exponential storage, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.405-410, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73046]
• 15: J. E. Goodman, R. Pollack and B. Sturmfels. The intrinsic spread of a configuration in ~d. j. Amer. Math. Soc. 3 (1990), 639-651.
• 16: L. Lov~sz. On the number of halving lines. Ann. Univ. Sci. Budapest EStvSs Sect. Math. 14 (1971), 107-108.
• 17: János Pach , William Steiger , Endre Szemerédi, An upper bound on the number of planar K-sets, Discrete & Computational Geometry, v.7 n.2, p.109-123, 1992
• 18: Edgar A. Ramos, The number of 3-sets of a finite point set in the plane, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 19: L. A. Santal6. Integral Geometry and Geometric Probabilit~t. Addison-Wesley, Reading, Mass., 1976.
• 20: Pavel Valtr, Convex independent sets and 7-holes in restricted planar point sets, Discrete & Computational Geometry, v.7 n.2, p.135-152, 1992
• 21: P. VMtr. Planar point sets with bounded ratios of distances. Ph.D. thesis, Fachbereich Math., Freie Univ. Berlin, 1994.
• 22: Rade T. Živaljevic , Sinša T. Vrecica, The colored Tverberg's problem and complexes of injective functions, Journal of Combinatorial Theory Series A, v.61 n.2, p.309-318, Nov. 1992 [doi>10.1016/0097-3165(92)90028-S]

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory, Verification