An optimal visibility graph algorithm for triangulated simple polygons

DOI10.1007/BF01553883zbMath0662.68041OpenAlexW2086966885MaRDI QIDQ1114399

J. E. Hershberger

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553883

zbMATH Keywords

triangulationshortest pathcomputational geometryvisibility graphsimple polygon

Mathematics Subject Classification ID

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 (32)

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

This page was built for publication: An optimal visibility graph algorithm for triangulated simple polygons