Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
From MaRDI portal
DOI10.1007/BF01840360zbMATH Open0642.68081OpenAlexW2132339863MaRDI QIDQ1101226FDOQ1101226
Authors: Daniel Leven, Micha Sharir, Leonidas Guibas, John Hershberger, Robert E. Tarjan 
Publication date: 1987
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840360
Recommendations
computational geometryshortest pathstriangulationvisibilitylinear-time algorithmssimple polygonray shooting
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)
Cites Work
- A short proof of Chvatal's Watchman Theorem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Self-adjusting binary search trees
- Optimal Search in Planar Subdivisions
- Finding the convex hull of a simple polygon
- Title not available (Why is that?)
- Mathematics for the analysis of algorithms.
- A linear time algorithm for minimum link paths inside a simple polygon
- Optimal Point Location in a Monotone Subdivision
- Visibility and intersection problems in plane geometry
- Euclidean shortest paths in the presence of rectilinear barriers
- Triangulating a simple polygon
- Triangulating Simple Polygons and Equivalent Problems
- A linear algorithm for computing the visibility polygon from a point
- Visibility of a simple polygon
- A new data structure for representing sorted lists
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- A linear algorithm for finding the convex hull of a simple polygon
- Shortest path solves edge-to-edge visibility in a polygon
Cited In (only showing first 100 items - show all)
- The vertex-edge visibility graph of a polygon
- Routing among convex polygonal obstacles in the plane
- Routing in polygonal domains
- Routing in polygonal domains
- An optimal algorithm for the on-line closest-pair problem
- Finding a largest-area triangle in a terrain in near-linear time
- Packing two disks in a polygon
- An \(O(n \log n)\) algorithm for computing a link center in a simple polygon
- Parallel algorithms for shortest path problems in polygons
- Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time
- Parallel methods for visibility and shortest-path problems in simple polygons
- Decomposing the boundary of a nonconvex polyhedron
- An efficient algorithm for finding the CSG representation of a simple polygon
- A 2-approximation algorithm for the zookeeper's problem
- Reflective guarding a gallery
- Recognizing weakly convex visible polygons
- Approximate Shortest Paths in Polygons with Violations
- An approximative solution to the Zookeeper's problem
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS
- Weak visibility queries of line segments in simple polygons and polygonal domains
- A new algorithm for shortest paths among obstacles in the plane
- Shortest zookeeper's routes in simple polygons
- An efficient algorithm for the three-guard problem
- Quickest visibility queries in polygonal domains
- Cartographic line simplication and polygon CSG formulae in \(O(n \log^* n)\) time
- An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
- Vertex-colored encompassing graphs
- Near optimal line segment queries in simple polygons
- Shortest polygonal paths in space
- A workbench for computational geometry
- Shortest path planning for a tethered robot
- Visibility between two edges of a simple polygon
- Computing external farthest neighbors for a simple polygon
- A new data structure for shortest path queries in a simple polygon
- AN APPROXIMATE MORPHING BETWEEN POLYLINES
- Optimally computing a shortest weakly visible line segment inside a simple polygon
- Parallel rectilinear shortest paths with rectangular obstacles
- A near-optimal algorithm for shortest paths among curved obstacles in the plane
- An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
- An algorithm for recognizing palm polygons
- A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
- Special subgraphs of weighted visibility graphs
- Title not available (Why is that?)
- Efficient computation of the geodesic Voronoi diagram of points in a simple polygon
- Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
- Dynamic algorithms for visibility polygons in simple polygons
- An efficient algorithm for the three-dimensional diameter problem
- A unified approach to conic visibility
- Visibility with multiple reflections
- The furthest-site geodesic Voronoi diagram
- Dynamic Trees and Dynamic Point Location
- A framework for advancing front techniques of finite element mesh generation
- A linear-time algorithm for solving the strong hidden-line problem in a simple polygon
- A survey of motion planning and related geometric algorithms
- Storing line segments in partition trees
- Towards a definition of higher order constrained Delaunay triangulations
- An algorithmic approach to some problems in terrain navigation
- Computing minimum length paths of a given homotopy class
- Finding the largest area axis-parallel rectangle in a polygon
- A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
- A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
- Computing the Fréchet distance between simple polygons
- On the geodesic Voronoi diagram of point sites in a simple polygon
- Geodesic-preserving polygon simplification
- Approximate convex decomposition of polygons
- Characterizing and recognizing the visibility graph of a funnel-shaped polygon
- Visibility and ray shooting queries in polygonal domains
- Visibility in semi-convex spaces
- Computing geodesic furthest neighbors in simple polygons
- Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
- OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
- Link Distance and Shortest Path Problems in the Plane
- Shortest paths in simple polygons with polygon-meet constraints
- Maintaining visibility of a polygon with a moving point of view
- Computing the external geodesic diameter of a simple polygon
- A linear-time algorithm for the geodesic center of a simple polygon
- CLEARING A POLYGON WITH TWO 1-SEARCHERS
- Triangulating a simple polygon in linear time
- Computing a shortest watchman path in a simple polygon in polynomial-time
- Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
- Shortest watchman routes in simple polygons
- Ray shooting in polygons using geodesic triangulations
- Shortest Path Problems on a Polyhedral Surface
- Computing the link center of a simple polygon
- Separating two simple polygons by a sequence of translations
- Visibility and intersection problems in plane geometry
- Optimal finger search trees in the pointer machine
- Generating random polygons with given vertices
- Delineating boundaries for imprecise regions
- Approximation Algorithms for Edge-Covering Problem
- Search for shortest path around semialgebraic obstacles in the plane
- Simple algorithms for searching a polygon with flashlights
- The geodesic 2-center problem in a simple polygon
- SEARCHING A POLYGONAL ROOM WITH ONE DOOR BY A 1-SEARCHER
- Shortest path problems on a polyhedral surface
- Minimum weight pseudo-triangulations
- Visibility with multiple diffuse reflections
- On polyhedra induced by point sets in space
- On the correctness of a linear-time visibility polygon algorithm∗
This page was built for publication: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101226)
