Exercise 1.1.1:

We have to give a counterexample. The first counterexample can be produced when $N = 2$. Imagine we have $2N = 4$ points:

  • $A(3,10)$,
  • $B(4,-2)$,
  • $C(5,2)$ and
  • $D(7,4)$.

Now the optimality of the greedy solution will depend on the order in which the points are chosen. In case of $N = 2$, there are two possible orders.

  1. Choosing $A$ first, pair $(A,D)$ and $(B,C)$. Total cost = $\sqrt{52} + \sqrt{17} \approx 11.33$.

    The first setup

  2. Choosing $C$ first, pair $(C,D)$ and $(A,B)$. Total cost = $\sqrt{8} + \sqrt{145} \approx 14.87$

    The second setup

So, greedy will not produce optimal result if we choose $C$ first.