Your friend dropped you at a point p in the desert. You wish to walk to the near
ID: 3871815 • Letter: Y
Question
Your friend dropped you at a point p in the desert. You wish to walk to the nearest road, from which you could hitchhike back home. However, you have no idea in which direction you should head. Let q be the nearest road point, and let d be the distance from p to q. Explain how you could walk a distance of c·d and reach a road point (not necessarily q). Here c is a constant (does not depend on d) that you have to compute. For simplicity, assume that every road that crosses the desert is an infinite straight line. Each road is either horizontal (oriented East-West) or vertical (South-North). Comments:
(a) Assume that the desert is flat, so every path is possible. Also assume that you are equipped with an accurate GPS, showing you location as well as the direction to North. You have no access to maps.
(b) For simplicity, assume that you need to be physically on the road to see it. So ignore range-of-visibility issues.
(c) Obviously, roads could cross each other, and if they do, they are orthogonal to each other.
(d) If your solution is iterative, explain what exactly is executed at the i’th iteration (for every i)
Explanation / Answer
Let us assume that either road A(North to South) or road B(East to west) is at a distance d from the point point p. As we know that we have a gps system in our hand which gives us the information about our location and where does the north direction exists.
So what we have to do is that we should move distance d in north direction. If the raod B exists in the norht then we will get otherwise we must move distance d in the west direction. If the road A is there at distance d then we will get it. Else we must move distance 2 d in the east direction back. If the road A is at distance d then we will get the road there.
Till now we have already covered distance 4d.
Now if we won't come accross the road A that means that all the possibilities for getting the road A are finished else we must have got road A. now move distance d back in the west direction and then move distance 2d in the south direction.
Till now we have covered all the possibilities of getting the road and we will must get it now.
Hence for exploring the roads we have moved over all distance 7d.
Hence the value of c is 7.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.