scientific article

zbMath0653.52001MaRDI QIDQ3799261

Publication date: 1987

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

monotone triangulation decomposition computational geometry star-shaped polygons spiral visibility graphs art gallery theorems convex partitioning algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Polyhedra and polytopes; regular figures, division of spaces (51M20) Other problems of combinatorial convexity (52A37) Graph theory (05C99) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02) Designs and configurations (05B99)

Related Items (only showing first 100 items - show all)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Extension to Even Triangulations ⋮ Unnamed Item ⋮ Graphics in flatland revisited ⋮ Universal Guard Problems ⋮ Two-floodlight illumination of convex polygons ⋮ On the complexity of approximating and illuminating three-dimensional convex polyhedra ⋮ Computing a shortest watchman path in a simple polygon in polynomial-time ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons ⋮ A short proof of the non-biplanarity of $K_9$ ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ Visibility-based pursuit-evasion in a polygonal environment ⋮ On hamiltonian triangulations in simple polygons (Extended Abstract) ⋮ Analysis of Spatial and Spatiotemporal Anomalies Using Persistent Homology: Case Studies with COVID-19 Data ⋮ Guarding a Polygon Without Losing Touch ⋮ Triangle-Based Heuristics for Area Optimal Polygonizations ⋮ Minimizing visible edges in polyhedra ⋮ On the general position numbers of maximal outerplane graphs ⋮ The dispersive art gallery problem ⋮ A Multi-level Optimization Approach for the Planning of Heterogeneous Sensor Networks ⋮ Optimal Sensor Positioning; A Probability Perspective Study ⋮ On $r$-guarding SCOTs -- a new family of orthogonal polygons ⋮ On the complexity of half-guarding monotone polygons ⋮ On Some City Guarding Problems ⋮ Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Guarding Art Galleries: The Extra Cost for Sculptures Is Linear ⋮ On colourability of polygon visibility graphs ⋮ Two-guarding a rectilinear polygon ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Topological art in simple galleries ⋮ Algorithm 966 ⋮ Unnamed Item ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ A Bound on a Convexity Measure for Point Sets ⋮ Combinatorics of beacon-based routing in three dimensions ⋮ Orbiting triangle method for convex polygon triangulation ⋮ Quadrilaterizing an Orthogonal Polygon in Parallel ⋮ An addition to art galleries with interior walls ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Disproving a conjecture on planar visibility graphs ⋮ Towards Optimal Positioning of Surveillance UGVs ⋮ Finding the shortest boundary guard of a simple polygon ⋮ Computing accumulation density of particles on a line with parabolic trajectories. ⋮ Visibility with multiple reflections ⋮ On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane ⋮ Inapproximability of finding maximum hidden sets on polygons and terrains ⋮ Illumination in the presence of opaque line segments in the plane ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ Guarding Exterior Region of a Simple Polygon ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Unnamed Item ⋮ On Colourability of Polygon Visibility Graphs ⋮ Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments ⋮ Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region ⋮ Variants of Visibility and their Complexity ⋮ How to Keep an Eye on Small Things ⋮ Improved bounds for guarding plane graphs with edges ⋮ Solving the Watchman Route Problem with Heuristic Search ⋮ Guarding rectangular art galleries ⋮ Computability and complexity of ray tracing ⋮ Optimum placement of guards ⋮ Camera placement in integer lattices ⋮ Pentagonal chains and annuli as models for designing nanostructures from cages ⋮ Monitoring maximal outerplanar graphs ⋮ Area requirement of visibility representations of trees ⋮ Geodesic convexity in discrete spaces ⋮ Searching a polygonal region by a group of stationary $k$-searchers ⋮ Tight bounds for the number of edge guards for spiral polygons ⋮ Protecting convex sets ⋮ Guarding galleries and terrains ⋮ Guarding polyominoes, polycubes and polyhypercubes ⋮ Hiding points in arrangements of segments ⋮ Optimum watchman routes ⋮ Partitioning orthogonal polygons into $\leq 8$-vertex pieces, with application to an art gallery theorem ⋮ Polygon guarding with orientation ⋮ Proper interval graphs and the guard problem ⋮ Rectangle-visibility representations of bipartite graphs ⋮ On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees ⋮ Cooperative mobile guards in grids ⋮ Triangulations, visibility graph and reflex vertices of a simple polygon ⋮ Approximating maximum edge 2-coloring in simple graphs ⋮ Note on an art gallery problem ⋮ Illumination by floodlights ⋮ A new upper bound for the VC-dimension of visibility regions ⋮ Recognizing weakly convex visible polygons ⋮ Visibility with multiple diffuse reflections ⋮ Watchman tours for polygons with holes ⋮ Guarding a set of line segments in the plane ⋮ Approximation algorithms for a geometric set cover problem ⋮ On $k$-convex polygons ⋮ A nearly optimal algorithm for covering the interior of an art gallery ⋮ Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces ⋮ Art gallery theorems for guarded guards. ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ The robber route problem ⋮ Minimum k-partitioning of rectilinear polygons ⋮ Triangulating a nonconvex polytope

This page was built for publication: