An algorithmic approach to some problems in terrain navigation
Recent advantages in the field of computational geometry have provided efficient algorithms for a variety of shortest path problems. Many problems in the field of terrain navigation can be cast as optimal path problems in a precise geometric model. With such a model one can develop and analyse algorithms for the solution of the original problem and can gain insights into how to design more efficient heuristics to deal with more complex problems. We examine the path planning problem in which we are given a ``map of a region of terrain and we are expected to find optimal paths from one point to another. This, for example, is a task which must be done repeatedly for the guidance of an autonomous vehicle. We examine how to formulate some path planning problems precisely, and we report algorithms to solve certain special cases.
- scientific article; zbMATH DE number 1424303
- Shortest paths in the plane with convex polygonal obstacles
- Searching shortest paths on a set of geometric objects
- Generalizations of Naismith's problem: minimal transit time between two points in a heterogenous terrian
- Approximate shortest descending paths
- A Method for Solving Arbitrary-Wall Mazes by Computer
- A note on two problems in connexion with graphs
- An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
- An algorithm for shortest-path motion in three dimensions
- An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
- Computational geometry in a curved world
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Euclidean shortest paths in the presence of rectilinear barriers
- scientific article; zbMATH DE number 3887061 (Why is no real title available?)
- scientific article; zbMATH DE number 4149525 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3657150 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 177864 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3213117 (Why is no real title available?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- On Shortest Paths in Polyhedral Spaces
- On Some Distance Problems in Fixed Orientations
- Optimal piecewise linear motion of an object among obstacles
- Optimal Search in Planar Subdivisions
- Optimal shortest path queries in a simple polygon
- Optimum watchman routes
- Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Rectilinear shortest paths in the presence of rectangular barriers
- Shortest path between two simple polygons
- Shortest watchman routes in simple polygons
- The Discrete Geodesic Problem
- The power of geometric duality revisited
- Unobstructed shortest paths in polyhedral environments
- Visibility of disjoint polygons
- Trajectory planning in \(H\)-space
- A new algorithm for shortest paths among obstacles in the plane
- On fast planning of suboptimal paths amidst polygonal obstacles in plane
- Efficient piecewise-linear function approximation using the uniform metric
- Computing the trajectories for the development of optimal routes
- Quickest path queries on transportation network
- Generalizations of Naismith's problem: minimal transit time between two points in a heterogenous terrian
- Automatic target tracking on multi-resolution terrain
- scientific article; zbMATH DE number 1462394 (Why is no real title available?)
- Linear Search with Terrain-Dependent Speeds
- Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces
- On approximating shortest paths in weighted triangular tessellations
- Characterizing and recognizing weak visibility polygons
- Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs
- Guarding curvilinear art galleries with vertex or point guards
This page was built for publication: An algorithmic approach to some problems in terrain navigation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116366)
