Отсортируем сначала пары по a.
Найдем пару с максимальным b — это корень дерева, все пары левее ее будут в левом поддереве, остальные — в правом.
Рекурсивно строим левое и правое поддерево тем же алгоритмом.
Чтобы быстро искать максимум можно использовать, например, дерево отрезков.

Ещё можно явно построить декартово дерево, поочерёдно добавляя в него вершины, прежде отсортировав их по b в порядке уменьшения, чтобы избежать обработки вырожденных деревьев за квадрат.