Abstract
We consider a collectionH ofn hyperplanes in Ed (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all Ed and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r d) simplices (which is asymptotically optimal). Forr≤n 1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn)O(1) r d−1). In the plane we achieve a time boundO(nr) forr≤n 1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm.
For ann point setX⊆Ed and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}),
In timeO(n(logn)O(1) r d−1+r O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry.
These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
[AESW] P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. InProc. 6th ACM Symposium on Computational Geometry, pages 203–210, 1990.
[A1] P. K. Agarwal. Partitioning arrangments of lines, I: An efficient deterministic algorithm.Discrete & Computational Geometry,5:449–483, 1990.
[A2] P. K. Agarwal. Partitioning arrangements of lines, II: Applications.Discrete & Computational Geometry,5: 533–573, 1990.
[AHU] A. V. Aho, J. E. Hopcroft, and J. D. Ulman.The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1983.
[AHWW] N. Alon, D. Haussler, E. Welzl, and G. Wöginger. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. InProc. 3rd ACM Symposium on Computational Geometry, pages 331–340, 1987.
[BR] B. Berger and J. Rompel. Simulating (logn)c-wise independence in NC. InProc. 30th IEEE Symposium on Foundations of Computer Science, pages 2–7, 1989.
[BRS] B. Berger, J. Rompel, and P. W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. InProc. 30th IEEE Symposium on Foundations of Computer Science, pages 54–59, 1989.
[CEG] B. Chazelle, H. Edelsbrunner, and L. Guibas. Lines in space: Combinatorics, algorithms and applications. InProc. 21st ACM Symposium on Theory of Computing, pages 389–392, 1989.
[CEGS] B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly-exponential stratification scheme for real semi-algebraic varieties and its applications. InProc. 16th International Colloquium on Automata, Languages and Programming, pages 179–192, 1989.
[CF] B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry.Combinotorica,10: 229–249, 1990.
[C1] K. L. Clarkson. Applications of random sampling in computational geometry, II. InProc. 4th ACM Symposium on Computational Geometry, pages 1–11, 1988.
[C2] K. L. Clarkson. A randomized algorithm for closest-point queries.SIAM Journal on Computing,17: 830–847, 1988.
[E] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987.
[EGH*] H. Edelsbrunner, L. Guibas, J. Herschberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl. Implicitly representing arrangements of lines or segments.Discrete & Computational Geometry,4: 433–466, 1989.
[EM] H. Edelsbrunner and P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Transactions on Computer Graphics,9: 66–104, 1990.
[EOS] H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of hyperplanes with applications.SIAM Journal on Computing,15: 341–363, 1986.
[HW] D. Haussler and E. Welzl. ε-nets and simplex range queries.Discrete & Computational Geometry,2: 127–151, 1987.
[M1] J. Matoušek. Approximate half-planar range counting. KAM Series (technical report) 59–87, Charles University, Prague, 1987. A revised version (Approximate levels in line arrangements) inSIAM Journal on Computing,20(2):222–227, 1991.
[M2] J. Matoušek. Construction of ε-nets.Discrete & Computational Geometry,5: 427–448, 1990.
[M3] J. Matoušek. More on cutting arrangements and spanning trees with low crossing number. Tech. Report B-90-2. FB Mathematik. FU Berlin, 1990.
[M4] J. Matoušek. Approximations and optimal geometric divide-and-conquer. InProc. 23rd ACM Symposium on Theory of Computing, pages 506–511, 1991.
[M5] J. Matoušek. Efficient partition trees. InProc. 7th ACM Symposium on Computational Geometry, pages 1–9, 1991.
[PW] J. Pach and G. Wöginger. Some new bounds for epsilon-nets. InProc. 6th ACM Symposium on Computational Geometry, pages 10–15, 1990.
[R] P. Raghavan. Probabilitic construction of deterministic algorithms: approximating packing integer programs. InProc. 27th IEEE Symposium on Foundations of Computer Science, pages 10–18, 1986.
[S] R. Spencer.Ten Lectures on the Probabilistic Method. CBMS-NSF, SIAM, Philadelphia, PA, 1987.
[SWM] R. Seidel, E. Welzl, and J. Matoušek. Netting a lot with a little: Small ε-nets for disks and half-spaces. InProc. 6th ACM Symposium on Computational Geometry, pages 16–22, 1990.
[VC] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability and Its Application,16: 264–280, 1971.
[YY] F. F. Yao and A. C. Yao. A general approach to geometric queries. InProc. 17th ACM Symposium on Theory of Computing, pages 163–168, 1985.
Author information
Authors and Affiliations
Additional information
A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.
Rights and permissions
About this article
Cite this article
Matoušek, J. Cutting hyperplane arrangements. Discrete Comput Geom 6, 385–406 (1991). https://doi.org/10.1007/BF02574697
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574697