{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:18:19Z","timestamp":1725549499211},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_10","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"110-121","source":"Crossref","is-referenced-by-count":4,"title":["Approximate Range Searching Using Binary Space Partitions"],"prefix":"10.1007","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[]},{"given":"Micha","family":"Streppel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s00454-002-2817-1","volume":"28","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., de Berg, M., Gudmundsson, J., Hammar, M., Haverkort, H.J.: Box-trees and R-trees with near-optimal query time. Discrete Comput. Geom.\u00a028, 291\u2013312 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J., Pollack, R. (eds.) Advances in Discrete and Computational Geometry,Contemporary Mathematics, vol.\u00a0223, pp. 1\u201356. American Mathematical Society (1998)","DOI":"10.1090\/conm\/223\/03131"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"1422","DOI":"10.1137\/S0097539797320578","volume":"29","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Grove, E., Murali, T.M., Vitter, J.S.: Binary space partitions for fat rectangles. SIAM J. Comput.\u00a029, 1422\u20131448 (2000)","journal-title":"SIAM J. Comput."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Murali, T.M., Vitter, J.S.: Practical techniques for constructing binary space partition for orthogonal rectangles. In: Proc. 13th ACM Symp. of Comput. Geom, pp. 382\u2013384 (1997)","DOI":"10.1145\/262839.263011"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1137\/S0097539794269801","volume":"19","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Suri, S.: Surface Approximation and Geometric Partitions. SIAM J. Comput.\u00a019, 1016\u20131035 (1998)","journal-title":"SIAM J. Comput."},{"key":"10_CR6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0925-7721(00)00022-5","volume":"17","author":"A. Arya","year":"2000","unstructured":"Arya, A., Mount, D.: Approximate range searching, Comput. Geom. Theory Appl.\u00a017, 135\u2013152 (2000)","journal-title":"Geom. Theory Appl."},{"key":"10_CR7","unstructured":"Ballieux, C.: Motion planning using binary space partitions. Technical Report Inf\/src\/93-25, Utrecht University (1993)"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0925-7721(03)00016-6","volume":"26","author":"M. Berg de","year":"2003","unstructured":"de Berg, M., David, H., Katz, M.J., Overmars, M., van der Stappen, A.F., Vleugels, J.: Guarding scenes against invasive hypercubes. Comput. Geom.\u00a026, 99\u2013117 (2003)","journal-title":"Comput. Geom."},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s004530010047","volume":"28","author":"M. Berg de","year":"2000","unstructured":"de Berg, M.: Linear size binary space partitions for uncluttered scenes. Algorithmica\u00a028, 353\u2013366 (2000)","journal-title":"Algorithmica"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/3-540-58218-5_6","volume-title":"Algorithm Theory - SWAT 1994","author":"M. Berg de","year":"1994","unstructured":"de Berg, M., de Groot, M., Overmars, M.: New results on binary space partitions in the plane. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol.\u00a0824, pp. 61\u201372. Springer, Heidelberg (1994)"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"de Berg, M., Katz, M.J., van der Stappen, A.F., Vleugels, J.: Realistic input models for geometric algorithms. In: Proc. 13th Annu. ACM Sympos. Comput. Geom, pp. 294\u2013303 (1997)","DOI":"10.1145\/262839.262986"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Chin, N., Feiner, S.: Near real time shadow generation using bsp trees. In: Proc. SIGGRAPH 1989, pp. 99\u2013106 (1989)","DOI":"10.1145\/74333.74343"},{"key":"10_CR13","unstructured":"Duncan, C.A.: Balanced Aspect Ratio Trees, Ph.D. Thesis, John Hopkins University (1999)"},{"key":"10_CR14","unstructured":"Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees. In: Proc. 10th Ann. ACM-SIAM Sympos. Discrete Algorithms, pp. 300\u2013309 (1999)"},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/965105.807481","volume":"14","author":"H. Fuchs","year":"1980","unstructured":"Fuchs, H., Kedem, Z.M., Naylor, B.: On visible surface generation by a priori tree structures. Comput. Graph.\u00a014(3), 124\u2013133 (1980); Proc. SIGGRAPH 1980","journal-title":"Comput. Graph."},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom.\u00a02, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Haverkort, H.J., de Berg, M., Gudmundsson, J.: Box-Trees for Collision Checking in Industrial Installations. In: Proc. 18th ACM Symp. on Computational Geometry, pp. 53\u201362 (2002)","DOI":"10.1145\/513400.513407"},{"issue":"4","key":"10_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/97880.97892","volume":"24","author":"B. Naylor","year":"1990","unstructured":"Naylor, B., Amanatides, J.A., Thibault, W.: Merging BSP trees yields polyhedral set operations. Comput. Graph.\u00a024(4), 115\u2013124 (1990); Proc. SIGGRAPH 1990","journal-title":"Comput. Graph."},{"key":"10_CR19","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF01931656","volume":"30","author":"M.H. Overmars","year":"1990","unstructured":"Overmars, M.H., Schipper, H., Sharir, M.: Storing line segments in partition trees. BIT\u00a030, 385\u2013403 (1990)","journal-title":"BIT"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02187806","volume":"5","author":"M.S. Paterson","year":"1990","unstructured":"Paterson, M.S., Yao, F.F.: Efficient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom.\u00a05, 485\u2013503 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0196-6774(92)90007-Y","volume":"13","author":"M.S. Paterson","year":"1992","unstructured":"Paterson, M.S., Yao, F.F.: Optimal binary space partitions for orthogonal objects. J. Algorithms\u00a013, 99\u2013113 (1992)","journal-title":"J. Algorithms"},{"key":"10_CR22","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, Heidelberg (1985)"},{"issue":"4","key":"10_CR23","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/127719.122725","volume":"25","author":"S.J. Teller","year":"1991","unstructured":"Teller, S.J., S\u00e9quin, C.H.: Visibility preprocessing for interactive walkthroughs. Comput. Graph\u00a025(4), 61\u201369 (1991); Proc. SIGGRAPH 1991","journal-title":"Comput. Graph"},{"key":"10_CR24","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00454-003-2921-x","volume":"20","author":"C.D. T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: A Note on Binary Plane Partitions. Discrete Comput. Geom.\u00a020, 3\u201316 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/S0097539702403785","volume":"32","author":"C.D. T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: Binary Space Partitions for Line Segments with a Limited Number of Directions. SIAM J. Comput.\u00a032, 307\u2013325 (2003)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10_CR26","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/37402.37421","volume":"21","author":"W.C. Thibault","year":"1987","unstructured":"Thibault, W.C., Naylor, B.F.: Set operations on polyhedra using binary space partitioning trees. Comput. Graph.\u00a021(4), 153\u2013162 (1987); Proc. SIGGRAPH 1987","journal-title":"Comput. Graph."}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T23:08:48Z","timestamp":1558912128000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}