1
$\begingroup$

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments between vertices of the polygonal obstacles.

This seems intuitive enough, but how do we prove this?

I have found several resources that seem to gloss over this:

1 and 2) Previous stackexchange answer, which says this problem is reducible to having lines as obstacles, but the Ph.D. thesis it refers to doesn't actually seem to provide a proof for this either, as there is no proof given for Corollary 5.1 on p. 112 (whereas the theorem it is a corollary to seems to have a very simple proof).

  1. Stanford geometric algorithms lecture notes also gloss over this, no proof provided for lemma 2.

  2. Another paper I found also says for the relevant Lemma 1 "we don't provide the simple proof [...]."

I can't tell if I'm just missing something obvious that most readers can just fill in the blanks with or not.

Any thoughts appreciated.

Thanks.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hint: Triangle Inequality. For any path, that has a vertex outside the polygonal obstacle, you can create a shorter path. $\endgroup$
    – Inuyasha Yagami
    Commented Jan 21, 2022 at 21:02

0

Reset to default

Your Answer

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