{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:34:39Z","timestamp":1742960079920,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642219306"},{"type":"electronic","value":"9783642219313"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21931-3_2","type":"book-chapter","created":{"date-parts":[[2011,6,17]],"date-time":"2011-06-17T14:11:35Z","timestamp":1308319895000},"page":"17-29","source":"Crossref","is-referenced-by-count":4,"title":["An Optimal Hidden-Surface Algorithm and Its Parallelization"],"prefix":"10.1007","author":[{"given":"F.","family":"D\u00e9vai","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-15781-3_7","volume-title":"Algorithms \u2013 ESA 2010","author":"D. Ajwani","year":"2010","unstructured":"Ajwani, D., Sitchinava, N., Zeh, N.: Geometric algorithms for private-cache chip multiprocessors. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06347, pp. 75\u201386. Springer, Heidelberg (2010)"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1145\/800196.806007","volume-title":"Proc. 1967 22nd National Conference, ACM 1967","author":"A. Appel","year":"1967","unstructured":"Appel, A.: The notion of quantitative invisibility and the machine rendering of solids. In: Proc. 1967 22nd National Conference, ACM 1967, pp. 387\u2013393. ACM Press, New York (1967)"},{"key":"2_CR3","first-page":"197","volume-title":"Proc. 20th Annual Symposium on Parallelism in Algorithms and Architectures, SPAA 2008","author":"L. Arge","year":"2008","unstructured":"Arge, L., Goodrich, M.T., Nelson, M., Sitchinava, N.: Fundamental parallel algorithms for private-cache chip multiprocessors. In: Proc. 20th Annual Symposium on Parallelism in Algorithms and Architectures, SPAA 2008, pp. 197\u2013206. ACM Press, New York (2008)"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T. Asano","year":"1986","unstructured":"Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica\u00a01, 49\u201363 (1986)","journal-title":"Algorithmica"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1137\/S0097539797329397","volume":"31","author":"A.M. Ben-Amram","year":"2001","unstructured":"Ben-Amram, A.M., Galil, Z.: Topological lower bounds on algebraic random access machines. SIAM J. Comput.\u00a031, 722\u2013761 (2001)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR6","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/j.comgeo.2008.12.010","volume":"43","author":"M. Berg de","year":"2010","unstructured":"de Berg, M., Gray, C.: Computing the visibility map of fat objects. Comput. Geom. Theory Appl.\u00a043(4), 410\u2013418 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/BF01377182","volume":"12","author":"M. Berg de","year":"1994","unstructured":"de Berg, M., Halperin, D., Overmars, M., Snoeyink, J., van Kreveld, M.: Efficient ray shooting and hidden surface removal. Algorithmica\u00a012, 30\u201353 (1994)","journal-title":"Algorithmica"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Maggs, B.M.: Parallel algorithms. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook, Chapman & Hall\/CRC (2010)","DOI":"10.1201\/9781584888215-c25"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B., Guibas, L.J., Lee, D.T.: The power of geometric duality. BIT\u00a025, 76\u201390 (1985)","journal-title":"BIT"},{"issue":"1","key":"2_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/71.980023","volume":"13","author":"W. Chen","year":"2002","unstructured":"Chen, W., Wada, K.: On computing the upper envelope of segments in parallel. IEEE Transactions on Parallel and Distributed Systems\u00a013(1), 5\u201313 (2002)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"Cole, R.: Parallel merge sort. SIAM J. Comput.\u00a017, 770\u2013785 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0747-7171(89)80003-3","volume":"7","author":"R. Cole","year":"1989","unstructured":"Cole, R., Sharir, M.: Visibility problems for polyhedral terrains. Journal of Symbolic Computation\u00a07(1), 11\u201330 (1989)","journal-title":"Journal of Symbolic Computation"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. Cook","year":"1986","unstructured":"Cook, S., Dwork, C., Reischuk, R.: Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput.\u00a015, 87\u201397 (1986)","journal-title":"SIAM J. Comput."},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"D\u00e9vai, F.: Quadratic bounds for hidden-line elimination. In: Proc. 2nd Annu. ACM Sympos. Comput. Geom, pp. 269\u2013275 (1986)","DOI":"10.1145\/10515.10544"},{"key":"2_CR15","unstructured":"D\u00e9vai, F.: An intersection-sensitive hidden-surface algorithm. In: Proc. Eurographics 1987, pp. 495\u2013502 (1987)"},{"key":"2_CR16","unstructured":"D\u00e9vai, F.: An O(logN) parallel time exact hidden-line algorithm. In: Advances in Computer Graphics Hardware II, Record of the Second Eurographics Workshop on Graphics Hardware, pp. 65\u201373 (1988)"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rouke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput.\u00a015, 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2_CR18","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/965105.807480","volume":"14","author":"W.R. Franklin","year":"1980","unstructured":"Franklin, W.R.: A linear time exact hidden surface algorithm. Comput. Graph.\u00a014(3), 117\u2013123 (1980); Proc. Siggraph 1980","journal-title":"Comput. Graph."},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/362912.362921","volume":"12","author":"R. Galimberti","year":"1969","unstructured":"Galimberti, R., Montanari, U.: An algorithm for hidden-line elimination. Commun. ACM\u00a012, 206 (1969)","journal-title":"Commun. ACM"},{"key":"2_CR20","first-page":"1","volume":"54","author":"M.T. Goodrich","year":"1992","unstructured":"Goodrich, M.T.: A polygonal approach to hidden-line and hidden-surface elimination. CVGIP: Graph. Models Image Process.\u00a054, 1\u201312 (1992)","journal-title":"CVGIP: Graph. Models Image Process."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/BF02189329","volume":"9","author":"M.T. Goodrich","year":"1993","unstructured":"Goodrich, M.T.: Constructing arrangements optimally in parallel. Discrete and Computational Geometry\u00a09, 371\u2013385 (1993)","journal-title":"Discrete and Computational Geometry"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1993.1059","volume":"107","author":"M.T. Goodrich","year":"1993","unstructured":"Goodrich, M.T., Atallah, M.J., Overmars, M.H.: Output-sensitive methods for rectilinear hidden surface removal. Inform. Comput.\u00a0107, 1\u201324 (1993)","journal-title":"Inform. Comput."},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00453-001-0042-6","volume":"31","author":"N. Gupta","year":"2001","unstructured":"Gupta, N., Sen, S.: An efficient output-size sensitive parallel algorithm for hidden-surface removal for terrains. Algorithmica\u00a031, 179\u2013207 (2001)","journal-title":"Algorithmica"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/0219047","volume":"19","author":"T. Hagerup","year":"1990","unstructured":"Hagerup, T.: Planar depth-first search in O(logn) parallel time. SIAM J. Comput.\u00a019, 678\u2013704 (1990)","journal-title":"SIAM J. Comput."},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02574383","volume":"12","author":"D. Halperin","year":"1994","unstructured":"Halperin, D., Sharir, M.: New bounds for lower envelopes in three dimensions, with applications to visibility in terrains. Discrete and Computational Geometry\u00a012, 313\u2013326 (1994)","journal-title":"Discrete and Computational Geometry"},{"issue":"3","key":"2_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0097-8493(82)90005-X","volume":"6","author":"C. Hornung","year":"1982","unstructured":"Hornung, C.: An approach to a calculation-minimized hidden line algorithm. Computers & Graphics\u00a06(3), 121\u2013126 (1982)","journal-title":"Computers & Graphics"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1109\/MCG.1984.275874","volume":"4","author":"C. Hornung","year":"1984","unstructured":"Hornung, C.: A method for solving the visibility problem. IEEE Comput. Graph. Appl.\u00a04, 26\u201333 (1984)","journal-title":"IEEE Comput. Graph. Appl."},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"IBM Blue Gene Team: Overview of the IBM Blue Gene\/P project. IBM J. Res. Dev.\u00a052, 199\u2013220 (January 2008)","DOI":"10.1147\/rd.521.0199"},{"key":"2_CR29","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison Wesley Longman Publishing Co., Inc, Redwood City (1992)"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0925-7721(92)90024-M","volume":"2","author":"M.J. Katz","year":"1992","unstructured":"Katz, M.J., Overmars, M.H., Sharir, M.: Efficient hidden surface removal for objects with small union size. Comput. Geom. Theory Appl.\u00a02, 223\u2013234 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.cad.2006.08.007","volume":"39","author":"T. Keeler","year":"2007","unstructured":"Keeler, T., Fedorkiw, J., Ghali, S.: The spherical visibility map. Comput. Aided Des.\u00a039, 17\u201326 (2007)","journal-title":"Comput. Aided Des."},{"issue":"4","key":"2_CR32","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R.E. Ladner","year":"1980","unstructured":"Ladner, R.E., Fischer, M.J.: Parallel prefix computation. J. ACM\u00a027(4), 831\u2013838 (1980)","journal-title":"J. ACM"},{"key":"2_CR33","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F. Thomson Leighton","year":"1992","unstructured":"Thomson Leighton, F.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers Inc, San Mateo (1992)"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/T-C.1970.222898","volume":"C-19","author":"P.P. Loutrel","year":"1970","unstructured":"Loutrel, P.P.: A solution to the hidden-line problem for computer drawn polyhedra. IEEE Trans. Comput.\u00a0C-19, 205\u2013213 (1970)","journal-title":"IEEE Trans. Comput."},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1145\/1365490.1365501","volume":"6","author":"W. Mark","year":"2008","unstructured":"Mark, W.: Future graphics architectures. Queue\u00a06, 54\u201364 (2008)","journal-title":"Queue"},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/27625.27627","volume":"6","author":"M. McKenna","year":"1987","unstructured":"McKenna, M.: Worst-case optimal hidden-surface removal. ACM Trans. Graph.\u00a06, 19\u201328 (1987)","journal-title":"ACM Trans. Graph."},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1145\/74334.74372","volume":"23","author":"K. Mulmuley","year":"1989","unstructured":"Mulmuley, K.: An efficient algorithm for hidden surface removal. Siggraph Comput. Graph.\u00a023, 379\u2013388 (1989)","journal-title":"Siggraph Comput. Graph."},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/BF01293267","volume":"11","author":"M.H. Overmars","year":"1994","unstructured":"Overmars, M.H., Sharir, M.: An improved technique for output-sensitive hidden surface removal. Algorithmica\u00a011, 469\u2013484 (1994)","journal-title":"Algorithmica"},{"key":"2_CR39","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF01758847","volume":"8","author":"F. Preparata","year":"1992","unstructured":"Preparata, F., Vitter, J., Yvinec, M.: Output-sensitive generation of the perspective view of isothetic parallelepipeds. Algorithmica\u00a08, 257\u2013283 (1992)","journal-title":"Algorithmica"},{"key":"2_CR40","volume-title":"Handbook of Parallel Computing: Models, Algorithms and Applications","author":"S. Rajasekaran","year":"2008","unstructured":"Rajasekaran, S., Reif, J.H.: Handbook of Parallel Computing: Models, Algorithms and Applications. Chapman & Hall\/CRC, Boca Raton (2008)"},{"issue":"5","key":"2_CR41","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J.H. Reif","year":"1985","unstructured":"Reif, J.H.: Depth-first search is inherently sequential. Information Processing Letters\u00a020(5), 229\u2013234 (1985)","journal-title":"Information Processing Letters"},{"key":"2_CR42","first-page":"193","volume-title":"Proc. 4th Annual Symposium on Computational Geometry, SCG 1988","author":"J.H. Reif","year":"1988","unstructured":"Reif, J.H., Sen, S.: An efficient output-sensitive hidden surface removal algorithm and its parallelization. In: Proc. 4th Annual Symposium on Computational Geometry, SCG 1988, pp. 193\u2013200. ACM Press, New York (1988)"},{"issue":"5","key":"2_CR43","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0895-7177(95)00016-U","volume":"21","author":"J.H. Reif","year":"1995","unstructured":"Reif, J.H., Sen, S.: An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains. Mathematical and Computer Modelling\u00a021(5), 89\u2013104 (1995)","journal-title":"Mathematical and Computer Modelling"},{"key":"2_CR44","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90048-8","volume":"29","author":"G.E. Shannon","year":"1988","unstructured":"Shannon, G.E.: A linear-processor algorithm for depth-first search in planar graphs. Inf. Process. Lett.\u00a029, 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"2_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102377.112141","volume":"11","author":"M. Sharir","year":"1992","unstructured":"Sharir, M., Overmars, M.H.: A simple output-sensitive algorithm for hidden surface removal. ACM Trans. Graph.\u00a011, 1\u201311 (1992)","journal-title":"ACM Trans. Graph."},{"key":"2_CR46","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/MC.2010.75","volume":"43","author":"A.C. Sodan","year":"2010","unstructured":"Sodan, A.C., Machina, J., Deshmeh, A., Macnaughton, K., Esbaugh, B.: Parallelism via multithreaded and multicore CPUs. Computer\u00a043, 24\u201332 (2010)","journal-title":"Computer"},{"issue":"1","key":"2_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/356625.356626","volume":"6","author":"I.E. Sutherland","year":"1974","unstructured":"Sutherland, I.E., Sproull, R.F., Schumacker, R.A.: A characterization of ten hidden-surface algorithms. ACM Comput. Surv.\u00a06(1), 1\u201355 (1974)","journal-title":"ACM Comput. Surv."},{"key":"2_CR48","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/SPIRE.2000.878204","volume-title":"Proc. 7th International Symposium on String Processing Information Retrieval (Spire 2000)","author":"U. Vishkin","year":"2000","unstructured":"Vishkin, U.: A PRAM-on-chip vision (invited abstract). In: Proc. 7th International Symposium on String Processing Information Retrieval (Spire 2000), p. 260. IEEE Computer Society Press, Washington, DC, USA (2000)"},{"key":"2_CR49","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/1866739.1866757","volume":"54","author":"U. Vishkin","year":"2011","unstructured":"Vishkin, U.: Using simple abstraction to reinvent computing for parallelism. Commun. ACM\u00a054, 75\u201385 (2011)","journal-title":"Commun. ACM"},{"key":"2_CR50","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1145\/321328.321330","volume":"13","author":"R.A. Weiss","year":"1966","unstructured":"Weiss, R.A.: Be Vision, a package of IBM 7090 FORTRAN programs to draw orthographic views of combinations of plane and quadric surfaces. J. ACM\u00a013, 194\u2013204 (1966)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications - ICCSA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21931-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T17:00:31Z","timestamp":1560272431000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21931-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642219306","9783642219313"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21931-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}