Approximation algorithms for terrain guarding

No abstract is available for this paper.

• Publication year

  2002

• Venue

  Information Processing Letters

• Publication date

  2002-04-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0020-0190(01)00255-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computational Geometry: Algorithms and Applications, Second Edition

  2000cited by this paper
• Art Gallery and Illumination Problems

  2000cited by this paper
• (In-)Approximability of visibility problems on polygons and terrains

  2000cited by this paper
• Inapproximability of some art gallery problems

  1998cited by this paper
• Inapproximability Results for Guarding Polygons without Holes

  1998cited by this paper
• Positioning Guards at Fixed Height Above a Terrain - An Optimum Inapproximability Result

  1998cited by this paper
• Guarding Polyhedral Terrains

  1997cited by this paper
• Computing the Shortest Watchtower of a Polyhedral Terrain in O(n Log N) Time

  1997cited by this paper
• Improved Low-Degree Testing and its Applications

  1997cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• Digital Elevation Models and TIN Algorithms

  1996cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Visibility Algorithms on Triangulated Digital Terrain Models

  1994cited by this paper
• Recent Results in Art Galleries

  1992cited by this paper
• Recent results in art galleries (geometry)

  1992cited by this paper
• Art gallery theorems and algorithms

  1987cited by this paper
• Computational complexity of art gallery problems

  1986cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper

• 3D visibility analysis of urban parks using LIDAR for enhanced accuracy

  2025cites this paper
• Effect of Boundary Approximation on Visibility

  2021cites this paper
• Covering geometric domains

  2021cites this paper
• Efficient Viewshed Computation Algorithms On GPUs and CPUs

  2020cites this paper
• On guarding real terrains: The terrain guarding and the blocking path problems

  2020cites this paper
• Mapping 3D visibility in an urban street environment from mobile LiDAR point clouds

  2020cites this paper
• Algorithms for Tower Placement on Terrain

  2019cites this paper
• Covering 1.5D Terrain by Common Height Towers

  2018cites this paper
• Altitude Terrain Guarding and Guarding Uni-Monotone Polygons

  2018cites this paper
• A new algorithm for viewshed computation on raster terrain

  2018cites this paper
• A finite dominating set of cardinality O(k) and a witness set of cardinality O(n) for 1.5D terrain guarding problem

  2017cites this paper
• Optimisation of numbers, types, and locations of wireless sensors with communication, finite supply, and multiple-sensor coverage constraints

  2017cites this paper
• Terrain visibility and guarding problems

  2017cites this paper
• Two-stage automated measurement process for high-resolution 3D digitization of unknown objects.

  2016cites this paper
• An Efficient External Memory Algorithm for Terrain Viewshed Computation

  2016influential citation
• The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS

  2015influential citation
• A PTAS for the Continuous 1.5D Terrain Guarding Problem

  2014cites this paper
• Voxel based volumetric visibility analysis of urban environments

  2013cites this paper
• The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm

  2013cites this paper
• Geometric covering

  2013influential citation
• Towards Semantic Trajectory Outlier Detection

  2013cites this paper
• Combinatorial Optimization Problems in Geometric Settings

  2013cites this paper
• Genetic algorithm and pure random search for exosensor distribution optimisation

  2012cites this paper
• Optimal sensor placement with signal propagation effects and inhomogeneous coverage preferences

  2011cites this paper
• Efficient viewshed computation on terrain in external memory

  2011cites this paper
• An exact algorithm for minimizing vertex guards on art galleries

  2011cites this paper
• Approximation Algorithms for Art Gallery Problems in Polygons and Terrains

  2010influential citation
• Optimal placement of multiple types of communicating sensors with availability and coverage redundancy constraints

  2010influential citation
• Generalized Watchman Route Problem with Discrete View Cost

  2010influential citation
• Approximation algorithms for art gallery problems in polygons

  2010cites this paper
• Study on Art Gallery Based on 4-coloring

  2009cites this paper
• A Complete Bibliography of Publications in Information Processing Letters: 2000-2009

  2009cites this paper
• Algoritmo eficiente para cálculo de mapas de visibilidade em terrenos armazenados em memória externa

  2009cites this paper
• On the influence of problem definition in sensor placement optimization

  2009cites this paper
• Survey and analysis of multimodal sensor planning and integration for wide area surveillance

  2009cites this paper
• Towards Optimal Positioning of Surveillance UGVs

  2009influential citation
• An Exact Algorithm for an Art Gallery Problem

  2009cites this paper
• Study on Art Gallery Based on 4-coloring

  2009cites this paper
• On fast exploration in 2D and 3D terrains with multiple robots

  2009cites this paper
• On reduced time fault tolerant paths for multiple UAVs covering a hostile terrain

  2008influential citation
• Covering hostile terrains with partial and complete visibilities: On minimum distance paths

  2008cites this paper
• Optimal positioning of surveillance UGVs

  2008influential citation
• Optimal sensor placement with terrain-based constraints and signal propagation effects

  2008cites this paper
• Experimental Evaluation of an Exact Algorithm for the Orthogonal Art Gallery Problem

  2008cites this paper
• Efficient viewshed computation on terrains in external memory

  2008cites this paper
• An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem

  2007cites this paper
• A Constant-Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding

  2007cites this paper
• Coverage optimization to support security monitoring

  2007cites this paper
• Geometric optimization and querying: exact & approximate

  2007cites this paper
• Survey of Positioning Algorithms for Surveillance UGVs

  2007cites this paper
• Sensor configuration for coverage optimization for surveillance applications

  2007cites this paper
• An Efficient Algorithm to Compute the Viewshed on DEM Terrains Stored in the External Memory

  2007cites this paper
• Geometric optimization and querying : exact & approximate

  2007cites this paper
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains

  2006cites this paper
• Finding minimum hidden guard sets in polygons - tight approximability results

  2006cites this paper
• Power-efficient sensor placement and transmission structure for data gathering under distortion constraints

  2006cites this paper
• On Visibility Problems in the Plane -- Solving Minimum Vertex Guard Problems by Successive Approximations

  2006cites this paper
• Geometric Facility Location Optimization Thesis

  2005cites this paper
• Energy-aware stage illumination

  2005cites this paper
• Approximative terrain guarding with given number of guards

  2005cites this paper
• A constant-factor approximation algorithm for optimal terrain guarding

  2005cites this paper
• An Optimal New Algorithm for Guarding TIN '

  2005cites this paper
• K-guarding of polyhedral terrain

  2004cites this paper
• Peer Reviewed Title: Power-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints Author:

  2004cites this paper
• A NEW ALGORITHM FOR GUARDING TRIANGULATED IRREGULAR NETWORKS

  2004cites this paper
• Comparing Probabilistic Heuristics for Guarding

  2004cites this paper
• Power-efficient sensor placement and transmission structure for data gathering under distortion constraints

  2004cites this paper
• Comparing probabilistic heuristics for guarding polyhedral terrain

  2004cites this paper
• Approximation Algorithms to Minimum Vertex Cover Problems on Polygons and Terrains

  2003influential citation
• Guarding galleries and terrains

  2002cites this paper
• Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains

  2002cites this paper