Article

Free access

Visibility with a moving point of view

Authors:

Marshall Bern,

David Dobkin,

David Eppstein,

Robert GrossmanAuthors Info & Claims

SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms

Pages 107 - 117

Published: 01 January 1990 Publication History

PDF eReader

References

[1]

M.J. Atallah, Dynamic Computational Geometry, Proc. 24~h IEEE Foundations of Comp. Science, 1983, 92-99.

Google Scholar

[2]

J.L. Bentley and T. A. Ottmann, Algorithms for Reporting and Counting Geometric Intersections, IEEE Trans. on Computers 28 ( 979), 64 -647.

Digital Library

Google Scholar

[3]

R. Cole and M. Sharir, Visibility Problems for PolyhedraJ Terrains, J. Symbolic Computation 7 (1989), 11-30.

Digital Library

Google Scholar

[4]

J.R. Driscoll, N. Sarnak, D. Sleator, and R. E. Tarjan, Making Data Structures Persistent, Proc. 18th A CM Syrup. on Theory of Computing, 1986, 109-121.

Digital Library

Google Scholar

[5]

H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing Arrangemenfs of Lines and Hyperplanes with Applications, SIAM J. Cornputing 15 (1986), 341-363.

Digital Library

Google Scholar

[6]

tt. Fuchs, Z. M. Kedem, and B. F. Naylot, On Visible Surface Generation by A Prior~ Tree Structures, Computer Graphics 14 (1980), 124-133.

Digital Library

Google Scholar

[7]

S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel Sequences and of GeneraJized Path Compression Schemes, Combinatorica 6 (1986), 151-177.

Digital Library

Google Scholar

[8]

H. Hubschman and S. Zucker, Frame-to- Frame Coherence and the Hidden Surface Computation: Constraints /'or a Convex World, Computer Graphics 15 (August 1981), 45-54.

Digital Library

Google Scholar

[9]

J.W. Jaromczyk and M. Kowaluk, Skewed Projections with an Application to Line Stabbing in Rz, Proc. ~th A CM Syrup. on Comp. Geometry, 1988, 362-370.

Digital Library

Google Scholar

[10]

D.T. Lee and F. P. Preparata, Location of a Point in a Planar Subdivision and its Applications, SIAM J. on Computing 6 (1977), 594-606.

Google Scholar

[11]

G.L. Miller and 3. H. Reif, Parallel Tree Contraction and its Applications, Proc. 26th IEEE Foundations of Comp. Science, 1985, 478-489.

Google Scholar

[12]

K. Mulmuley, A Fast Planar Partition Algorithm, I, Proc. 29th IEEE Foundations of Comp. Science, 1988, 580-589.

Google Scholar

[13]

K. Mulmuley, On Obstructions in Relation to a Fixed Viewpoint, Proc. 30th IEEE Foundations of Comp. Science, 1989.

Google Scholar

[14]

M. Paterson and F. F. Yao, Binary Partitions wi~h AppIications to Hidden Surface Removal and Solid Modelling, Proc. 5th A CM Syrup. on Comp. Geometry, 1989, 23-32.

Digital Library

Google Scholar

[15]

W.H. Plantinga and C. R. Dyer, An Algorithm for Constructing the Aspect Graph, Proc. 27th IEEE Foundations of Comp. Science, 1986, 123-131.

Google Scholar

[16]

W.H. Plantinga, C. R. Dyer, and B. Scales, Real-time Hidden-Line Elimination for a Rotating Polyhed~M Scene Using tile Aspect Representation, manuscript, 1988.

Google Scholar

[17]

F.P. Preparata and M. I. Shamos, Computational Geometry: An introduction, Springer- Verlag, 1985.

Digital Library

Google Scholar

[18]

F.P. Preparata and R. Tamassia, Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures, Proc. 29th IEEE Foundations of Comp. Science, 1988, 558-567.

Google Scholar

[19]

