{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T03:49:36Z","timestamp":1794023376550,"version":"4.8.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1991,9]]},"DOI":"10.1007\/bf02574697","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T10:31:20Z","timestamp":1174559480000},"page":"385-406","source":"Crossref","is-referenced-by-count":67,"title":["Cutting hyperplane arrangements"],"prefix":"10.1007","volume":"6","author":[{"given":"Ji\u0159i","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,6,26]]},"reference":[{"key":"BF02574697_CR1","doi-asserted-by":"crossref","unstructured":"[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\u2013210, 1990.","DOI":"10.1145\/98524.98567"},{"key":"BF02574697_CR2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"[A1] P. K. Agarwal. Partitioning arrangments of lines, I: An efficient deterministic algorithm.Discrete & Computational Geometry,5:449\u2013483, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02574697_CR3","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF02187809","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"[A2] P. K. Agarwal. Partitioning arrangements of lines, II: Applications.Discrete & Computational Geometry,5: 533\u2013573, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02574697_CR4","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1983","unstructured":"[AHU] A. V. Aho, J. E. Hopcroft, and J. D. Ulman.The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1983."},{"key":"BF02574697_CR5","doi-asserted-by":"crossref","unstructured":"[AHWW] N. Alon, D. Haussler, E. Welzl, and G. W\u00f6ginger. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. InProc. 3rd ACM Symposium on Computational Geometry, pages 331\u2013340, 1987.","DOI":"10.1145\/41958.41994"},{"key":"BF02574697_CR6","doi-asserted-by":"crossref","unstructured":"[BR] B. Berger and J. Rompel. Simulating (logn) c -wise independence in NC. InProc. 30th IEEE Symposium on Foundations of Computer Science, pages 2\u20137, 1989.","DOI":"10.1109\/SFCS.1989.63447"},{"key":"BF02574697_CR7","doi-asserted-by":"crossref","unstructured":"[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\u201359, 1989.","DOI":"10.1109\/SFCS.1989.63455"},{"key":"BF02574697_CR8","doi-asserted-by":"crossref","unstructured":"[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\u2013392, 1989.","DOI":"10.1145\/73007.73044"},{"key":"BF02574697_CR9","doi-asserted-by":"crossref","unstructured":"[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\u2013192, 1989.","DOI":"10.1007\/BFb0035760"},{"key":"BF02574697_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"[CF] B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry.Combinotorica,10: 229\u2013249, 1990.","journal-title":"Combinotorica"},{"key":"BF02574697_CR11","doi-asserted-by":"crossref","unstructured":"[C1] K. L. Clarkson. Applications of random sampling in computational geometry, II. InProc. 4th ACM Symposium on Computational Geometry, pages 1\u201311, 1988.","DOI":"10.1145\/73393.73394"},{"key":"BF02574697_CR12","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. L. Clarkson","year":"1988","unstructured":"[C2] K. L. Clarkson. A randomized algorithm for closest-point queries.SIAM Journal on Computing,17: 830\u2013847, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"BF02574697_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"[E] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987."},{"key":"BF02574697_CR14","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF02187742","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"[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\u2013466, 1989.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02574697_CR15","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H. Edelsbrunner","year":"1990","unstructured":"[EM] H. Edelsbrunner and P. M\u00fccke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Transactions on Computer Graphics,9: 66\u2013104, 1990.","journal-title":"ACM Transactions on Computer Graphics"},{"key":"BF02574697_CR16","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"[EOS] H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of hyperplanes with applications.SIAM Journal on Computing,15: 341\u2013363, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"BF02574697_CR17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"[HW] D. Haussler and E. Welzl. \u03b5-nets and simplex range queries.Discrete & Computational Geometry,2: 127\u2013151, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02574697_CR18","series-title":"KAM Series (technical report)","first-page":"59","volume-title":"Approximate half-planar range counting","author":"J. Matou\u0161ek","year":"1987","unstructured":"[M1] J. Matou\u0161ek. Approximate half-planar range counting. KAM Series (technical report) 59\u201387, Charles University, Prague, 1987. A revised version (Approximate levels in line arrangements) inSIAM Journal on Computing,20(2):222\u2013227, 1991."},{"key":"BF02574697_CR19","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF02187804","volume":"5","author":"J. Matou\u0161ek","year":"1990","unstructured":"[M2] J. Matou\u0161ek. Construction of \u03b5-nets.Discrete & Computational Geometry,5: 427\u2013448, 1990.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02574697_CR20","unstructured":"[M3] J. Matou\u0161ek. More on cutting arrangements and spanning trees with low crossing number. Tech. Report B-90-2. FB Mathematik. FU Berlin, 1990."},{"key":"BF02574697_CR21","doi-asserted-by":"crossref","unstructured":"[M4] J. Matou\u0161ek. Approximations and optimal geometric divide-and-conquer. InProc. 23rd ACM Symposium on Theory of Computing, pages 506\u2013511, 1991.","DOI":"10.1145\/103418.103470"},{"key":"BF02574697_CR22","doi-asserted-by":"crossref","unstructured":"[M5] J. Matou\u0161ek. Efficient partition trees. InProc. 7th ACM Symposium on Computational Geometry, pages 1\u20139, 1991.","DOI":"10.1145\/109648.109649"},{"key":"BF02574697_CR23","doi-asserted-by":"crossref","unstructured":"[PW] J. Pach and G. W\u00f6ginger. Some new bounds for epsilon-nets. InProc. 6th ACM Symposium on Computational Geometry, pages 10\u201315, 1990.","DOI":"10.1145\/98524.98529"},{"key":"BF02574697_CR24","doi-asserted-by":"crossref","unstructured":"[R] P. Raghavan. Probabilitic construction of deterministic algorithms: approximating packing integer programs. InProc. 27th IEEE Symposium on Foundations of Computer Science, pages 10\u201318, 1986.","DOI":"10.1109\/SFCS.1986.45"},{"key":"BF02574697_CR25","volume-title":"Ten Lectures on the Probabilistic Method","author":"R. Spencer","year":"1987","unstructured":"[S] R. Spencer.Ten Lectures on the Probabilistic Method. CBMS-NSF, SIAM, Philadelphia, PA, 1987."},{"key":"BF02574697_CR26","doi-asserted-by":"crossref","unstructured":"[SWM] R. Seidel, E. Welzl, and J. Matou\u0161ek. Netting a lot with a little: Small \u03b5-nets for disks and half-spaces. InProc. 6th ACM Symposium on Computational Geometry, pages 16\u201322, 1990.","DOI":"10.1145\/98524.98530"},{"key":"BF02574697_CR27","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"[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\u2013280, 1971.","journal-title":"Theory of Probability and Its Application"},{"key":"BF02574697_CR28","doi-asserted-by":"crossref","unstructured":"[YY] F. F. Yao and A. C. Yao. A general approach to geometric queries. InProc. 17th ACM Symposium on Theory of Computing, pages 163\u2013168, 1985.","DOI":"10.1145\/22145.22163"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574697.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574697\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574697","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T23:46:55Z","timestamp":1736898415000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574697"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF02574697"],"URL":"https:\/\/doi.org\/10.1007\/bf02574697","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}