Assignment

Cancelled Posted Apr 21, 2009 Paid on delivery
Cancelled Paid on delivery

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.)

Java

Project ID: #422304

About the project

5 proposals Remote project Active Apr 27, 2009

5 freelancers are bidding on average $114 for this job

interpb

Dear Sir , please kindly view PMB

$120 USD in 2 days
(54 Reviews)
6.1
fstudio

Dear sir, I am very interested in your project, Please see PMB for more details. Thanks. Best Regards.

$120 USD in 2 days
(55 Reviews)
5.5
JavaBeau

Let's start:) Please check PMB:)

$110 USD in 2 days
(27 Reviews)
5.1
LajosArpad

I would gladly work on this project, i have worked on many projects in the graph theory domain.

$100 USD in 7 days
(3 Reviews)
3.4
kumaraindika

I'm interesting in your project

$120 USD in 10 days
(0 Reviews)
0.0
webhkp

sir, please check pm. best regards.

$120 USD in 7 days
(0 Reviews)
0.0