J.H. Reif and S. Sen, An Efficient Output- Sensitive Hidden-Surface Removal Algorithm and its Parallelization, Proc. 4th A CM Syrup. on Comp. Geometry, 1988, 194-200.

Digital Library

Google Scholar

[20]

i. E. Sutherland, R. F. Sproull, and R. A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, Computing Surveys 6 (1974), 1-25.

Digital Library

Google Scholar

[21]

G.R. Swart, A Schema for Real Time Hidden Line Removal, Tech. Report, Dept. of Computer Science, U. of Washington, 1984.

Google Scholar

Cited By

View all

Moet EKnauer Cvan Kreveld M(2008)Visibility maps of segments and triangles in 3DComputational Geometry: Theory and Applications10.1016/j.comgeo.2006.11.00139:3(163-177)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.comgeo.2006.11.001
Moet EKnauer Cvan Kreveld M(2006)Visibility maps of segments and triangles in 3dProceedings of the 6th international conference on Computational Science and Its Applications - Volume Part I10.1007/11751540_3(20-29)Online publication date: 8-May-2006
https://dl.acm.org/doi/10.1007/11751540_3
Ghali SStewart AWhitesides S(1996)Maintenance of the set of segments visible from a moving viewpoint in two dimensionsProceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237423(503-504)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237423
Show More Cited By

Index Terms

Visibility with a moving point of view

Recommendations

Query point visibility computation in polygons with holes

In this paper, we consider the problem of computing the visibility of a query point inside polygons with holes. The goal is to perform this computation efficiently per query considering the cost of the preprocessing phase. Our algorithm is based on ...
Efficient computation of query point visibility in polygons with holes
SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

In this paper, we consider the problem of computing the visibility of a query point inside polygons with holes. The goal is to perform this computation efficiently per query with more cost in the preprocessing phase. Our algorithm is based on solutions ...
Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
Abstract
We devise an algorithm for maintaining the visibility polygon of any query point in a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the data structures that ... $_{^{}} {^{}}^{}$ ${^{}}^{}_{^{}}$ $_{^{}}$ $^{}$ $^{}$ $^{}$ $^{}$ $_{^{}}$ $^{}$ $_{^{}}$ $_{^{}}$ $_{^{}}$ ${^{}}^{}$ ${^{}}^{}$ $^{}$ $^{}$ $^{}$ $^{}$ $^{}$

Comments

Information & Contributors

Information

Published In

SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms

January 1990

522 pages

ISBN:0898712513

Chairman:
David Johnson

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1990

Check for updates

Qualifiers

Article

Conference

SODA90

Sponsor:

SIGACT

SODA90: ACM/SIGACT-SIAM Symposium on Discrete Algorithm

January 22 - 24, 1990

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
394
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)4

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moet EKnauer Cvan Kreveld M(2008)Visibility maps of segments and triangles in 3DComputational Geometry: Theory and Applications10.1016/j.comgeo.2006.11.00139:3(163-177)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.comgeo.2006.11.001
Moet EKnauer Cvan Kreveld M(2006)Visibility maps of segments and triangles in 3dProceedings of the 6th international conference on Computational Science and Its Applications - Volume Part I10.1007/11751540_3(20-29)Online publication date: 8-May-2006
https://dl.acm.org/doi/10.1007/11751540_3
Ghali SStewart AWhitesides S(1996)Maintenance of the set of segments visible from a moving viewpoint in two dimensionsProceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237423(503-504)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237423
Mulmuley KKoutsougeras CVitter J(1991)Hidden surface removal with respect to a moving view pointProceedings of the twenty-third annual ACM symposium on Theory of Computing10.1145/103418.103471(512-522)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/103418.103471
Pellegrini MSeidel R(1990)Stabbing and ray shooting in 3 dimensional spaceProceedings of the sixth annual symposium on Computational geometry10.1145/98524.98563(177-186)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/98524.98563

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Query point visibility computation in polygons with holes

Efficient computation of query point visibility in polygons with holes

Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane