Minimum-link paths revisited
From MaRDI portal
Publication:2450201
DOI10.1016/J.COMGEO.2013.12.005zbMATH Open1290.65016arXiv1302.3091OpenAlexW1990187919MaRDI QIDQ2450201FDOQ2450201
Authors: Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski 
Publication date: 19 May 2014
Published in: Computational Geometry (Search for Journal in Brave)
Abstract: A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case (C = 2). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains. Our two main algorithms are as follows: A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains. An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm. We also obtain several related results: - 3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain). - An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones. - An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain. - A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path. - A notion of "robust" paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1.
Full work available at URL: https://arxiv.org/abs/1302.3091
Recommendations
- On the complexity of minimum-link path problems
- scientific article
- Minimal cost linkages in graphs
- Minimum-link paths among obstacles in the plane
- On finding Min-Min disjoint paths
- scientific article; zbMATH DE number 599010
- A new algorithm for minimum path in a network
- On the minimax path in a network
- On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms
- Connected components and minimum paths
Cites Work
- On a class of \(O(n^ 2)\) problems in computational geometry
- Title not available (Why is that?)
- Computing the visibility polygon from a convex set and related problems
- Geometric discrepancy. An illustrated guide
- Rectilinear paths among rectilinear obstacles
- ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
- Title not available (Why is that?)
- A linear time algorithm for minimum link paths inside a simple polygon
- Efficient Algorithms for Geometric Graph Search Problems
- Title not available (Why is that?)
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- On Some Distance Problems in Fixed Orientations
- Quasi-optimal range searching in spaces of finite VC-dimension
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Ray shooting in polygons using geodesic triangulations
- Optimal computation of finitely oriented convex hulls
- On rectilinear link distance
- Computing minimum length paths of a given homotopy class
- On approximate halfspace range counting and relative epsilon-approximations
- Minimum-link paths among obstacles in the plane
- New algorithms for special cases of the hidden line elimination problem
- On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
- Faster algorithms for minimum-link paths with restricted orientations
- On bends and distances of paths among obstacles in two-layer interconnection model
- Rectilinear Path Problems among Rectilinear Obstacles Revisited
- Dynamic orthogonal segment intersection search
- Title not available (Why is that?)
- Title not available (Why is that?)
- MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES
Cited In (25)
- Structured discrete shape approximation: theoretical complexity and practical algorithm
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- Link-Length Minimization in Networks
- On minimum reload cost paths, tours, and flows
- Geodesic-preserving polygon simplification
- On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- Cutting polygons into small pieces with chords: Laser-based localization
- Homotopic \(\mathcal{C}\)-oriented routing
- Faster algorithms for minimum-link paths with restricted orientations
- Minimum-link shortest paths for polygons amidst rectilinear obstacles
- Minimum-link \(C\)-oriented paths visiting a sequence of regions in the plane
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- On the complexity of minimum-link path problems
- Alternating paths and cycles of minimum length
- Minimum cost path problems with relays
- Title not available (Why is that?)
- Finding paths with minimum shared edges
- The Minimum Reload s-t Path/Trail/Walk Problems
- Shortcut hulls: vertex-restricted outer simplifications of polygons
- MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES
- Homotopic \(\mathcal{C}\)-oriented routing with few links and thick edges
- The minimum reload \(s-t\) path, trail and walk problems
- Title not available (Why is that?)
- Gender-aware facility location in multi-gender world
This page was built for publication: Minimum-link paths revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2450201)
