Article

An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal

Authors:

Michael T. Goodrich,

Mikhail J. Atallah,

Mark H. OvermarsAuthors Info & Claims

Proceedings of the seventeenth international colloquium on Automata, languages and programming

Pages 689 - 702

Published: 01 July 1990 Publication History

Abstract

No abstract available.

Cited By

View all

de Berg MYap C(1993)Generalized hidden surface removalProceedings of the ninth annual symposium on Computational geometry10.1145/160985.160987(1-10)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/160985.160987
Sharir MOvermars M(1992)A simple output-sensitive algorithm for hidden surface removalACM Transactions on Graphics10.1145/102377.11214111:1(1-11)Online publication date: 2-Jan-1992
https://dl.acm.org/doi/10.1145/102377.112141
Katz MOvermars MShairr MDrysdale R(1991)Efficient hidden surface removal for objects with small union sizeProceedings of the seventh annual symposium on Computational geometry10.1145/109648.109652(31-40)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/109648.109652
Show More Cited By

Index Terms

An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

An Input-Size/Output-Size Trade-Off in the Time-Complexity of Rectilinear Hidden Surface Removal (Preliminary Version)
ICALP '90: Proceedings of the 17th International Colloquium on Automata, Languages and Programming
Hidden surface removal using polygon area sorting

A polygon hidden surface and hidden line removal algorithm is presented. The algorithm recursively subdivides the image into polygon shaped windows until the depth order within the window is found. Accuracy of the input data is preserved.The approach is ...
A simple output-sensitive algorithm for hidden surface removal

We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map, the method runs in time O(n √k ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the seventeenth international colloquium on Automata, languages and programming

July 1990

780 pages

ISBN:0387528261

Editor:
Michael S. Paterson
Univ. of Warwick, Warwick, UK

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 1990

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

de Berg MYap C(1993)Generalized hidden surface removalProceedings of the ninth annual symposium on Computational geometry10.1145/160985.160987(1-10)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/160985.160987
Sharir MOvermars M(1992)A simple output-sensitive algorithm for hidden surface removalACM Transactions on Graphics10.1145/102377.11214111:1(1-11)Online publication date: 2-Jan-1992
https://dl.acm.org/doi/10.1145/102377.112141
Katz MOvermars MShairr MDrysdale R(1991)Efficient hidden surface removal for objects with small union sizeProceedings of the seventh annual symposium on Computational geometry10.1145/109648.109652(31-40)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/109648.109652
Overmars MSharir MSeidel R(1990)Merging visibility mapsProceedings of the sixth annual symposium on Computational geometry10.1145/98524.98561(168-176)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/98524.98561
Goodrich MGhouse MBright JLeighton F(1990)Generalized sweep methods for parallel computational geometryProceedings of the second annual ACM symposium on Parallel algorithms and architectures10.1145/97444.97695(280-289)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/97444.97695

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

An Input-Size/Output-Size Trade-Off in the Time-Complexity of Rectilinear Hidden Surface Removal (Preliminary Version)

Hidden surface removal using polygon area sorting

A simple output-sensitive algorithm for hidden surface removal

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations