Assignment

You are given an undirected planar graph where the nodes are points in two-dimensional Cartesian space. (So the points are described by pairs of floating point numbers.) Assume some convenient value (say, 100) for the maximum value for both coordinates. Generally, the nearest three or four points to a given point are connected to it by edges (but this is just a rule of thumb). You are given an undirected planar graph where the nodes are points in two-dimensional Cartesian space. (So the points are described by pairs of floating point numbers.) Assume some convenient value (say, 100) for the maximum value for both coordinates. Generally, the nearest three or four points to a given point are connected to it by edges (but this is just a rule of thumb). Distinguish one node as the start, another as the destination. Arrange things so that these two distinguished nodes are never in the interior of the convex hull. Given the start and destination nodes and the convex hull, find the two paths from start to destination that lie on the convex hull. Find the shortest path from the start to the destination through the interior of the convex hull. The only nodes on the convex hull that also lie on this path are the start and destination points. Simulate vehicles moving simultaneously along these paths. Arrange the speed so that, when they set out from the start point at the same time, they arrive simultaneously at the destination. Allow for random errors in following a motion plan. The vehicle could either move to some node connected to the current node other than the next node on the plan or it could take a longer or shorter time to get to the next node. If the timing is off, the correction is simply to adjust the speed so that it still arrives at the destination at the same time as the other vehicles. If the vehicle deviates from the path, there are two cases, depending on whether the vehicle is supposed to be moving along the convex hull or through its interior. If the vehicle is supposed to be moving along the convex hull, then we need a new plan to get it back on the convex hull as soon as possible. If the vehicle was moving through the interior of the convex hull, then we need a new shortest path to the destination that stays in the interior. In either case, following the new path should have the vehicle arrive at the destination at the same time the other vehicles arrive there. As an alternative to finding one path through the interior of the convex hull, find three paths through it (assuming there are enough nodes). One will be the shortest path as computed before. amir says: The other two will be the shortest paths on either side of this path that do not intersect the convex hull itself. (If we can find three such paths, we can get two paths by deleting the middle path.)