Visibility Algorithms in the Plane

DOI10.1017/CBO9780511543340zbMath1149.68076OpenAlexW35252975MaRDI QIDQ5444161

Publication date: 22 February 2008

Full work available at URL: https://doi.org/10.1017/cbo9780511543340

Nonnumerical algorithms (68W05) Computing methodologies for image processing (68U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

The partial visibility curve of the Feigenbaum cascade to chaos ⋮ Detection and computation of conservative kernels of models consisting of freeform curves and surfaces, using inequality constraints ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Diffuse reflection diameter in simple polygons ⋮ FO model checking on geometric graphs ⋮ Unnamed Item ⋮ The embracing Voronoi diagram and closest embracing number ⋮ Soft computing methods for WiMAX network planning on 3D geographical information systems ⋮ Routing among convex polygonal obstacles in the plane ⋮ An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ Grid obstacle representation of graphs ⋮ Optimal placement of UV-based communications relay nodes ⋮ Path Counting for Grid-Based Navigation ⋮ A new upper bound for the VC-dimension of visibility regions ⋮ Computing a visibility polygon using few variables ⋮ Randomized approximation algorithms for planar visibility counting problem ⋮ Guarding a Polygon Without Losing Touch ⋮ On rainbow quadrilaterals in colored point sets ⋮ Connecting guards with minimum Steiner points inside simple polygons ⋮ Near optimal line segment queries in simple polygons ⋮ Optimization of mixture models on time series networks encoded by visibility graphs: an analysis of the US electricity market ⋮ Mapping simple polygons: how robots benefit from looking back ⋮ Visibility graphs, dismantlability, and the cops and robbers game ⋮ Optimal Area Polygonization by Triangulation and Visibility Search ⋮ Kernel-based construction operators for Boolean sum and ruled geometry ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ On colourability of polygon visibility graphs ⋮ One-sided terrain guarding and chordal graphs ⋮ Reachable region query and its applications ⋮ On colouring point visibility graphs ⋮ A polygon is determined by its angles ⋮ Incremental Algorithms to Update Visibility Polygons ⋮ Reconstructing visibility graphs with simple robots ⋮ Geometric path problems with violations ⋮ Algorithm 966 ⋮ Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon ⋮ Minimization of the maximum distance between the two guards patrolling a polygonal region ⋮ Simple agents learn to find their way: an introduction on mapping polygons ⋮ Diffuse reflection diameter and radius for convex-quadrilateralizable polygons ⋮ Computational complexity aspects of point visibility graphs ⋮ Online algorithms for searching and exploration in the plane ⋮ Characterizing and recognizing LR-visibility polygons ⋮ Obstacle Numbers of Planar Graphs ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ On the structure of graphs with low obstacle number ⋮ Dynamic Algorithms for Visibility Polygons in Simple Polygons ⋮ Approximate Shortest Paths in Polygons with Violations ⋮ Space-time trade-offs for stack-based algorithms ⋮ Visibility Testing and Counting ⋮ Combinatorics of beacon-based routing in three dimensions ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ A COMPLETE ALGORITHM FOR SEARCHLIGHT SCHEDULING ⋮ Weak visibility queries of line segments in simple polygons and polygonal domains ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ On the Bar Visibility Number of Complete Bipartite Graphs ⋮ Recognition and complexity of point visibility graphs ⋮ An exact algorithm for minimizing vertex guards on art galleries ⋮ Approximation algorithms for art gallery problems in polygons ⋮ A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon ⋮ Computing pseudotriangulations via branched coverings ⋮ Graphs with Large Obstacle Numbers ⋮ Algorithms for Computing Diffuse Reflection Paths in Polygons ⋮ Diffuse reflection radius in a simple polygon ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ Unnamed Item ⋮ On Colourability of Polygon Visibility Graphs ⋮ Point Visibility Graph Recognition is NP-Hard ⋮ A fast shortest path algorithm on terrain-like graphs ⋮ Mapping a polygon with holes using a compass ⋮ An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem ⋮ Reconstructing Visibility Graphs with Simple Robots ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane ⋮ Computing Shortest Paths in the Plane with Removable Obstacles ⋮ Mapping a Polygon with Holes Using a Compass ⋮ Some results on point visibility graphs ⋮ Visibility Graphs of Anchor Polygons ⋮ Walking in Streets with Minimal Sensing ⋮ Visibility testing and counting ⋮ Weak visibility counting in simple polygons ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Walking in streets with minimal sensing ⋮ Approximability of guarding weak visibility polygons