There are several alternative ways to define a distance between two points P 1 , = (x 1 , Y l ) and P 2 = (x 2 , Y 2 ) in the Cartesian plane. In particular, the so-called Manhattan distance is...

There are several alternative ways to define a distance between two points P₁, = (x₁, Y_l) and P₂
= (x₂, Y₂) in the Cartesian plane. In particular, the so-called Manhattan distance is defined as

Prove that dM satisfies the following axioms which every distance function must satisfy:

i. d_M(P₁, P₂)
 0 for any two points P₁
and P₂
and d_M(P₁, P₂) = 0 if and only if P₁
= P₂;

ii. d_M(P₁, P₂
) = d_M(P₂, P₁);

iii. d_M(P₁, P₂)
 d_M(P₁, P₃) + d_M(P₃, P₂) for any P₁, P₂, and P₃.

b. Sketch all the points in the x, y coordinate plane whose Manhattan distance to the origin (0,0) is equal to 1. Do the same for the Euclidean distance.

c. True or false: A solution to the closest -pair problem does not depend on which of the two metrics-d_E
(Euclidean) or d_M
(Manhattan)-is used?