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

From MaRDI portal

Publication:1101226

Jump to:navigation, search

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

triangulation shortest paths visibility computational geometry linear-time algorithms simple polygon ray 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

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, 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, 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, Visibility between two edges of a simple polygon, A 2-approximation algorithm for the zookeeper's problem, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, A linear-time algorithm for constructing a circular visibility diagram, Routing among convex polygonal obstacles in the plane, A new algorithm for shortest paths among obstacles in the plane, A framework for advancing front techniques of finite element mesh generation, Separating two simple polygons by a sequence of translations, Computing the link center of a simple polygon, Parallel algorithms for shortest path problems in polygons, Efficient piecewise-linear function approximation using the uniform metric, An optimal visibility graph algorithm for triangulated simple polygons, On the geodesic Voronoi diagram of point sites in a simple polygon, An algorithmic approach to some problems in terrain navigation, Online exploration outside a convex obstacle, Generalized hidden surface removal, Visibility in semi-convex spaces, Routing in polygonal domains, Self-approaching paths in simple polygons, A survey of motion planning and related geometric algorithms, Generating random polygons with given vertices, Shortest paths in the plane with obstacle violations, The vertex-edge visibility graph of a polygon, Recognizing weakly convex visible polygons, Visibility with multiple diffuse reflections, Near optimal line segment queries in simple polygons, Shortest path planning for a tethered robot, Link distance and shortest path problems in the plane, Improved bounds for finger search on a RAM, Visibility and intersection problems in plane geometry, Shortest paths and convex hulls in 2D complexes with non-positive curvature, Storing line segments in partition trees, Geometric path problems with violations, Searching for mobile intruders in circular corridors by two 1-searchers, Augmenting the edge connectivity of planar straight line graphs to three, Approximation algorithms for the watchman route and zookeeper's problems., Shortest path problems on a polyhedral surface, Computing external farthest neighbors for a simple polygon, Triangulating a simple polygon in linear time, A new data structure for shortest path queries in a simple polygon, Computing the Fréchet distance between simple polygons, Finding a shortest Hamiltonian path inside a simple polygon, An optimal algorithm for finding the edge visibility polygon under limited visibility, Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures, Decomposing the boundary of a nonconvex polyhedron, Proximity problems for points on a rectilinear plane with rectangular obstacles, Parallel rectilinear shortest paths with rectangular obstacles, Finding a shortest diagonal of a simple polygon in linear time, LR-visibility in polygons, Finding the largest area axis-parallel rectangle in a polygon, Search for shortest path around semialgebraic obstacles in the plane, Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon, An \(O(n\log n)\) algorithm for computing the link center of a simple polygon, Computing the visibility polygon of an island in a polygonal domain, Characterizing and recognizing weak visibility polygons, Special subgraphs of weighted visibility graphs, Parallel methods for visibility and shortest-path problems in simple polygons, Computing the \(L_1\) geodesic diameter and center of a polygonal domain, The furthest-site geodesic Voronoi diagram, Visibility and ray shooting queries in polygonal domains, Parametric search: three new applications, Visibility extension via mirror-edges to cover invisible segments, \(L_{1}\) shortest path queries in simple polygons, Computing the geodesic center of a simple polygon, Computing the external geodesic diameter of a simple polygon, Diffuse reflection radius in a simple polygon, A linear-time algorithm for the geodesic center of a simple polygon, An efficient algorithm for the three-guard problem, Voronoi diagrams for a moderate-sized point-set in a simple polygon, Towards a definition of higher order constrained Delaunay triangulations, A fast shortest path algorithm on terrain-like graphs, Vertex-colored encompassing graphs, An efficient algorithm for finding the CSG representation of a simple polygon, A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon, Finding shortest safari routes in simple polygons, An approximative solution to the Zookeeper's problem, Shortest watchman routes in simple polygons, Isomorphism of spiral polygons, Shortest polygonal paths in space, The geodesic farthest-point Voronoi diagram in a simple polygon, Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time, Computing geodesic furthest neighbors in simple polygons, Quickest visibility queries in polygonal domains, Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences, Optimal placement of base stations in border surveillance using limited capacity drones, On Romeo and Juliet problems: minimizing distance-to-sight, \(L_1\) geodesic farthest neighbors in a simple polygon and related problems, Simple algorithms for searching a polygon with flashlights, Weak visibility queries of line segments in simple polygons, Shortest zookeeper's routes in simple polygons, A workbench for computational geometry

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1101226&oldid=13135379"