Cutting hyperplane arrangements

ABSTRACT

We will consider an arrangement H of n hyperplanes in Ed (where the dimension d is fixed). An &egr;-cutting for H will be a collection of (possibly unbounded) d-dimensional simplices with disjoint interiors, which cover all Ed and such that the interior of any simplex is intersected by at most &egr;n hyperplanes of H. We give a deterministic algorithm, finding a (1/r)-cutting with &Ogr;(rd(log r)C) simplices in time &Ogr;(n(log n)Ard-1 (log r)B) (A,B,C are constants dependent on dimension). In a similar time bound (with an additional &Ogr;(r&Ogr;(1)) overhead) we can also find a (1/r)-net for the range space (X, H(X)), where X is a n-point set in Ed and H(X) denotes the set of all subsets of X which can be cut by a halfspace. This (1/r)-net has size &Ogr;(r log r), which matches the best known existence result; in fact, the method gives a constructive existence proof. In the plane, we can obtain a (1/r)-cutting of optimal size &Ogr;(r2) in time &Ogr;(nr) (which is optimal if we want to compute also the collection of lines intersecting each simplex of the cutting). This improves the result of Agarwal, and our algorithm is conceptually simpler.

REFERENCES

• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• Aga: P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
• Aga1: P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proceedings of the fifth annual symposium on Computational geometry, p.315-325, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73868]
• CEG: B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
• CF: B.ChazeUe, J.Friedman: A deterministic view of random sampling and its use in geometry, Report CS-TR-181-88, extended abstract FOCS 1988, pp.539-549
• Cla: K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
• Cla1: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• C&al: K.Clarkson, H.Edelsbrunner, L.Guibas, M.Sharir, E.Welzh Combinatorial complexity for arrangements of curves and surfaces, FOCS 1988, pp. 568-579
• Ede: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• E&al: H. Edelsbrunner , L. Guibas , J. Hershberger , R. Seidel , M. Sharir , J. Snoeyink , E. Welzl, Implicitly representing arrangements of lines or segments, Discrete & Computational Geometry, v.4 n.5, p.433-466, 1989 [doi>10.1007/BF02187742]
• EOS: 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]
• HW: D.Haussler, E.Welzh e-nets and simplex range queries, Discr. & Comput. Geometry 2(1987) pp. 127-151
• Ma: J. Matoušek, Construction of epsilon nets, Proceedings of the fifth annual symposium on Computational geometry, p.1-10, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73834]
• Ma1: J.Matou~ek: Approximate halfplanar range counting, KAM Series 59-87, Charles University 1987
• PW: J.Pach, G. Woeginger: Some new bounds for epsilon-nets, Report B-89-08 Serie B - Informatik, FU Berlin 1989
• YY: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

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.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms