{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:37:29Z","timestamp":1787506649147,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648482","type":"print"},{"value":"9783540685302","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_18","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T17:14:16Z","timestamp":1194542056000},"page":"211-222","source":"Crossref","is-referenced-by-count":2,"title":["Constructing Binary Space Partitions for Orthogonal Rectangles in Practice"],"prefix":"10.1007","author":[{"given":"T. M.","family":"Murali","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter, Binary space partitions for fat rectangles, Proc. 37th Annu. IEEE Sympos. Found. Comput. Sci., October 1996, pp. 482\u2013491.","DOI":"10.1109\/SFCS.1996.548507"},{"key":"18_CR2","unstructured":"P. K. Agarwal and S. Suri, Surface approximation and geometric partitions, Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, 1994, pp. 24\u201333."},{"key":"18_CR3","volume-title":"Increasing Update Rates in the Building Walkthrough System with Automatic Model-space Subdivision and Potentially Visible Set Calculations","author":"J. M. Airey","year":"1990","unstructured":"J. M. Airey, Increasing Update Rates in the Building Walkthrough System with Automatic Model-space Subdivision and Potentially Visible Set Calculations, Ph.D. Thesis, Dept. of Computer Science, University of North Carolina, Chapel Hill, 1990."},{"key":"18_CR4","volume-title":"Modeling Global Diffiuse Illumination for Image Synthesis","author":"A. T. Campbell","year":"1991","unstructured":"A. T. Campbell, Modeling Global Diffiuse Illumination for Image Synthesis, Ph.D. Thesis, Dept. of Computer Sciences, University of Texas, Austin, 1991."},{"key":"18_CR5","unstructured":"T. Cassen, K. R. Subramanian, and Z. Michalewicz, Near-optimal construction of partitioning trees by evolutionary techniques, Proc. Graphics Interface\u2019 95, 1995, pp. 263\u2013271."},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/74334.74343","volume":"23","author":"N. Chin","year":"1989","unstructured":"N. Chin and S. Feiner, Near real-time shadow generation using BSP trees, Proc. SIGGRAPH 89, Comput. Graph., Vol. 23, ACM SIGGRAPH, 1989, pp. 99\u2013106.","journal-title":"Proc. SIGGRAPH 89, Comput. Graph."},{"key":"18_CR7","unstructured":"N. Chin and S. Feiner, Fast object-precision shadow generation for areal light sources using BSP trees, Proc. 1992 Sympos. Interactive 3D Graphics, 1992, pp. 21\u201330."},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"M. de Berg, Linear size binary space partitions for fat objects, Proc. 3rd Annu. European Sympos. Algorithms, Lecture Notes Comput. Sci., Vol. 979, Springer-Verlag, 1995, pp. 252\u2013263.","DOI":"10.1007\/3-540-60313-1_148"},{"key":"18_CR9","volume-title":"Computer Graphics: Principles and Practice","author":"J. D. Foley","year":"1990","unstructured":"J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes, Computer Graphics: Principles and Practice, Addison-Wesley, Reading, MA, 1990."},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/965105.807481","volume":"14","author":"H. Fuchs","year":"1980","unstructured":"H. Fuchs, Z. M. Kedem, and B. Naylor, On visible surface generation by a priori tree structures, Proc. SIGGRAPH 80, Comput. Graph., Vol. 14, ACMSIGGRAPH, 1980, pp. 124\u2013133.","journal-title":"Proc. SIGGRAPH 80, Comput. Graph."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"C. Mata and J. S. B. Mitchell, Approximation algorithms for geometric tour and network design problems, Proc. 11th Annu. ACM Sympos. Comput. Geom., 1995, pp. 360\u2013369.","DOI":"10.1145\/220279.220318"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"T. M. Murali and T. A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proc. 1997 Sympos. Interactive 3D Graphics, 1997, pp. 155\u2013162.","DOI":"10.1145\/253284.253326"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"M. J. Muus, Understanding the preparation and analysis of solid models, in: Techniques for Computer Graphics (D. F. Rogers and R. A. Earnshaw, eds.), Springer-Verlag, 1987.","DOI":"10.1007\/978-1-4613-8713-8_8"},{"key":"18_CR14","unstructured":"B. Naylor, Constructing good partitioning trees, Proc. Graphics Interface\u2019 93, 1993, pp. 181\u2013191."},{"key":"18_CR15","unstructured":"B. Naylor and W. Thibault, Application of BSP trees to ray-tracing and CSG evaluation, Technical Report GIT-ICS 86\/03, Georgia Institute of Tech., School of Information and Computer Science, February 1986."},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/97880.97892","volume":"24","author":"B. F. Naylor","year":"1990","unstructured":"B. F. Naylor, J. Amanatides, and W. C. Thibault, Merging BSP trees yields polyhedral set operations, Proc. SIGGRAPH 90, Comput. Graph., Vol. 24, ACM SIGGRAPH, 1990, pp. 115\u2013124.","journal-title":"Proc. SIGGRAPH 90, Comput. Graph."},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02187806","volume":"5","author":"M. S. Paterson","year":"1990","unstructured":"M. S. Paterson and F. F. Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete Comput. Geom., 5 (1990), 485\u2013503.","journal-title":"Discrete Comput. Geom."},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0196-6774(92)90007-Y","volume":"13","author":"M. S. Paterson","year":"1992","unstructured":"M. S. Paterson and F. F. Yao, Optimal binary space partitions for orthogonal objects, J. Algorithms, 13 (1992), 99\u2013113.","journal-title":"J. Algorithms"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp, Study for applying computer-generated images to visual simulation, Tech. Rep. AFHRL-TR-69-14, U.S. Air Force Human Resources Laboratory, 1969.","DOI":"10.21236\/AD0700375"},{"key":"18_CR20","unstructured":"P. J. Tanenbaum. Applications of computational geometry in army research and development. Invited talk, Second CGC Workshop on Computational Geometry, 1997."},{"key":"18_CR21","volume-title":"Visibility Computations in Densely Occluded Polyhedral Environments","author":"S. J. Teller","year":"1992","unstructured":"S. J. Teller, Visibility Computations in Densely Occluded Polyhedral Environments, Ph.D. Thesis, Dept. of Computer Science, University of California, Berkeley, 1992."},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/37402.37421","volume":"21","author":"W. C. Thibault","year":"1987","unstructured":"W. C. Thibault and B. F. Naylor, Set operations on polyhedra using binary space partitioning trees, Proc. SIGGRAPH 87, Comput. Graph., Vol. 21, ACM SIGGRAPH, 1987, pp. 153\u2013162.","journal-title":"Proc. SIGGRAPH 87, Comput. Graph."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:22:09Z","timestamp":1737505329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}