Разделить все точки на пары с минимальным расстоянием

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

Самый простой вариант - для каждой точки находить расстояние со всеми и выбирать минимальное. Но тогда получится, что оставшиеся в конце точки будут с максимальным расстоянием. А так не должно быть

Есть точки на координатной плоскости. Нужен алгоритм, как разделить все точки на пары с минимально возможным расстоянием у всех. Пары типа A-B, B-C, C-D (в любом порядке, каждая точка должна встречать в двух парах).