In the real-world island of Manhattan, the east–west blocks are roughly twice the length of the north–south blocks. As such, the more accurate picture of distances in the city is shown in Figure...

In the real-world island of Manhattan, the east–west blocks are roughly twice the length of the north–south blocks. As such, the more accurate picture of distances in the city is shown in Figure 2.44(b). Assuming it takes 1.5 minutes to walk a north–south (up–down) block and 3 minutes to walk an east–west (left–right) block, give a formula for the walking distance between hx, yi and Penn Station, at s := h8, 33i.

A Voronoi diagram—named after the 20th-century Russian mathematician Georgy Voronoy—is a decomposition of the plane R2 into regions based on a given set S of points. The region “belonging” to a point x ∈ S is y ∈ R2 : d(x, y) ≤ minz∈S d(z, y) , where d( , ) denotes Euclidean distance—in other words, the region “belonging” to point x is that portion of the plane that’s closer to x than any other point in S.