Results 1 to 3 of 3

Math Help - Convex hull and shortest path problem

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by RobJ View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2007
    Posts
    2
    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.
    Last edited by RobJ; April 19th 2007 at 01:05 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. convex hull
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: January 15th 2012, 11:19 PM
  2. Convex Hull
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 31st 2010, 12:17 PM
  3. Optimization theory-convex hull help
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: January 21st 2010, 03:44 AM
  4. help with visualizing convex hull and polytope
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: October 31st 2009, 02:03 PM
  5. Existence of a convex hull of few points in R^n ?
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: January 18th 2008, 06:17 AM

Search Tags


/mathhelpforum @mathhelpforum