TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS

DOI10.1142/S0218195914600085zbMATH Open1331.68253OpenAlexW2951115213MaRDI QIDQ5261016FDOQ5261016

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

Publication date 1 July 2015

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

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)

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.

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

Cites work

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

Cited in

(10)

• Computing Terrain Multi-visibility Maps for a Set of View Segments Using Graphics Hardware
• Terrain visibility with multiple viewpoints
• Computing visibility on terrains in external memory
• REGION INTERVISIBILITY IN TERRAINS
• On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
• An efficient algorithm for the 1D total visibility-index problem
• An efficient algorithm for the 1D total visibility-index problem and its parallelization
• Altitude terrain guarding and guarding uni-monotone polygons
• Visibility with a moving point of view
• On characterizing terrain visibility graphs

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)