Точное решение с доказательством я привести не могу, но могу дать несколько направлений.
Первый вариант
Можно построить частный случай Kd-дерева, когда каждой области принадлежит по 1 точке, а после начать объединять области снизу, используя данное условие. Если точки находятся "близко", то они будут соседями на соседних уровнях, и поэтому объединятся в первую очередь.
Второй вариант
Второй вариант предполагает построение диаграммы Вороного. Для каждой точки находим ближайшие границы. Области можно объединять только с областями, которые смежные с данными границами. В данном случае будет усеченный перебор, так как в среднем у каждой точки будет мало таких границ. Худший случай - точки расположены строго по гексагональной сетке.

Рекомендую посмотреть "Mark de Berg - Computational Geometry Algorithms and Applications". Там будет описание построения данных структур.
Я бы начал с первого варианта, так как Kd деревья реализуются достаточно просто и информации по ним больше, возможно, даже можно найти пример с объединением по условию, так как эти деревья имеют много применений. Диаграммы Вороного проще "дебажить" графически и есть много реализаций на разных языках, поэтому базу можно быстрее сделать.
Если отталкиваться от "в приоритете близость точек друг к другу и равное количество для каждой зоны", то диаграммы Вороного могут быть лучше, так как у них при построении похожая задача стоит. Возможно, можно доказать транзитивность этого условия между областями. Тогда достаточно будет построить диаграмму второго порядка, их в книге вроде нет, но можно найти несколько статей на эту тему. К сожалению, готовых реализаций для диаграмм высших порядков я не встречал, поэтому придется писать самостоятельно.