1
$\begingroup$

Let $S$ be a convex polygon on $n$ points. Given two points $A$ and $B$, where $A$ is left of $S$, and $B$ is right of $S$, what's an algorithm to find the shortest path from $A$ to $B$, that avoids the interior of $S$? What about the longest path?

$\endgroup$
4
  • 1
    $\begingroup$ Are A and B on the edges of S, or are they vertices of S? Are you asking how to choose the shorter of the two paths around the border of a polygon? $\endgroup$ Oct 1, 2013 at 16:33
  • $\begingroup$ A and B are not points of S. A is left of S & B is right of S. $\endgroup$
    – user9665
    Oct 1, 2013 at 16:40
  • 1
    $\begingroup$ Is the longest path even well defined here? If I give you a path, can't you always find a longer one? $\endgroup$
    – Juho
    Oct 1, 2013 at 16:42
  • $\begingroup$ To make your question more clear you should use words outside and around instead of in. $\endgroup$ Oct 1, 2013 at 17:06

1 Answer 1

1
$\begingroup$

The shortest path will be made out of straight lines connecting A, B and the vertices of S.

The most simple solution is to check a bunch of paths, starting with path AB; then AXB and AYB where X and Y are the topmost and bottommost points of S; then extending to the left or right neighbors of X and Y, if some intersections happen.

A smarter solution would be to find the points P, minimizing and maximizing the angle between $\vec {AP}$ and $\vec {AB}$. Those will be the points where your path enters and leaves S.

The longest path is, obviously, infinite.

$\endgroup$
3
  • $\begingroup$ would not the shortest path be the shortest edge ? can there be any two points not going through the interior and also smaller than smallest edge ? $\endgroup$ Nov 1, 2013 at 5:33
  • 1
    $\begingroup$ @AshishNegi I think this needs a drawing. Blue is S, red is the shortest path. What edge are you talking about? $\endgroup$ Nov 1, 2013 at 6:13
  • $\begingroup$ got it thank you. confused with path and straight lines. $\endgroup$ Nov 1, 2013 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.