patternMinor
Trapezoidal decomposition of a graph
Viewed 0 times
decompositiontrapezoidalgraph
Problem
When we plan the motion of a robot we may apply the trapezoidal
decomposition of free space. While applying the trapezoidal
decomposition we add nodes to both the centers of trapezoids and
vertical walls.
When a robot wants to traverse between obstacles it avoids the obstacles
by following the nodes added. The nodes create a graph which provides a
smooth traverse between the obstacles (at least so we assume). In this
case we assume that we are creating a graph using all nodes.
Is it possible to plan a graph with only using the center of trapezoid
or the center nodes of vertical walls?
My idea is; it depends on the situation (the position of obstacles, the
shape of the robot etc.) But I could not image such graph which could
be changed to a new graph with only using the nodes on the vertical
walls. If we design the example do we need to increase the number of
edges?
I think it is not necessity to increase the number of edges to manage to
use only vertical walls' nodes, but I could not figure out how it could
be possible exactly.
decomposition of free space. While applying the trapezoidal
decomposition we add nodes to both the centers of trapezoids and
vertical walls.
When a robot wants to traverse between obstacles it avoids the obstacles
by following the nodes added. The nodes create a graph which provides a
smooth traverse between the obstacles (at least so we assume). In this
case we assume that we are creating a graph using all nodes.
Is it possible to plan a graph with only using the center of trapezoid
or the center nodes of vertical walls?
My idea is; it depends on the situation (the position of obstacles, the
shape of the robot etc.) But I could not image such graph which could
be changed to a new graph with only using the nodes on the vertical
walls. If we design the example do we need to increase the number of
edges?
I think it is not necessity to increase the number of edges to manage to
use only vertical walls' nodes, but I could not figure out how it could
be possible exactly.
Solution
In order to get valid paths in the free space from paths in the graph $G=(V,E)$ that is constructed via the trapezoidal decomposition, we require that all edges of $G$ lie inside the free space.
The segment between two centers of adjacent trapezoids is not always fully contained inside the free space. For example, consider a square and take a slightly smaller square with the same center as the obstacle. So, using only the nodes at the center of the trapezoid is not sufficient to find paths in the free space.
On the other hand, any segment between a pair of nodes centered at a vertical boundary of the same trapezoid is fully inside the free space, since trapezoids are convex. So, the graph $G'=(V',E')$ with as vertices the centers of the vertical boundaries with an edge between every pair of vertices that lies on the boundary of the same trapezoid lies fully within the free space.
So, why bother using the graph $G$ and not $G'$? One issue with $G'$ is that a trapezoid with $d$ adjacent trapezoids means $G'$ has the complete graph on $d$ nodes as a subgraph, which has $\Theta(d^2)$ edges. So in the worst case, finding a path in $G'$ takes at least $\Omega(n^2)$ time, where $n$ is the number of in the decomposition. On the other hand, $G$ has at most $2$ edges for each vertical trapezoid boundary, so at most two per vertex of the obstacle boundary, which means it has $O(n)$ edges and we can find shortest paths in $O(n\log n)$ using Dijkstra.
The segment between two centers of adjacent trapezoids is not always fully contained inside the free space. For example, consider a square and take a slightly smaller square with the same center as the obstacle. So, using only the nodes at the center of the trapezoid is not sufficient to find paths in the free space.
On the other hand, any segment between a pair of nodes centered at a vertical boundary of the same trapezoid is fully inside the free space, since trapezoids are convex. So, the graph $G'=(V',E')$ with as vertices the centers of the vertical boundaries with an edge between every pair of vertices that lies on the boundary of the same trapezoid lies fully within the free space.
So, why bother using the graph $G$ and not $G'$? One issue with $G'$ is that a trapezoid with $d$ adjacent trapezoids means $G'$ has the complete graph on $d$ nodes as a subgraph, which has $\Theta(d^2)$ edges. So in the worst case, finding a path in $G'$ takes at least $\Omega(n^2)$ time, where $n$ is the number of in the decomposition. On the other hand, $G$ has at most $2$ edges for each vertical trapezoid boundary, so at most two per vertex of the obstacle boundary, which means it has $O(n)$ edges and we can find shortest paths in $O(n\log n)$ using Dijkstra.
Context
StackExchange Computer Science Q#134246, answer score: 2
Revisions (0)
No revisions yet.