Thread: Convex hull and shortest path problem

Hi,

I'm not so much after answers here as an explanation of what the second question is asking:

3. There is a fenced area in the two-dimensional Euclidean plane in the shape of a convex polygon with vertices at points

P1(x1,y1), P2(x2,y2), ...., Pn(xn,yn)

(not necessarily in this order). There are two more points, A(xA, yA) and B(xB,yB), such that xA < min { x1, ..., xn } and xB > max { x1, ..., xn }. Design a reasonably efficient algorithm for computing the length of the shortest path between A and B, and the shortest path itself.

4. Under the conditions of question 3, design a reasonably efficient algorithm for computing the shortest among all piece-wise linear paths between A and B having the least number of angle points.

Now I've done question three by effectively finding the convex hull of { P1, ..., Pn, A, B } and then using Dijkstra's algorithm to find the shortest path through them. I've drawn a diagram to illustrate what I mean:



What I'm not sure about is what question 4 is asking. They're after the path that is shortest AND has least angle points? Or some kind of compromise? Aside from the angle point restriction Q4 looks identical to Q3...

Does anyone have any ideas as to what Q4 is asking? This is fairly urgent and I'd really appreciate the help.

Thanks,
Rob

Originally Posted by RobJ

Hi,

I'm not so much after answers here as an explanation of what the second question is asking:

Now I've done question three by effectively finding the convex hull of { P1, ..., Pn, A, B } and then using Dijkstra's algorithm to find the shortest path through them. I've drawn a diagram to illustrate what I mean:

It would be advantageous if the convex hull were convex!

RonL

Well yes, I have to admit my MSPaint skills may not be quite up to scratch! Assuming for a minute that the convex hull is in fact convex can anyone help me?

Edit: Okay, I think I've resolved this issue. I'm taking the minimal length segment ACB where C is the outermost vertex in { P1, P2, ..., Pn } since that seems to fill most of the criteria.