{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T03:34:49Z","timestamp":1772508889382,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1990,10,1]],"date-time":"1990-10-01T00:00:00Z","timestamp":654739200000},"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":[[1990,10]]},"DOI":"10.1007\/bf02187804","type":"journal-article","created":{"date-parts":[[2005,9,20]],"date-time":"2005-09-20T18:17:21Z","timestamp":1127240241000},"page":"427-448","source":"Crossref","is-referenced-by-count":46,"title":["Construction of \u025b-nets"],"prefix":"10.1007","volume":"5","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1990,10,1]]},"reference":[{"key":"BF02187804_CR1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal: A deterministic algorithm for partitioning arrangements of lines and its applications,Proc. 5th Ann. ACM Symposium on Computational Geometry (1989), pp. 11\u201321 (full version to apear inDiscrete Comput. Geom.).","DOI":"10.1145\/73833.73835"},{"key":"BF02187804_CR2","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal: Ray shooting and other applications of spanning trees with low stabbing number,Proc. 5th Ann. ACM Symposium on Computational Geometry (1989), pp. 315\u2013325 (full version to appear inDiscrete Comput. Geom.).","DOI":"10.1145\/73833.73868"},{"key":"BF02187804_CR3","unstructured":"M. Ajtai, J. Koml\u00f3s, E. Szemer\u00e9di: AnO(n logn) sorting network,Proc. 15th ACM Symp. on Theory on Computing (1983), pp. 1\u20139."},{"key":"BF02187804_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle, J. Friedman: A deterministic view of random sampling and its use in geometry, Report CS-TR-181-88 (extended abstract inProc. 29th Ann. IEEE Symposium on Foundations of Computer Science (1988), pp. 539\u2013549).","DOI":"10.1109\/SFCS.1988.21970"},{"key":"BF02187804_CR5","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle, E. Welzl: Quasi-optimal range searching in spaces of finite VC-dimension,Discrete Comput. Geom. 4 (1989), 467\u2013490.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187804_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal: A greedy heuristics for the set-covering problem,Math. Oper. Res. 4 (1979), 233\u2013235.","journal-title":"Math. Oper. Res."},{"key":"BF02187804_CR7","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"K. Clarkson, P. Shor: Applications of random sampling in computational geometry, II,Discrete Comput. Geom. 4 (1989), 387\u2013421.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187804_CR8","doi-asserted-by":"crossref","unstructured":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl: Combinatorial complexity for arrangements of curves and surfaces,Proc. 29th Ann. IEEE Symposium on Foundations of Computer Science (1988), pp. 568\u2013579.","DOI":"10.1109\/SFCS.1988.21973"},{"key":"BF02187804_CR9","first-page":"200","volume":"31","author":"R. Cole","year":"1984","unstructured":"R. Cole: Slowing down sorting networks to obtain faster sorting algorithms,J. Assoc. Comput. Mach. 31 (1984), 200\u2013208.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02187804_CR10","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R. Cole","year":"1989","unstructured":"R. Cole, J. Salowe, W. L. Steiger, E. Szemer\u00e9di: An optimal-time algorithm for slope selection,SIAM J. Comput. 18 (1989), 792\u2013810.","journal-title":"SIAM J. Comput."},{"key":"BF02187804_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner:Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987."},{"key":"BF02187804_CR12","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF02187742","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner, L. Guibas, J. Herschberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl: Implicitly representing arrangements of lines or segments,Discrete Comput. Geom. 4 (1989), 433\u2013466.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187804_CR13","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, E. Welzl: Constructing belts in 2-dimensional arrangements,SIAM J. Comput. 15 (1986), 271\u2013284.","journal-title":"SIAM J. Comput."},{"key":"BF02187804_CR14","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey, D. S. Johnson;Computers and Intractability, Freeman, San Francisco, 1979."},{"key":"BF02187804_CR15","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler, E. Welzl:\u025b-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127\u2013151.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187804_CR16","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz: On the ratio of optimal integral and fractional cover,Discrete Math. 13 (1975), 383\u2013390.","journal-title":"Discrete Math."},{"key":"BF02187804_CR17","series-title":"KAM Series","volume-title":"Approximate Halfplanar Range Counting","author":"J. Matou\u0161ek","year":"1987","unstructured":"J. Matou\u0161ek:Approximate Halfplanar Range Counting, KAM Series 59-87, Charles University, Prague, 1987."},{"key":"BF02187804_CR18","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek: Cutting hyperplane arrangements, 6th ACM Symposium on Computational Geometry, 1990.","DOI":"10.1145\/98524.98528"},{"key":"BF02187804_CR19","unstructured":"J. Matou\u0161ek: Spanning trees with low crossing number, to appear inInform. Theoret. Applic."},{"key":"BF02187804_CR20","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo: Applying parallel computation algorithm in the design of serial algorithms,J. Assoc. Comput. Mach. 30 (1983), 852\u2013865.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02187804_CR21","doi-asserted-by":"crossref","unstructured":"J. Pach, W. Steiger, E. Szemer\u00e9di: An upper bound for the number of planark-sets,Proc. 30th Ann. IEEE Symposium on Foundations of Computer Science (1989), pp. 72\u201381.","DOI":"10.1109\/SFCS.1989.63458"},{"key":"BF02187804_CR22","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S. Suri","year":"1986","unstructured":"S. Suri: A linear algorithm for minimum link paths inside a simple polygon,Comput. Vision Graphics Image Process. 35 (1986), 99\u2013110.","journal-title":"Comput. Vision Graphics Image Process."},{"key":"BF02187804_CR23","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik, A. Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl. 16 (1971), 264\u2013280.","journal-title":"Theory Probab. Appl."},{"key":"BF02187804_CR24","doi-asserted-by":"crossref","unstructured":"E. Welzl: Partition trees for triangle counting and other range searching problems,Proc. 4th ACM Symposium on Computational Geometry (1988), pp. 23\u201333.","DOI":"10.1145\/73393.73397"},{"key":"BF02187804_CR25","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02187686","volume":"1","author":"E. Welzl","year":"1986","unstructured":"E. Welzl: More onk-sets of finite sets in the plane,Discrete Comput. Geom. 1 (1986), 95\u2013100.","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187804.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187804\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T17:54:58Z","timestamp":1586454898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,10]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1990,10]]}},"alternative-id":["BF02187804"],"URL":"https:\/\/doi.org\/10.1007\/bf02187804","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,10]]}}}