Пытаюсь придумать алгоритм создания палитры цветов. Но для хитрой палитры. Палитра состоит из N базовых цветов + дополнительные оттенки, которые получаются полусуммой любых базовых цветов. К примеру, пусть у нас будет 4 базовых цвета A, B, C, D. Тогда общая палитра будет таковой:

A AB AC AD
  B  BC ВD
     C  CD
        D

При этом выполняется равенство:

AB = (A + B)/2
AC = (A + C)/2
...
CD = (C + D)/2

Если бы не дополнительные оттенки – то проблем бы не было. Выбираем начальные точки медианным сечением, и дальше методом k-средних выводим наиболее оптимальные цифры.

Но для моей ситуации все чуть сложнее. Метод k-средних на каждой итерации смещает центры масс кластеров, что приводит к тому, что равенство перестает выполняться. И на каждой итерации мне нужно производить корректировку центров масс каждого кластера так, что бы исходное равенство снова стало верным.

Т.е. задача алгоритма – найти такие минимальные коэффициенты для каждого кластера, при умножении на которые (или при сложении с которыми?) исходное равенство снова становится верным. При этом каждый кластер имеет свой вес в виде количества цветов, относящихся к данному кластеру. Чем больше вес – тем меньше центр масс кластера должен смещаться.

Подскажите, в каком направлении двигаться.