Если вы настаиваете на точном разбиении, то вам нужно вычислить все сбалансированные разбиения набора точек на плоскости по линии (оптимальное разбиение - это разбиение Вороного, поэтому два набора точек разделены линией). Такие разделы известны какk-множествами. Самый быстрый алгоритм, известный в настоящее время для этой работы вO(n4/3logn) для вычисления этих разделов в двойном [т.е. kУровень набора n линии, для k=n/2]. Когда у вас есть все возможные разделы, вам просто нужно проверить каждый из них. Используя стандартные приемы, это можно сделать за постоянное время для каждого раздела.
(Обновление: доказательство того, что оптимальный раздел реализуется k-установить для k=n/2не совсем тривиально. Я бы оставил это как милое упражнение для заинтересованного читателя. Подсказка: рассмотрите линию, проходящую через два оптимальных центра, и направление, перпендикулярное к нему.)
Если вам нет дела до точного решения, тогда более простым подходом будет использование kозначает кластеризацию. Это приведет кO(ϵ−2logn) взвешенные точки в этом случае, с общим весом n, Затем вам просто нужно решить проблему с помощью взвешенного набора точек. Самым простым решением было бы создать набор подходящих местоположений для центров и проверить все пары на взвешенных точках. Конструкция coreset и создание центров-кандидатов описаны в этой статье:
http://sarielhp.org/p/03/kcoreset/
Сариэль Хар-Пелед
источник