{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:54:19Z","timestamp":1725490459347},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744757"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74477-1_5","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T19:15:06Z","timestamp":1188328506000},"page":"51-62","source":"Crossref","is-referenced-by-count":1,"title":["Determining the Visibility of a Planar Set of Line Segments in ${\\mathcal{O}(n\\log\\log n)}$ Time"],"prefix":"10.1007","author":[{"given":"Frank","family":"D\u00e9vai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marina L.","family":"Gavrilova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","first-page":"22","volume-title":"Proc. GMAI\u201906 International Conference on Graphical Models and Imaging","author":"S. Dalal","year":"2006","unstructured":"Dalal, S., D\u00e9vai, F., Rahman, M.M.: High-performance rendering on clusters of workstations. In: Proc. GMAI\u201906 International Conference on Graphical Models and Imaging, pp. 22\u201327. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"5_CR2","unstructured":"Dalal, S., Rahman, M.M.: An efficient scanline-based system for the visualisation of large data sets. In: Proc. 2nd Internat. Conference on Computer Graphics, Imaging and Vision, Beijing, China, pp. 136\u2013143 (2005)"},{"key":"5_CR3","first-page":"469","volume-title":"Geometric Modeling and Computing: Seattle 2003","author":"M.M. Rahman","year":"2004","unstructured":"Rahman, M.M.: A scanline-based distributed system for the visualisation of large data sets. In: Lucian, M.L., Neamtu, M. (eds.) Geometric Modeling and Computing: Seattle 2003, pp. 469\u2013480. Nashboro Press, Brentwood, Tennessee, USA (2004)"},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0218035","volume":"18","author":"M.J. Atallah","year":"1989","unstructured":"Atallah, M.J., Cole, R., Goodrich, M.T.: Cascading divide-and-conquer\u2014A technique for designing parallel algorithms. SIAM J. Comput.\u00a018(3), 499\u2013532 (1989)","journal-title":"SIAM J. Comput."},{"key":"5_CR5","unstructured":"D\u00e9vai, F.: Complexity of two-dimensional visibility computations. In: Proc. 3rd European Conf. on CAD\/CAM and Computer Graphics, vol.\u00a03, pp. 827\u2013841 (1984)"},{"issue":"9","key":"5_CR6","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/362736.362739","volume":"13","author":"W.J. Bouknight","year":"1970","unstructured":"Bouknight, W.J.: A procedure for generation of three-dimensional half-toned computer graphics presentations. Comm. ACM\u00a013(9), 527\u2013536 (1970)","journal-title":"Comm. ACM"},{"issue":"1","key":"5_CR7","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":"5_CR8","unstructured":"Watkins, G.S.: A real-time visible surface algorithm. Technical Report UTEC-CSc-70-101, Computer Science, University of Utah (June 1970)"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Wylie, C., Romney, G.W., Evans, D.C., Erdahl, A.C.: Halftone perspective drawings by computer. In: Proc. Fall Joint Computer Conference, Washington DC, USA, Thompson Books, pp. 49\u201358 (1967)","DOI":"10.1145\/1465611.1465619"},{"key":"5_CR10","unstructured":"D\u00e9vai, F.: On the computational requirements of virtual reality systems. In: Eurographics\u201997 State of the Art Reports, pp. 59\u201392 (September 1997)"},{"key":"5_CR11","volume-title":"Interactive Computer Graphics: A Top-Down Approach Using OpenGL","author":"E. Angel","year":"2006","unstructured":"Angel, E.: Interactive Computer Graphics: A Top-Down Approach Using OpenGL, 4th edn. Addison-Wesley, Reading (2006)","edition":"4"},{"key":"5_CR12","volume-title":"Computer Graphics: Principles and Practice","author":"J.D. Foley","year":"1996","unstructured":"Foley, J.D., van Dam, A., Feiner, S.K., Hughes, J.F.: Computer Graphics: Principles and Practice, 2nd edn in C. Addison-Wesley, Reading (1996)","edition":"2"},{"key":"5_CR13","volume-title":"Computer Graphics with OpenGL","author":"D. Hearn","year":"2004","unstructured":"Hearn, D., Baker, P.: Computer Graphics with OpenGL, 3rd edn. Prentice-Hall, Englewood Cliffs (2004)","edition":"3"},{"issue":"3","key":"5_CR14","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.F.: On visible surface generation by a priori tree structures. Siggraph Comput. Graph.\u00a014(3), 124\u2013133 (1980)","journal-title":"Siggraph Comput. Graph."},{"key":"5_CR15","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 & Computational Geometry\u00a05, 485\u2013503 (1990)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0925-7721(97)00008-4","volume":"8","author":"M. Berg de","year":"1997","unstructured":"de Berg, M., de Groot, M., Overmars, M.H.: New results on binary space partitions in the plane. Comput. Geom.\u00a08, 317\u2013333 (1997)","journal-title":"Comput. Geom."},{"issue":"2","key":"5_CR17","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(2), 307\u2013325 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00454-003-2921-x","volume":"30","author":"C.D. T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: A note on binary plane partitions. Discrete & Computational Geometry\u00a030(1), 3\u201316 (2003)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF02187734","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H.: The upper envelope of piecewise linear functions: Tight bounds on the number of faces. Discrete & Computational Geometry\u00a04, 337\u2013343 (1989)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J., Sharir, M.: The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry\u00a04, 311\u2013336 (1989)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02187732","volume":"4","author":"J. Pach","year":"1989","unstructured":"Pach, J., Sharir, M.: The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis. Discrete & Computational Geometry\u00a04, 291\u2013309 (1989)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR22","first-page":"187","volume-title":"SODA\u201994: Proc. 5th Annu. ACM-SIAM Symp. on Discrete Algorithms","author":"Y. Matias","year":"1994","unstructured":"Matias, Y., Vitter, J.S., Young, N.E.: Approximate data structures with applications. In: SODA\u201994: Proc. 5th Annu. ACM-SIAM Symp. on Discrete Algorithms, pp. 187\u2013194. ACM Press, New York (1994)"},{"issue":"3","key":"5_CR23","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s004530010040","volume":"28","author":"J.H. Reif","year":"2000","unstructured":"Reif, J.H., Tate, S.R.: Fast spatial decomposition and closest pair computation for limited precision input. Algorithmica\u00a028(3), 271\u2013287 (2000)","journal-title":"Algorithmica"},{"issue":"3","key":"5_CR24","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/231731.231735","volume":"15","author":"S. Fortune","year":"1996","unstructured":"Fortune, S., Wyk, C.J.V.: Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Trans. Graph\u00a015(3), 223\u2013248 (1996)","journal-title":"ACM Trans. Graph"},{"issue":"1","key":"5_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1023\/A:1009934225596","volume":"6","author":"M.L. Gavrilova","year":"2000","unstructured":"Gavrilova, M.L., Ratschek, H., Rokne, J.G.: Exact computation of Delaunay and power triangulations. Reliable Computing\u00a06(1), 39\u201360 (2000)","journal-title":"Reliable Computing"},{"issue":"12","key":"5_CR26","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1016\/S0010-4485(00)00050-6","volume":"32","author":"M.L. Gavrilova","year":"2000","unstructured":"Gavrilova, M.L., Rokne, J.G.: Reliable line segment intersection testing. Computer-Aided Design\u00a032(12), 737\u2013745 (2000)","journal-title":"Computer-Aided Design"},{"issue":"3","key":"5_CR27","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"48","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci.\u00a048(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"5_CR28","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. J. Algorithms\u00a050(1), 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"5_CR29","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"D.E. Willard","year":"2000","unstructured":"Willard, D.E.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput.\u00a029(3), 1030\u20131049 (2000)","journal-title":"SIAM J. Comput."},{"key":"5_CR30","first-page":"80","volume-title":"Proc. 15th ACM Symposium on Theory of Computing","author":"M. Ben-Or","year":"1983","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th ACM Symposium on Theory of Computing, pp. 80\u201386. ACM Press, New York (1983)"},{"key":"5_CR31","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":"5_CR32","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."},{"key":"5_CR33","volume-title":"The Intel Microprocessors","author":"B.B. Brey","year":"2003","unstructured":"Brey, B.B.: The Intel Microprocessors, 6th edn. Prentice-Hall, Englewood Cliffs (2003)","edition":"6"},{"key":"5_CR34","volume-title":"Computer Architecture: A Quantitative Approach","author":"D. Goldberg","year":"2003","unstructured":"Goldberg, D.: Appendix H: Computer arithmetic. In: Hennessy, J.L., Patterson, D.A. (eds.) Computer Architecture: A Quantitative Approach, 3rd edn. Morgan Kaufmann, San Francisco (2003), www.mkp.com\/CA3\/","edition":"3"},{"issue":"3","key":"5_CR35","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett.\u00a06(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications \u2013 ICCSA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74477-1_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T23:06:08Z","timestamp":1684019168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74477-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744757"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74477-1_5","relation":{},"subject":[]}}