A worst-case efficient algorithm for hidden-line elimination Footnote^†

†This work was carried out under NATO Grant No. RG 155.81; the work of the first and second authors was additicinally supported by a grant from the Deutsche Forschungsgemeinschaft DFG, and the work of the third author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.

References

• Adelson-Velskii , G. M. and Landis , Y. M. 1962 . An algorithm for the organization of information . Dokl. Akad. Nauk. SSSR , 146 : 263 – 266 .
   Google Scholar
• Beatty , J. C. , Booth , K. S. and Matthies , L. H. 1981 . Seventh Canadian Man-Computer Communications Society Conference . Revisiting Watkins’ algorithm . June 1981 . pp. 359 – 370 .
   Google Scholar
• Bentley J. L. Solutions to Klee's rectangle problems 1977 unpublished manuscript
   Google Scholar
• Bentley , J. L. and Ottmann , Th. 1979 . Algorithms for reporting and counting geometric intersections . IEEE Transactions on Computers , C-28 June : 643 – 647 .
   Web of Science ®Google Scholar
• Bentley , J. L. and Wood , D. 1980 . An optimal worst-case algorithm for reporting intersections of rectangles . IEEE Transactions on Computers , C-29 June : 571 – 577 .
   Web of Science ®Google Scholar
• Brown , K. Q. 1981 . Algorithms for reporting and counting geometric intersections . IEEE Transactions on Computers , C-30 June : 147 – 148 .
   Google Scholar
• Chazelle B. Reporting and counting arbitrary planar intersections Technical Report CS-83-16 Brown University Computer Science 1983
   Google Scholar
• Edelsbrunner H. Dynamic data structures for orthogonal intersection queries, Institut fur Informationsverarbeitung Graz, Report No. 59 Technische Universität 1980
   Google Scholar
• Edelsbrunner , H. and Overmars , M. H. 1982 . On the equivalence of some rectangle problems . Information Processing Letters , 14 : 124 – 127 .
   Web of Science ®Google Scholar
• Edelsbrunner , H. , Overmars , M. H. and Wood , D. 1983 . Graphics in Flatland, a case study , Edited by: Preparata , F. P. Vol. 1 , 35 – 59 . Advances in Computing Research .
   Google Scholar
• Foley , J. D. and Van Dam , A. 1982 . Fundamentals of Interactive Computer Graphics , Reading, Mass : Addison-Wesley Publishing Co .
   Google Scholar
• Franklin , W. R. 1980 . SIGGRAPH ’ 80 Conference Proceedings, Computer Graphics . A linear time exact hidden surface algorithm . 1980 . pp. 117 – 123 .
   Google Scholar
• Fredman , M. L. 1981 . A lower bound on the complexity of orthogonal range queries . Journal of the ACM , 28 : 696 – 705 .
   Google Scholar
• Giiting R. H. Ottmann Th. New algorithms for special cases of the hidden line elimination problem Technical Report 184 Universitä t Dortmund 1984
   Google Scholar
• Hamlin , G. Jr. and Gear , C. W. 1981 . Proceedings of the ACM SIGRAPH ’ 77Conference . Raster-Scan hidden surface algorithm techniques . 1981 . pp. 206 – 213 .
   Google Scholar
• Hubschman , H. and Zucker , S. W. 1981 . Frame-to-frame coherence and the hidden surface computation, constraints for a convex world . Computer Graphics , 15 : 45 – 54 .
   Google Scholar
• Lauther , U. 1981 . Proceedings 18th Design Automation Conference . An 0(N log N) Algorithm for Boolean mask operations . 1981 , Nashville. pp. 555 – 562 .
   Google Scholar
• Lee , D. T. and Preparata , F. P. 1982 . Private communication
   Google Scholar
• Newman , W. and Sproull , R. 1979 . Principles of Interactive Computer Graphics , New York : Mc Graw-Hill . 2nd edition
   Google Scholar
• Nievergelt , J. and Preparata , F. P. 1982 . Plane-sweep algorithms for intersecting geometric figures . Communications of the ACM , 25 : 739 – 747 .
   Web of Science ®Google Scholar
• Nievergelt , J. and Reingold , E. M. 1973 . Binary search trees of bounded balance . SI AM Journal on Computing , 2 : 33 – 43 .
   Google Scholar
• Nurmi , O. 1984 . A fast line-sweep algorithm for hidden line elimination . BIT , to appear
   Google Scholar
• Ottmann , Th. and Widmayer , P. 1984 . Solving visibility problems by using skeleton structures . Proceedings of MFCS ’ 84 Springer-Verlag Lecture Notes in Computer Science , 176 : 459 – 470 .
   Web of Science ®Google Scholar
• Ottmann , Th. , Widmayer , P. and Wood , D. 1984 . A fast algorithm for the Boolean masking problem . Computer Vision, Graphics, and Image Processing , 30 : 249 – 268 .
   Google Scholar
• Rappaport , D. 1982 . Proceedings of the 20th Allerton Conference on Communication, Control and Computing . Eliminating hidden lines from monotone slabs . 1982 . pp. 43 – 52 .
   Google Scholar
• Schmitt A. On the time and space complexity of certain exact hidden line algorithms Fakultä t fur Informatik, Report No. 24/81 Universitat Karlsruhe 1981
   Google Scholar
• Schmitt , A. 1982 . Personal communication
   Google Scholar
• Sechrest S. Master's thesis Cornell University 1981
   Google Scholar
• Sechrest , S. and Greenberg , D. 1981 . Proceedings of the ACM SIGRAPH ’81 Conference . A visible polygon reconstruction algorithm . 1981 . pp. 17 – 28 .
   Google Scholar
• Sutherland , I. E. , Sproull , R. F. and Schumacker , R. A. 1974 . A characterization of ten hidden-surface algorithms . Computing Surveys , 6 1 – 55 .
   Google Scholar
• Swart G. Ladner R. Efficient algorithms for reporting intersections Technical Report no. 83-0703 Computer Science Department, University of Washington Seattle 1983
   Google Scholar
• Tilove , B. 1980 . Set membership classification, a unified approach to geometric intersection problems . IEEE Transactions on Computers , C-29 874 – 883 .
   Google Scholar
• Vaishnavi , V. K. and Wood , D. 1982 . Rectilinear line segment intersection, layered segment trees and dynamization . Journal of Algorithms , 3 160 – 176 .
   Google Scholar