Efficient hidden surface removal for objects with small union size

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient hidden surface removal for objects with small union size

Full text

Pdf (977 KB)

Source

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

North Conway, New Hampshire, United States

Pages: 31 - 40

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Matthew J. Katz	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Mark H. Overmars	Department of Computer Science, Utrecht University, P. O. Box 80.089, 3508 TB Utrecht, the Netherlands
Micha Shairr	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel, and Courant Institute of Mathematical Sciences, New York University, New York, NY

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): 0, Downloads (12 Months): 8, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/109648.109652 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	P.K. Agarwal and M. Sharir, Applications of a new space partitioning technique, manuscript (1991).
	2	Marshall Bern, Hidden surface removal for rectangles, Journal of Computer and System Sciences, v.40 n.1, p.49-69, February 1990 [doi>10.1016/0022-0000(90)90018-G]
	3	J.L. Bentley and T.A. Ottmann, Algorithms for reporting and counting geometric intersections, IEEE Trans. Computers 28 (1979), 643-647.
	4	M.T. de Berg and M.H. Overmars, Hidden surface removal for axis-parallel polyhedra, Prec. 31st {EEE Symp. on Foundations of Computer Science, 1990, pp. 252-261.
	5	R. Chazelle, H. Edel~brunner, L. Guibas, R_ pollack, R. Seidel, M. Sharir and J. Snoeyink, Counting and cutting cycles of lines and rods in space, Prec. 31st IEEE Syrup. on Foundatzons of Computer Science, 1990, pp. 242-251.
	6	Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
	7	F Devai, Quadratic bounds for hidden line elimination, Proceedings of the second annual symposium on Computational geometry, p.269-275, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10544]
	8	M.T. Goodrich, A polygonal approach to hidden line elimination, Prec. 25th A llerton Conf. on Communication, Control and Computzng, 1987, pp. 849-858.
	9	Michael T. Goodrich , Mikhail J. Atallah , Mark H. Overmars, An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.689-702, July 1990, Warwick University, England
	10	Ralf Hartmut Güting , Thomas Ottmann, New algorithms for special cases of the hidden line elimination problem, Computer Vision, Graphics, and Image Processing, v.40 n.2, p.188-204, November 1, 1987 [doi>10.1016/S0734-189X(87)80114-7]
	11	Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
	12	H. Mairson and J. Stolfi, Reporting and counting intersections between two sets of line segments, Theoretical Foundations of Computer Graphzcs and CAD, R.A. Earnshaw, Ed., N ATO ASI Series, Vol F-40, Springer Verlag, 1988, pp. 307-326.
	13	J. Matou~ek, J. Pach, M. Sharir, S. Sifrony and E. Welzl, Fat triangles determine linearly many holes, Tech. Report 174/90, Eskenasy Institute of Computer Sciences, Tel Aviv University, May 1990.
	14	Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
	15	K. Mulmuley, An efficient algorithm for hidden surface removal, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.379-388, July 1989
	16	Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
	17	M.H. Overmars and M. Sharir, Output-sensitive hidden surface removal, Pr'oc. 30th IEEE gymp on Foundations of Computer Science, 1989. pp 59S- 603.
	18	M.H. Overmars and M. Sharir, An improved technique for output-sensitive hidden surface removal, Techn. Rept. RUU-CS-89-32, Dept. of Computer Science, Utrecht University, 1989.
	19	Mark H. Overmars , Micha Sharir, Merging visibility maps, Computational Geometry: Theory and Applications, v.1 n.1, p.35-49, July 1991 [doi>10.1016/S0925-7721(99)00057-7]
	20	M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
	21	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	22	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 [doi>10.1145/78964.78967]
	23	J. H. Reif , S. Sen, An efficient output-sensitive hidden surface removal algorithm and its parallelization, Proceedings of the fourth annual symposium on Computational geometry, p.193-200, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73413]
	24	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 [doi>10.1145/102377.112141]
	25	A. Schmitt, Time and space bounds for hidden line and hidden surface algorithms, Eurographics '81, pp. 43-56.
	26	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]

CITED BY 4

	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
	Mark de Berg , Mark Overmars , Otfried Schwarzkopf, Computing and verifying depth orders, Proceedings of the eighth annual symposium on Computational geometry, p.138-145, June 10-12, 1992, Berlin, Germany
	Leila De Floriani , Paola Magillo, Visibility Computations on Hierarchical Triangulated Terrain Models, Geoinformatica, v.1 n.3, p.219-250, October 1997
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States