Quadratic bounds for hidden line elimination

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quadratic bounds for hidden line elimination

Full text

Pdf (414 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the second annual symposium on Computational geometry table of contents

Yorktown Heights, New York, United States

Pages: 269 - 275

Year of Publication: 1986

ISBN:0-89791-194-6

Author

F Devai

Computer and Automation Institute, Hungarian Academy of Sciences, P.O. Box 63, Kende utca 13-17, Budapest, Hungary, H-1502

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 24, Citation Count: 9

Additional Information:

references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/10515.10544 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Arthur Appel, The notion of quantitative invisibility and the machine rendering of solids, Proceedings of the 1967 22nd national conference, p.387-393, January 1967, Washington, D.C., United States [doi>10.1145/800196.806007]
	2	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	3	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	4	Chazelle, B., Guibas, L.J., Lee, D.T. The power of geometric duality. Proc. 24th Annual Symp. on Foundations of Comp. Sci. Tucson, Arizona, (Nov. 1983), 217-225.
	5	D~vai, F. Complexity of visibility computations. Dissertation for the degree of Candidate of Sciences. Budapest, Hungary, 1981 (In Hungarian) .
	6	D~vai, F. Complexity of two-dimensional visibility computations. Proc. 3rd European conference on CAD'CAM and computer graphics, Paris, France, (Feb. 1984), MICAD'84 Vol. 3, 827-841.
	7	Edelsbrunner, H., O'Rourke, J., Seidel, R. Constructing arrangements of lines and hyperplanes with applications. Proc. 24th Annual Symp. on Foundations of Comp. Sci. Tucson, Arizona, (Nov. 1983), 83-91.
	8	Forrest, A.R. Computational geometry in practice. NATO ASI Series, Vol. F17, Fundamental Algorithms for Computer Graphics (Ed. R.A. Earnshaw) Springer-Verlag, Berlin 1985, 707-724.
	9	Wm Randolph Franklin, A linear time exact hidden surface algorithm, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.117-123, July 1980
	10	Michael L. Fredman , Bruce Weide, On the complexity of computing the measure of ∪[a_i,b_i], Communications of the ACM, v.21 n.7, p.540-544, July 1978 [doi>10.1145/359545.359553]
	11	R. Galimberti, An algorithm for hidden line elimination, Communications of the ACM, v.12 n.4, p.206-211, April 1969 [doi>10.1145/362912.362921]
	12	Haj6s Gy. Introduction to Geometry. Tank6nyvkida6, Budapest, 1972 (In Hungarian).
	13	Hilbert, D., Cohn-Vossen, S. Geometry and the Imagination. Chelsea Publishing Co., New York, 1952.
	14	Loutrel, P.P. A solution to the hidden-line problem for computer drawn polyhedra. IEEE Trans. Comp. C-19,3 (Mar. 1970), 205-213.
	15	Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
	16	Schmitt, A. Time and space bounds for hidden line and hidden surface algorithms. Proc. EUROGRAPHICS' 81, Darmstadt, FRG, (Sep. 1981), 43-56.
	17	Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
	18	Kevin Weiler , Peter Atherton, Hidden surface removal using polygon area sorting, ACM SIGGRAPH Computer Graphics, v.11 n.2, p.214-222, Summer 1977
	19	Welzl, E. Constructing the visibility graph for n line segments in O(n2) time. Information Processing Lett. 20 (1985), 167-171.

CITED BY 9

	Leila De Floriani , Paola Magillo, Algorithms for visibility computation on digital terrain models, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.380-387, February 14-16, 1993, Indianapolis, Indiana, United States
	Jeff Erickson, Finite-resolution hidden surface removal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.901-909, January 09-11, 2000, San Francisco, California, United States
	Mark H. Overmars , Micha Sharir, Merging visibility maps, Proceedings of the sixth annual symposium on Computational geometry, p.168-176, June 07-09, 1990, Berkley, California, United States
	Matthew J. Katz , Mark H. Overmars , Micha Shairr, Efficient hidden surface removal for objects with small union size, Proceedings of the seventh annual symposium on Computational geometry, p.31-40, June 10-12, 1991, North Conway, New Hampshire, United States
	Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987
	Franco P. Preparata , Jeffrey S. Vitter , Mariette Yvinec, Computation of the axial view of a set of isothetic parallelepipeds, ACM Transactions on Graphics (TOG), v.9 n.3, p.278-300, July 1990
	P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proceedings of the fifth annual symposium on Computational geometry, p.315-325, June 05-07, 1989, Saarbruchen, West Germany
	Micha Sharir , Mark H. Overmars, A simple output-sensitive algorithm for hidden surface removal, ACM Transactions on Graphics (TOG), v.11 n.1, p.1-11, Jan. 1992
	Todd Keeler , John Fedorkiw , Sherif Ghali, The spherical visibility map, Computer-Aided Design, v.39 n.1, p.17-26, January, 2007