An optimal visibility graph algorithm for triangulated simple polygons
From MaRDI portal
Publication:1114399
DOI10.1007/BF01553883zbMath0662.68041OpenAlexW2086966885MaRDI QIDQ1114399
Publication date: 1989
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01553883
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)
Related Items
An algorithm for recognizing palm polygons, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, Quasi-Monte-Carlo methods and the dispersion of point sequences, Generating random polygons with given vertices, The vertex-edge visibility graph of a polygon, Recognizing weakly convex visible polygons, On colourability of polygon visibility graphs, One-sided terrain guarding and chordal graphs, Approximation algorithms for the watchman route and zookeeper's problems., A fast algorithm for approximating the detour of a polygonal chain., Triangulating a simple polygon in linear time, A new data structure for shortest path queries in a simple polygon, Spiderman graph: visibility in urban regions, A note on the combinatorial structure of the visibility graph in simple polygons, Computing the maximum clique in the visibility graph of a simple polygon, On recognizing and characterizing visibility graphs of simple polygons, Characterizing and recognizing weak visibility polygons, On guarding the vertices of rectilinear domains, Parallel methods for visibility and shortest-path problems in simple polygons, Characterizing LR-visibility polygons and related problems, Algorithms for Computing Diffuse Reflection Paths in Polygons, LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS, On Colourability of Polygon Visibility Graphs, Topologically sweeping visibility complexes via pseudotriangulations, Stabbing information of a simple polygon, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane, On local transformation of polygons with visibility properties., VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME, Efficient visibility queries in simple polygons, Weak visibility queries of line segments in simple polygons, Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons, Two-Guard Walkability of Simple Polygons
Cites Work
- Unnamed Item
- Visibility and intersection problems in plane geometry
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Visibility of disjoint polygons
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A new data structure for representing sorted lists
- Triangulating a simple polygon
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Triangulation and shape-complexity
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
