An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains
From MaRDI portal
Publication:1755791
DOI10.1007/s00453-018-0446-1zbMath1410.68374arXiv1504.06842OpenAlexW2802252099MaRDI QIDQ1755791
Haitao Wang, Mikko Sysikaski, Valentin Polishchuk, Joseph S. B. Mitchell
Publication date: 11 January 2019
Published in: Algorithmica, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.06842
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
Minimum-link shortest paths for polygons amidst rectilinear obstacles, Rectilinear link diameter and radius in a rectilinear polygonal domain, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, Rectilinear link diameter and radius in a rectilinear polygonal domain, Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rectilinear link distance
- Rectilinear shortest paths in the presence of rectangular barriers
- Triangulating a simple polygon in linear time
- An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
- Minimum-link paths among obstacles in the plane
- On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
- Computing minimum length paths of a given homotopy class
- An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
- An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains
- Optimal parallel algorithms for rectilinear link-distance problems
- Separation and approximation of polyhedral objects
- Minimum-link paths revisited
- A linear time algorithm for minimum link paths inside a simple polygon
- A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane
- Efficient Algorithms for Geometric Graph Search Problems
- Triangulation and shape-complexity
- Triangulating Simple Polygons and Equivalent Problems
- Optimal Point Location in a Monotone Subdivision
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- Optimal Search in Planar Subdivisions
- APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
- MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES
- TRIANGULATING DISJOINT JORDAN CHAINS
- Two-Point L1 Shortest Path Queries in the Plane
- Sorting jordan sequences in linear time using level-linked search trees
- LOGARITHMIC-TIME LINK PATH QUERIES IN A SIMPLE POLYGON
- AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
- Computing the visibility polygon from a convex set and related problems
