Соколинский БорисЕсть идеи, в какую сторону копать?
Если бы точек было большое количество, я бы попробовал построить жадный алгоритм, ползущий от наиболее удалённых от центра точек. А если 10-20... думаю, на таких объёмах хватит и полного перебора. Задачу "построить круг, охватывающий заданные точки", думаю, решить очевидно как :)

maytonЯ-бы шел от центров кластеров точек.
Простой пример: .....(x.....x).....(x.....x).....

Если идти от центра, тяжело решить, стоит ли объединять окружностью центральные точки.

maytonПервый бомбовый удар я обозначу. По скоплению огней.
Плохой выбор. Чтобы добить Северную Америку, при этом радиусе поражения придётся потратить ещё два удара (отмечены красным), в то время как мой подход справится за два вообще (зелёным).

maytonЯ не возражаю. Я хотел подчеркнуть что в реальной задаче как правило цифры могут быть неожиданно (!) бОльшими чем ожидалось.
В реальной задаче должны быть доверительные интервалы. Если конструктору говорят сделать самолёт для пятитонной бомбы, а потом неожиданно (!) хотят повесить на него пятидесятитонную, то это абзац.

maytonЛучше оперировать сразу центром кластера а потом "добивать" тех кто еще "недобит".
Я не думаю, что это лучше чем-либо, кроме удовлетворения ложного интуитивного ощущения, проистекающего из неверной модели последовательных ударов. На самом деле они одновременные и нет никакого "потом". В то же время очевидно, что "центральный" подход лопухнётся на множестве реальных раскладов, а вот где он будет лучше краевого - я сходу и не придумаю.

maytonНо опять-же надо рассмотреть частные случаи. Возможно границу между сотами можно будет без потерь попаданий растянуть. Тоесть расстояние между центрами сот сделать больше чем радиус.
Да не суть. Смотрите: для любых наперёд заданных условий задачи есть оптимальное решение. Мы можем его не знать и не иметь возможности найти, но оно есть. Так вот, Вы фактически постулируете, что оптимальное решение должно содержать определённый ход. Это.... произвольное утверждение, назовём так, и с большой вероятностью оно будет неверным. Ваша же иллюстрация показывает это лучше всего, поскольку "первый ход" оказывается просто лишним, после него оказывается необходимым нанести те же удары, что и без него. Подход с края, может быть, и не гарантирует оптимального решения - не возьмусь утверждать - но по крайней мере, не теряет его так откровенно. Крайнюю точку так или иначе надо задеть, и разумно задевать её краем удара - примерно так. Ну а поскольку алгоритм рекурсивный - остатки ведь таки надо "добить", как? да так же, снова в центр оставшегося... получающееся решение.... имхо, не имеет шанса быть близким к оптимальному на правдоподобной выборке начальных раскладов.

maytonЯ предлагаю уйти от алгоритмов которые оперируют точками и подойти к нечётким алгоритмам которые бьют по удельной плотности точек.
Разумность такого подхода категорически зависит от смысла задачи. Думаю, этот подход вполне разумен для планирования предвыборных поездок, но очень сомнителен для планирования бомбардировок.