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?
$\begingroup$
$\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$– Karolis JuodelėCommented 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$– user9665Commented 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$– JuhoCommented Oct 1, 2013 at 16:42
-
$\begingroup$ To make your question more clear you should use words outside and around instead of in. $\endgroup$– Karolis JuodelėCommented Oct 1, 2013 at 17:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\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$ Commented 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$ Commented Nov 1, 2013 at 6:13
-
$\begingroup$ got it thank you. confused with path and straight lines. $\endgroup$ Commented Nov 1, 2013 at 6:15
