Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

DOI10.1007/BF01840360zbMath0642.68081OpenAlexW2132339863MaRDI QIDQ1101226

Daniel Leven, Micha Sharir, Leonidas J. Guibas, J. E. Hershberger, Robert Endre Tarjan

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

triangulationshortest pathsvisibilitycomputational geometrylinear-time algorithmssimple polygonray shooting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Geometric constructions in real or complex geometry (51M15)

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

Constructing pairwise disjoint paths with few links ⋮ Finding all weakly-visible chords of a polygon in linear time ⋮ Computing a shortest watchman path in a simple polygon in polynomial-time ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ CUTTING OUT POLYGONS WITH A CIRCULAR SAW ⋮ COMPUTING PUSH PLANS FOR DISK-SHAPED ROBOTS ⋮ Connect the Dot: Computing Feed-Links with Minimum Dilation ⋮ Shortest Path Problems on a Polyhedral Surface ⋮ Minimum weight pseudo-triangulations ⋮ AN OPTIMAL MORPHING BETWEEN POLYLINES ⋮ OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ SEARCHING A ROOM BY TWO GUARDS ⋮ Shortest paths in simple polygons with polygon-meet constraints ⋮ AN APPROXIMATE MORPHING BETWEEN POLYLINES ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE ⋮ On the correctness of a linear-time visibility polygon algorithm^∗ ⋮ An O(n log n) algorithm for computing a link center in a simple polygon ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ Cartographic line simplication and polygon CSG formulae in O(n log* n) time ⋮ A new balanced subdivision of a simple polygon for time-space trade-off algorithms ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Continuous-Time Moving Network Voronoi Diagram ⋮ Kinetic Geodesic Voronoi Diagrams in a Simple Polygon ⋮ Reflective guarding a gallery ⋮ Efficient computation of the geodesic Voronoi diagram of points in a simple polygon ⋮ Large \(k\)-gons in a 1.5D terrain ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Incremental Algorithms to Update Visibility Polygons ⋮ How to Extend Visibility Polygons by Mirrors to Cover Invisible Segments ⋮ Unnamed Item ⋮ Multiple point visibility and related problems ⋮ Characterizing and recognizing LR-visibility polygons ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems ⋮ Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding ⋮ Line-of-Sight Pursuit in Monotone and Scallop Polygons ⋮ Dynamic Algorithms for Visibility Polygons in Simple Polygons ⋮ On polyhedra induced by point sets in space ⋮ Approximate Shortest Paths in Polygons with Violations ⋮ Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon ⋮ Weak visibility queries of line segments in simple polygons and polygonal domains ⋮ Query-point visibility constrained shortest paths in simple polygons ⋮ Hide-and-Seek: Algorithms for Polygon Walk Problems ⋮ FINDING ALL DOOR LOCATIONS THAT MAKE A ROOM SEARCHABLE ⋮ Shortest-Path Queries in Geometric Networks ⋮ GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON ⋮ Delineating boundaries for imprecise regions ⋮ An optimal-time algorithm for shortest paths on a convex polytope in three dimensions ⋮ Characterizing LR-visibility polygons and related problems ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ A linear time algorithm to remove winding of a simple polygon ⋮ A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation ⋮ Unnamed Item ⋮ Visibility with multiple reflections ⋮ k-pairs non-crossing shortest paths in a simple polygon ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ SEARCHING A POLYGONAL ROOM WITH ONE DOOR BY A 1-SEARCHER ⋮ k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON ⋮ Computing in linear time a chord from which a simple polygon is weakly internally visible ⋮ Polygons cuttable by a circular saw ⋮ Approximate convex decomposition of polygons ⋮ Optimal finger search trees in the pointer machine ⋮ Guarding a terrain by two watchtowers ⋮ Guarding Exterior Region of a Simple Polygon ⋮ PARETO ENVELOPES IN SIMPLE POLYGONS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ CLEARING A POLYGON WITH TWO 1-SEARCHERS ⋮ Approximation Algorithms for Edge-Covering Problem ⋮ Unnamed Item ⋮ CUTTING OUT POLYGONS WITH LINES AND RAYS ⋮ Link Distance and Shortest Path Problems in the Plane ⋮ Unnamed Item ⋮ Dynamic Trees and Dynamic Point Location ⋮ Rectilinear paths among rectilinear obstacles ⋮ An optimal algorithm to compute the inverse beacon attraction region ⋮ On Romeo and Juliet Problems: Minimizing Distance-to-Sight. ⋮ How to Keep an Eye on Small Things ⋮ GEODESIC-PRESERVING POLYGON SIMPLIFICATION ⋮ Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time ⋮ Weak visibility counting in simple polygons ⋮ Routing in Polygonal Domains ⋮ Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons ⋮ Two-Guard Walkability of Simple Polygons ⋮ Determining Weak Visibility of a Polygon from an Edge in Parallel ⋮ ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS ⋮ Approximability of guarding weak visibility polygons ⋮ Optimally computing a shortest weakly visible line segment inside a simple polygon ⋮ Packing two disks in a polygon ⋮ The geodesic 2-center problem in a simple polygon ⋮ Computing minimum length paths of a given homotopy class ⋮ An optimal algorithm for the on-line closest-pair problem ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Finding a largest-area triangle in a terrain in near-linear time ⋮ Maintaining visibility of a polygon with a moving point of view ⋮ An algorithm for recognizing palm polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Visibility and intersection problems in plane geometry
• Mathematics for the analysis of algorithms.
• A linear algorithm for finding the convex hull of a simple polygon
• A new data structure for representing sorted lists
• A short proof of Chvatal's Watchman Theorem
• Triangulating a simple polygon
• A linear time algorithm for minimum link paths inside a simple polygon
• Visibility of a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Triangulating Simple Polygons and Equivalent Problems
• Optimal Point Location in a Monotone Subdivision
• Self-adjusting binary search trees
• Shortest path solves edge-to-edge visibility in a polygon
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• A linear algorithm for computing the visibility polygon from a point
• Optimal Search in Planar Subdivisions
• Finding the convex hull of a simple polygon

This page was built for publication: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons