TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS

DOI10.1142/S0218195914600085zbMATH Open1331.68253arXiv1309.4323OpenAlexW2951115213MaRDI QIDQ5261016FDOQ5261016

Frank Staals, Vera Sacristán, Maria Saumell, Inês Matos, Rodrigo I. Silveira, Maarten Löffler, Ferran Hurtado

Publication date: 1 July 2015

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Abstract: We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with $m>1$ viewpoints (or guards) located on the terrain surface. A point on the terrain is considered emph{visible} if it has an unobstructed line of sight to at least one viewpoint. We study several natural and fundamental visibility structures: (1) the visibility map, which is a partition of the terrain into visible and invisible regions; (2) the emph{colored} visibility map, which is a partition of the terrain into regions whose points have exactly the same visible viewpoints; and (3) the Voronoi visibility map, which is a partition of the terrain into regions whose points have the same closest visible viewpoint. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting. To the best of our knowledge, the other structures have not been studied before.

Full work available at URL: https://arxiv.org/abs/1309.4323

zbMATH Keywords

visibilitymultiple viewpointsterrains

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Terrain Guarding is NP-Hard
• Power Diagrams: Properties, Algorithms and Applications
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Improved algorithms for discs and balls using power diagrams
• Improved approximation algorithms for geometric set cover
• Corrections to Lee's visibility polygon algorithm
• Ray shooting in polygons using geodesic triangulations
• Improved approximations for guarding 1.5-dimensional terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Efficient hidden surface removal for objects with small union size
• Generalized hidden surface removal

Cited In (4)

• An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization
• Altitude terrain guarding and guarding uni-monotone polygons
• On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
• Visibility with a moving point of view

   Recommendations

• Terrain Visibility with Multiple Viewpoints 👍 👎
• Computing Terrain Multi-visibility Maps for a Set of View Segments Using Graphics Hardware 👍 👎
• Computing visibility on terrains in external memory 👍 👎
• On Voronoi visibility maps of 1.5D terrains with multiple viewpoints 👍 👎
• REGION INTERVISIBILITY IN TERRAINS 👍 👎

This page was built for publication: TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261016)