Yêu cầu đề bài tương đương với việc tìm cây khung cực tiểu. Giữa hai thị trấn ~i~ và ~j~, thay vì thêm cạnh có trọng số ~min(|x_i − x_j|,|y_i − y_j|)~, ta có thể thêm hai cạnh với trọng số lần lượt là ~|x_i − x_j|~ và ~|y_i − y_j|~. Với ba thị trấn ~i,j,k~ bất kì có ~x_i < x_j < x_k~, ta nhận xét rằng cạnh ~(i,k)~ với chi phí ~x_k−x_i~ sẽ không bao giờ xuất hiện trong cây khung cực tiểu, vì việc sử dụng hai cạnh ~(i, j)~ và ~(j, k)~ với tổng trọng số ~(x_j − x_i) + (x_k − x_j) = x_k −x_i~ sẽ có lợi hơn.

Do đó ta có thể tìm tập các cạnh cần xét (bao gồm ~2∗(N −1)~ cạnh) bằng cách:

• Sắp xếp các thị trấn theo tọa độ ~x~ tăng dần. Trong danh sách đã sắp xếp, với từng cặp thị trấn kề nhau, ta thêm cạnh giữa hai thị trấn này vào tập cạnh cần xét.
• Sắp xếp các thị trấn theo tọa độ ~y~ tăng dần. Trong danh sách đã sắp xếp, ta thêm cạnh giữa hai thị trấn này vào tập cạnh cần xét.

Sau đó, ta tìm cây khung cực tiểu của tập cạnh này (bằng thuật toán Prim, Kruskal hoặc Boruvka).

Độ phức tạp: ~O(NlogN)~