Путешествие на кратчайшее расстояние - обычное место встречи

Я столкнулся с этой проблемой, когда есть несколько домов на 2-мерной сетке (их координаты даны ), и мы, по сути, должны найти, какой дом можно использовать в качестве места встречи, чтобы минимизировать расстояние, пройденное всеми. Предположим, что расстояние по оси x или y составляет 1 единицу, а расстояние до диагональных соседей - (скажем) 1,2 единицы.

Я не могу придумать для этого хороший алгоритм оптимизации.

P.S: Это не домашнее задание. И я ищу только алгоритм (а не код) и, если возможно, его доказательство.

P.S # 2: Я не ищу исчерпывающего решения. Вы не поверите, но это меня поразило :)