Minimum-link paths among obstacles in the plane

DOI10.1007/BF01758855zbMath0788.68144MaRDI QIDQ1201747

Günter Rote, Joseph S. B. Mitchell, Gerhard J. Woeginger

Publication date: 17 January 1993

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

motion planningcomputational geometrylink distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Structured discrete shape approximation: theoretical complexity and practical algorithm ⋮ The Complexity of Drawing a Graph in a Polygonal Region ⋮ Unnamed Item ⋮ Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Optimal on-line algorithms for walking with minimum number of turns in unknown streets ⋮ On geometric path query problems ⋮ Link distance and shortest path problems in the plane ⋮ Minimum-link paths revisited ⋮ The complexity of drawing a graph in a polygonal region ⋮ Minimum-link paths among obstacles in the plane ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ ON GEOMETRIC PATH QUERY PROBLEMS ⋮ Algorithms for Computing Diffuse Reflection Paths in Polygons ⋮ Unnamed Item ⋮ Link Distance and Shortest Path Problems in the Plane ⋮ Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane ⋮ Rectilinear paths among rectilinear obstacles ⋮ Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons ⋮ A wavefront approach to center location problems with barriers

Cites Work

• The complexity and construction of many faces in arrangements of lines and of segments
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Corrections to Lee's visibility polygon algorithm
• Computing the link center of a simple polygon
• A tight lower bound for the complexity of path-planning for a disc
• Triangulating a simple polygon in linear time
• Minimum-link paths among obstacles in the plane
• A linear time algorithm for minimum link paths inside a simple polygon
• Visibility of a simple polygon
• Optimal Point Location in a Monotone Subdivision
• A linear algorithm for computing the visibility polygon from a point
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• An optimal algorithm for intersecting line segments in the plane
• An O(n log n) algorithm for computing a link center in a simple polygon