Geometric data structures approximations for network optimisation problems
Miloš Šeda, T. Březina · International Conference on Mathematical methods, Computational techniques and Intelligent systems · 2009
A frequent task in transportation, routing, robotics, and communications applications is to find the shortest path between two positions. In robot motion planning, the robot should pass around the obstacles touching none of them, i.e. the goal is to find a collision-free path from a starting to a target position. Research of path planning has yielded many fundamentally different approaches to its solution, mainly based on various decomposition and roadmap methods. In this paper, we show a possible use of geometric data structures in point-to-point motion planning in the Euclidean plane and present an approach using generalised Voronoi diagrams that decreases the probability of collisions with obstacles and generate smooth trajectories. The second application area, investigated here, is focused on problems of finding minimal networks connecting a set of given points in the Euclidean plane and their approximations using the Delaunay triangulation.