{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:31:29Z","timestamp":1770071489480,"version":"3.49.0"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,2,24]],"date-time":"2012-02-24T00:00:00Z","timestamp":1330041600000},"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":[[2012,6]]},"DOI":"10.1007\/s00454-012-9410-z","type":"journal-article","created":{"date-parts":[[2012,2,23]],"date-time":"2012-02-23T14:56:49Z","timestamp":1330009009000},"page":"661-690","source":"Crossref","is-referenced-by-count":40,"title":["Optimal Partition Trees"],"prefix":"10.1007","volume":"47","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,24]]},"reference":[{"key":"9410_CR1","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/1.9781611973068.21","volume-title":"Proc. 20th ACM-SIAM Sympos. Discrete Algorithms","author":"P. Afshani","year":"2009","unstructured":"Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proc. 20th ACM-SIAM Sympos. Discrete Algorithms, pp. 180\u2013186 (2009)"},{"key":"9410_CR2","volume-title":"Intersection and Decomposition Algorithms for Planar Arrangements","author":"P.K. Agarwal","year":"1991","unstructured":"Agarwal, P.K.: Intersection and Decomposition Algorithms for Planar Arrangements. Cambridge University Press, Cambridge (1991)"},{"key":"9410_CR3","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/0221035","volume":"21","author":"P.K. Agarwal","year":"1992","unstructured":"Agarwal, P.K.: Ray shooting and other applications of spanning trees with low stabbing number. SIAM J. Comput. 21, 540\u2013570 (1992)","journal-title":"SIAM J. Comput."},{"key":"9410_CR4","volume-title":"CRC Handbook of Discrete and Computational Geometry","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K.: Range searching. In: Goodman, J., O\u2019Rourke, J. (eds.) CRC Handbook of Discrete and Computational Geometry. CRC Press, New York (2004)"},{"key":"9410_CR5","first-page":"1","volume-title":"Discrete and Computational Geometry: Ten Years Later","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Discrete and Computational Geometry: Ten Years Later, pp. 1\u201356. AMS, Providence (1999)"},{"key":"9410_CR6","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/BF02574015","volume":"11","author":"P.K. Agarwal","year":"1994","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: On range searching with semialgebraic sets. Discrete Comput. Geom. 11, 393\u2013418 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF02189304","volume":"9","author":"P.K. Agarwal","year":"1993","unstructured":"Agarwal, P.K., Sharir, M.: Applications of a new space-partitioning technique. Discrete Comput. Geom. 9, 11\u201338 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR8","first-page":"267","volume-title":"Proc. 10th ACM Sympos. Comput. Geom.","author":"P.K. Agarwal","year":"1995","unstructured":"Agarwal, P.K., Aronov, B., Suri, S.: Stabbing triangulations by lines in 3D. In: Proc. 10th ACM Sympos. Comput. Geom., pp. 267\u2013276 (1995)"},{"key":"9410_CR9","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput. 29, 912\u2013953 (1999)","journal-title":"SIAM J. Comput."},{"key":"9410_CR10","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1006\/jcss.2000.1709","volume":"61","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Arge, L., Erickson, J., Franciosa, P.G., Vitter, J.S.: Efficient searching with linear constraints. J. Comput. Syst. Sci. 61, 194\u2013216 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9410_CR11","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1109\/SFCS.1994.365724","volume-title":"Proc. 35th IEEE Sympos. Found. Comput. Sci.","author":"N.M. Amato","year":"1994","unstructured":"Amato, N.M., Goodrich, M.T., Ramos, E.A.: Parallel algorithms for higher-dimensional convex hulls. In: Proc. 35th IEEE Sympos. Found. Comput. Sci., pp. 683\u2013694 (1994)"},{"key":"9410_CR12","unstructured":"Arora, S., Hazan, E., Kale, S.: Multiplicative weights method: a meta-algorithm and its applications. Theory Comput. (2012, to appear)"},{"key":"9410_CR13","first-page":"29","volume-title":"Proc. 26th ACM Sympos. Comput. Geom.","author":"S. Arya","year":"2010","unstructured":"Arya, S., Mount, D.M., Xia, J.: Tight lower bounds for halfspace range searching. In: Proc. 26th ACM Sympos. Comput. Geom., pp. 29\u201337 (2010)"},{"key":"9410_CR14","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. Bentley","year":"1980","unstructured":"Bentley, J., Saxe, J.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1, 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"9410_CR15","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14, 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR16","first-page":"284","volume-title":"Proc. 12th ACM Sympos. Comput. Geom.","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Fixed-dimensional linear programming queries made easy. In: Proc. 12th ACM Sympos. Comput. Geom., pp. 284\u2013290 (1996)"},{"key":"9410_CR17","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02712874","volume":"16","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom. 16, 369\u2013387 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR18","first-page":"423","volume-title":"Proc. 15th ACM-SIAM Sympos. Discrete Algorithms","author":"T.M. Chan","year":"2004","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pp. 423\u2013429 (2004)"},{"key":"9410_CR19","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/PL00009327","volume":"18","author":"T.M. Chan","year":"1997","unstructured":"Chan, T.M., Snoeyink, J., Yap, C.-K.: Primal dividing and dual pruning: output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams. Discrete Comput. Geom. 18, 433\u2013454 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR20","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B.: Lower bounds on the complexity of polytope range searching. J. Am. Math. Soc. 2, 637\u2013666 (1989)","journal-title":"J. Am. Math. Soc."},{"key":"9410_CR21","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9, 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR22","first-page":"25.1","volume-title":"Handbook of Data Structures and Applications","author":"B Chazelle","year":"2005","unstructured":"Chazelle, B: Cuttings. In: Mehta, D.P., Sahni, S. (eds.) Handbook of Data Structures and Applications, pp. 25.1\u201325.10. CRC Press, Boca Raton (2005)"},{"key":"9410_CR23","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10, 229\u2013249 (1990)","journal-title":"Combinatorica"},{"key":"9410_CR24","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0925-7721(95)00002-X","volume":"5","author":"B. Chazelle","year":"1996","unstructured":"Chazelle, B., Rosenberg, B.: Simplex range reporting on a pointer machine. Comput. Geom., Theory Appl. 5, 237\u2013247 (1996)","journal-title":"Comput. Geom., Theory Appl."},{"key":"9410_CR25","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Welzl, E.: Quasi-optimal range searching in space of finite VC-dimension. Discrete Comput. Geom. 4, 467\u2013489 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR26","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica 8, 407\u2013429 (1992)","journal-title":"Algorithmica"},{"key":"9410_CR27","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K.L. Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17, 830\u2013847 (1988)","journal-title":"SIAM J. Comput."},{"key":"9410_CR28","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42, 488\u2013499 (1995)","journal-title":"J. ACM"},{"key":"9410_CR29","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR30","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S0218195995000210","volume":"5","author":"M. Berg de","year":"1995","unstructured":"de Berg, M., Schwarzkopf, O.: Cuttings and applications. Int. J. Comput. Geom. Appl. 5, 343\u2013355 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9410_CR31","unstructured":"Dobkin, D., Edelsbrunner, H.: Organizing point sets in two and three dimensions. Report f130, Inst. Informationsverarb., Tech. Univ. Graz, Austria (1984)"},{"key":"9410_CR32","unstructured":"Edelsbrunner, H., Huber, F.: Dissecting sets of points in two and three dimensions. Report f138, Inst. Informationsverarb., Tech. Univ. Graz, Austria (1984)"},{"key":"9410_CR33","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0190(86)90088-8","volume":"23","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Welzl, E.: Halfplanar range search in linear space and O(n 0.695) query time. Inf. Process. Lett. 23, 289\u2013293 (1986)","journal-title":"Inf. Process. Lett."},{"key":"9410_CR34","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF02187742","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., Welzl, E.: Implicitly representing arrangements of lines or segments. Discrete Comput. Geom. 4, 433\u2013466 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR35","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR36","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1006\/jagm.1995.1017","volume":"18","author":"J. Hershberger","year":"1995","unstructured":"Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: shoot a ray, take a walk. J. Algorithms 18, 403\u2013431 (1995)","journal-title":"J. Algorithms"},{"key":"9410_CR37","doi-asserted-by":"crossref","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"9410_CR38","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1051\/ita\/1991250201031","volume":"25","author":"J. Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Spanning trees with low crossing number. RAIRO Theor. Inform. Appl. 25, 103\u2013124 (1991)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9410_CR39","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR40","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom., Theory Appl. 2, 169\u2013186 (1992)","journal-title":"Comput. Geom., Theory Appl."},{"key":"9410_CR41","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1006\/jagm.1993.1023","volume":"14","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Linear optimization queries. J. Algorithms 14, 432\u2013448 (1993). Also with O. Schwarzkopf in Proc. 8th ACM Sympos. Comput. Geom., pp.\u00a016\u201325, 1992","journal-title":"J. Algorithms"},{"key":"9410_CR42","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10, 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR43","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1145\/197405.197408","volume":"26","author":"J. Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J.: Geometric range searching. ACM Comput. Surv. 26, 421\u2013461 (1994)","journal-title":"ACM Comput. Surv."},{"key":"9410_CR44","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)"},{"key":"9410_CR45","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF02573975","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J., Schwarzkopf, O.: On ray shooting in convex polytopes. Discrete Comput. Geom. 10, 215\u2013232 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9410_CR46","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9410_CR47","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs (1994)"},{"key":"9410_CR48","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"9410_CR49","first-page":"390","volume-title":"Proc. 15th ACM Sympos. Comput. Geom.","author":"E. Ramos","year":"1999","unstructured":"Ramos, E.: On range reporting, ray shooting, and k-level construction. In: Proc. 15th ACM Sympos. Comput. Geom., pp. 390\u2013399 (1999)"},{"key":"9410_CR50","first-page":"176","volume-title":"Proc. 16th ACM Sympos. Comput. Geom.","author":"E. Ramos","year":"2000","unstructured":"Ramos, E.: Linear programming queries revisited. In: Proc. 16th ACM Sympos. Comput. Geom., pp.\u00a0176\u2013181 (2000)"},{"key":"9410_CR51","first-page":"404","volume-title":"Proc. 18th ACM Sympos. Theory Comput","author":"R. Seidel","year":"1986","unstructured":"Seidel, R.: Constructing higher-dimensional convex hulls at logarithmic cost per face. In: Proc. 18th ACM Sympos. Theory Comput, pp. 404\u2013413 (1986)"},{"key":"9410_CR52","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/3-540-55488-2_30","volume-title":"Data Structures and Efficient Algorithms","author":"E. Welzl","year":"1992","unstructured":"Welzl, E.: On spanning trees with low crossing numbers. In: Monien, B., Ottmann, T. (eds.) Data Structures and Efficient Algorithms. Lect. Notes Comput. Sci., vol. 594, pp. 233\u2013249. Springer, Berlin (1992)"},{"key":"9410_CR53","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D.E. Willard","year":"1982","unstructured":"Willard, D.E.: Polygon retrieval. SIAM J. Comput. 11, 149\u2013165 (1982)","journal-title":"SIAM J. Comput."},{"key":"9410_CR54","first-page":"163","volume-title":"Proc. 17th ACM Sympos. Theory Comput.","author":"A.C. Yao","year":"1985","unstructured":"Yao, A.C., Yao, F.F.: A general approach to D-dimensional geometric queries. In: Proc. 17th ACM Sympos. Theory Comput., pp. 163\u2013168 (1985)"},{"key":"9410_CR55","first-page":"258","volume-title":"Proc. 15th ACM Sympos. Theory Comput.","author":"F.F. Yao","year":"1983","unstructured":"Yao, F.F.: A\u00a03-space partition and its applications. In: Proc. 15th ACM Sympos. Theory Comput., pp.\u00a0258\u2013263 (1983)"},{"key":"9410_CR56","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1137\/0218025","volume":"18","author":"F.F. Yao","year":"1989","unstructured":"Yao, F.F., Dobkin, D.P., Edelsbrunner, H., Paterson, M.S.: Partitioning space for range queries. SIAM J. Comput. 18, 371\u2013384 (1989)","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9410-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9410-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9410-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:50:35Z","timestamp":1559087435000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9410-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,24]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9410"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9410-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,24]]}}}