Hi there. I am preparing to Robotics class exam. I solved all the questions from previous years exams but I have no clue how to deal with this one. I would appreciate your help very much as no one else in the class knows the answer and I can't ask the teacher. Any hint?
- Let us call an obstacle vertex like vertex A in Figure II.3 a convex vertex and an obstacle vertex like vertex B a reflex vertex. Explain why in an environment where all obstacles are polygonal regions the shortest path between any two given points is a polygonal line whose vertices are convex vertices.
- Assume now that the environment is three‐dimensional and that all obstacles are polyhedrons. Given any two points, is the shortest path between them a polygonal line whose vertices are obstacle vertices? If yes, prove it. If not, show a counter‐example.
An intuitive argument for the first question: Connect a loose rope to the starting and finish point. If we contract it (pull it tight) it will make angles at convex vertices, and be straight everywhere else, so if we have a path that doesn't satisfy the conditions, we can find a shorter path that does (by "pulling it tight"). Now this is admittedly not very precise and I'm not sure how to make it more precise.
For the second question, consider a cube as obstacle, and beginning and end point at opposing sides such that the straight line between them goes through the centers of these sides of the cube (so they are basically "exactly opposite to each other" with respect to the cube). The shortest path between the points avoiding the obstacle will make angles at the edges of the obstacle cube (rather than the vertices).