Minimum-link shortest paths for polygons amidst rectilinear obstacles

DOI10.1016/J.COMGEO.2022.101858MaRDI QIDQ2123290zbMATH OpenOpenAlexFDO

Authors Mincheol Kim, Hee-Kap Ahn

Publication date 8 April 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.14185

zbMATH Keywords

minimum linkspolygonsrectilinear obstaclesshortest paths

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)

Abstract: Consider two axis-aligned rectilinear simple polygons in the domain consisting of axis-aligned rectilinear obstacles in the plane such that the bounding boxes, one for each obstacle and one for each polygon, are disjoint. We present an algorithm that computes a minimum-link rectilinear shortest path connecting the two polygons in $O((N+n)log(N+n))$ time using $O(N+n)$ space, where $n$ is the number of vertices in the domain and $N$ is the total number of vertices of the two polygons.

Recommendations

• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Minimum-link paths among obstacles in the plane
• Rectilinear Path Problems among Rectilinear Obstacles Revisited

Cites work

• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• L₁ shortest path queries among polygonal obstacles in the plane
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Computational geometry. Algorithms and applications.
• Efficient Algorithms for Geometric Graph Search Problems
• scientific article; zbMATH DE number 177554 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• Minimum-link paths revisited
• ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
• ON GEOMETRIC PATH QUERY PROBLEMS
• Rectilinear Path Problems among Rectilinear Obstacles Revisited
• Rectilinear paths among rectilinear obstacles
• Rectilinear shortest paths in the presence of rectangular barriers
• THE L_∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS

Cited in

(14)

• An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions
• Minimum-link paths among obstacles in the plane
• Voronoi diagrams with barriers and on polyhedra for minimal path planning
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Computing a rectilinear shortest path amid splinegons in plane
• The shortest path in a simple polygon with obstacles
• scientific article; zbMATH DE number 2077086 (Why is no real title available?)
• A SHORTEST PAIR OF PATHS ON THE PLANE WITH OBSTACLES AND CROSSING AREAS
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS
• Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
• Finding a shortest pair of paths on the plane with obstacles and crossing areas
• Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
• Planar rectilinear shortest path computation using corridors

This page was built for publication: Minimum-link shortest paths for polygons amidst rectilinear obstacles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2123290)