{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T13:51:31Z","timestamp":1781531491622,"version":"3.54.5"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,4,1]],"date-time":"1995-04-01T00:00:00Z","timestamp":796694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,4]]},"DOI":"10.1007\/bf01293483","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T03:39:41Z","timestamp":1111721981000},"page":"325-345","source":"Crossref","is-referenced-by-count":66,"title":["Dynamic half-space range reporting and its applications"],"prefix":"10.1007","volume":"13","author":[{"given":"P. K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Matou\u0161ek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01293483_CR1","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"P. K. Agarwal","year":"1991","unstructured":"P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs.Discrete & Computational Geometry,6 (1991), 407\u2013422.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR2","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, D. Eppstein, and J. Matou\u0161ek. Dynamic half-space reporting, proximity problems, and geometric minimum spanning trees.Proc. 33rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 80\u201389.","DOI":"10.1109\/SFCS.1992.267816"},{"key":"BF01293483_CR3","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal and J. Matousek. Ray shooting and parametric search.SIAM Journal on Computing,22 (1993), 794\u2013806.","journal-title":"SIAM Journal on Computing"},{"key":"BF01293483_CR4","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, M. Hansen, and T. Leighton. Solving query-retrieval problems by compacting Voronoi diagrams.Proc. 22nd ACM Symposium on Theory of Computing, 1990, pp. 331\u2013340.","DOI":"10.1145\/100216.100260"},{"key":"BF01293483_CR5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1017\/S0963548300000225","volume":"1","author":"N. Alon","year":"1992","unstructured":"N. Alon, I. B\u00e1r\u00e1ny, Z. F\u00fcredi, and D. Kleitman. Point selections and weak \u025b-nets for convex hulls.Combinatorics, Probability, & Computing,1 (1992), 189\u2013200.","journal-title":"Combinatorics, Probability, & Computing"},{"key":"BF01293483_CR6","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/BF02574700","volume":"6","author":"B. Aronov","year":"1991","unstructured":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger. Points and triangles in the plane and halving planes in the space.Discrete & Computational Geometry,6 (1991), 435\u2013442.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR7","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. Bentley","year":"1980","unstructured":"J. Bentley and J. Saxe. Decomposable searching problems, I: Static-to-dynamic transformation.Journal of Algorithms,1 (1980), 301\u2013358.","journal-title":"Journal of Algorithms"},{"key":"BF01293483_CR8","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle. Lower bounds on the complexity of polytope range searching.Journal of the American Mathematical Society,2 (1989), 637\u2013666.","journal-title":"Journal of the American Mathematical Society"},{"key":"BF01293483_CR9","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF02573973","volume":"10","author":"B. Chazelle","year":"1993","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line-pair, and parametric searching.Discrete & Computational Geometry,10 (1993), 183\u2013196.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR10","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, L. Guibas, and D. T. Lee. The power of geometric duality.BIT,25 (1985), 76\u201390.","journal-title":"BIT"},{"key":"BF01293483_CR11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02187685","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and F. P. Preparata. Half-space range searching: An algorithmic application of k-sets.Discrete & Computational Geometry,1 (1986), 83\u201393.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR12","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems.Algorithmica,8 (1992), 407\u2013430.","journal-title":"Algorithmica"},{"key":"BF01293483_CR13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson. New applications of random sampling in computational geometry.Discrete& Computational Geometry,2 (1987), 195\u2013222.","journal-title":"Discrete& Computational Geometry"},{"key":"BF01293483_CR14","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. L. Clarkson","year":"1988","unstructured":"K. L. Clarkson. A randomized algorithm for closest-point queries.SIAM Journal on Computing,17 (1988), 830\u2013847.","journal-title":"SIAM Journal on Computing"},{"key":"BF01293483_CR15","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. Shor. New applications of random sampling in computational geometry, II.Discrete & Computational Geometry,4 (1989), 387\u2013421.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR16","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02574381","volume":"12","author":"T. Dey","year":"1994","unstructured":"T. Dey and H. Edelsbrunner. Counting triangle crossings and halving planes.Discrete & Computational Geometry,12 (1994), 281\u2013289.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR17","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, New York, 1987."},{"key":"BF01293483_CR18","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and E. Welzl. Constructing belts in two-dimensional arrangements with applications.SIAM Journal on Computing,15 (1986), 271\u2013284.","journal-title":"SIAM Journal on Computing"},{"key":"BF01293483_CR19","doi-asserted-by":"crossref","unstructured":"D. Eppstein. Dynamic three-dimensional linear programming.Proc. 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 94\u2013103.","DOI":"10.1109\/SFCS.1991.185410"},{"key":"BF01293483_CR20","unstructured":"D. Eppstein. Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions.Discrete & Computational Geometry, to appear."},{"key":"BF01293483_CR21","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01994880","volume":"32","author":"J. Hershberger","year":"1992","unstructured":"J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm.BIT,32 (1992), 249\u2013267.","journal-title":"BIT"},{"key":"BF01293483_CR22","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. Matou\u0161ek. Efficient partition trees.Discrete & Computational Geometry,8 (1992), 315\u2013334.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR23","doi-asserted-by":"crossref","unstructured":"J. Matousek and O. Schwarzkopf. Linear optimization queries.Proc. 8th ACM Symposium on Computational Geometry, 1992, pp. 16\u201325.","DOI":"10.1145\/142675.142683"},{"key":"BF01293483_CR24","doi-asserted-by":"crossref","unstructured":"J. Matousek. Approximations and optimal geometric divide-and-conquer.Proc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 506\u2013511.","DOI":"10.1145\/103418.103470"},{"issue":"3","key":"BF01293483_CR25","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matousek","year":"1992","unstructured":"J. Matousek. Reporting points in halfspaces.Computational Geometry: Theory and Applications,2(3) (1992), 169\u2013186.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"BF01293483_CR26","first-page":"720","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Linear-time algorithms for linear programming in \u211d3 and related problems.SIAM Journal on Computing,12 (1983), 720\u2013732.","journal-title":"SIAM Journal on Computing"},{"key":"BF01293483_CR27","volume-title":"Multi-Dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1985","unstructured":"K. Mehlhorn.Multi-Dimensional Searching and Computational Geometry. Springer-Verlag, Berlin, 1985."},{"key":"BF01293483_CR28","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K. Mulmuley","year":"1991","unstructured":"K. Mulmuley. On levels in arrangements and Voronoi diagrams.Discrete & Computational Geometry,6 (1991), 307\u2013338.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR29","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Randomized multidimensional search trees: Further results in dynamic sampling.Proc. 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 216\u2013227.","DOI":"10.1109\/SFCS.1991.185371"},{"key":"BF01293483_CR30","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Randomized multidimensional search trees: Lazy balancing and dynamic shuffling.Proc. 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 180\u2013186.","DOI":"10.1109\/SFCS.1991.185368"},{"key":"BF01293483_CR31","volume-title":"Lecture Notes in Computer Science, Vol. 156","author":"M. Overmars","year":"1983","unstructured":"M. Overmars.The Design of Dynamic Data Structures. Lecture Notes in Computer Science, Vol. 156, Springer-Verlag, Berlin, 1983."},{"key":"BF01293483_CR32","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane.Journal of Computer and System Sciences,23 (1981), 166\u2013204.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01293483_CR33","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02187829","volume":"7","author":"J. Pach","year":"1992","unstructured":"J. Pach, W. Steiger, and E. Szemer\u00e9di. An upper bound on the number of planar k-sets.Discrete & Computational Geometry,7 (1992), 109\u2013123.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR34","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/BF02187852","volume":"7","author":"M. Smid","year":"1992","unstructured":"M. Smid. Maintaining minimal distances of a point set in polylogarithmic time.Discrete & Computational Geometry,7 (1992), 415\u2013431.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01293483_CR35","unstructured":"C. Schwarz and M. Smid. An 0(n logn log logn) algorithm for online closest pair problem.Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 517\u2013526."},{"key":"BF01293483_CR36","unstructured":"K. Supowit. New techniques for some dynamic closest-point and farthest-point problems.Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 84\u201390."},{"key":"BF01293483_CR37","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0097-3165(92)90028-S","volume":"61","author":"S. Vre\u0107ica","year":"1992","unstructured":"S. Vre\u0107ica and R. \u017divaljevi\u0107. The colored tverberg's problem and complexes of injective functions.Journal of Combinatorial Theory, Series A,61 (1992), 309\u2013318.","journal-title":"Journal of Combinatorial Theory, Series A"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293483.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01293483\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T11:18:31Z","timestamp":1556795911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01293483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,4]]}},"alternative-id":["BF01293483"],"URL":"https:\/\/doi.org\/10.1007\/bf01293483","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,4]]}}}