Friday, February 25, 2011

Shortest path in connecting all vertices

Given below 4 vertices on a two dimensional plane. Connect them in shortest possible way. In other words, there are 4 cities A, B, C and D at the corner of square of side (a) units. What will be the minimum cost of connecting these cities?

Those making circuit layouts of VLSI chips need to solve the puzzle smartly. Even 0.1% gain in space is huge on miniaturized chips.

Answer: Assuming the side of square as s, the minimum cost (road connecting all four cities) is s x (SQRT(3) + 1)

No comments: