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$
  • 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$ – Karolis Juodelė Oct 1 '13 at 16:33
  • $\begingroup$ A and B are not points of S. A is left of S & B is right of S. $\endgroup$ – Manish Kumar Oct 1 '13 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 '13 at 16:42
  • $\begingroup$ To make your question more clear you should use words outside and around instead of in. $\endgroup$ – Karolis Juodelė Oct 1 '13 at 17:06
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$
  • $\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$ – Ashish Negi Nov 1 '13 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$ – Karolis Juodelė Nov 1 '13 at 6:13
  • $\begingroup$ got it thank you. confused with path and straight lines. $\endgroup$ – Ashish Negi Nov 1 '13 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.