Растущий график по набору (х, у) указывает

Question

Проблема:

Учитывая набор 2D точек на плоскости, найти множество ребер E, что сводит к минимуму как среднее время в пути между любыми двумя точками и размер E: то есть путем сопоставления стоимости r с каждой единицей времени отключения и стоимостью e за край в комплекте.

Я уверен, что есть набор алгоритмов, которые справляются с этой проблемой, но я не могу найти правильный поисковый запрос. Я подумал, что начинаю с полного графика и обрезки, но я не могу придумать эффективный способ рассчитать ущерб, нанесенный удалением края. Какие-либо предложения? Приближенные («достаточно хорошие») решения приветствуются.

Сообщите мне, если мое заявление о проблеме может быть улучшено или уточнено.

Answer 1

В литературе есть некоторая работа на spanners, которая связана с тем, что вы описываете (основное различие заключается в том, что гаечные ключи управляют максимальным растяжением, в то время как вы обеспокоены средним). Конструкция Чью («Существует планарный граф, почти такой же хороший, как полный график», SoCG '86) дает O (1) -приближение для вашей проблемы, поскольку триангуляция имеет в три раза больше ребер, чем остовное дерево (нижняя граница на оптимуме, так как граф должен быть связан) и настраивает каждое евклидово расстояние не более чем на квадрат (10) (следовательно, sqrt (10) умножает среднее значение для оптимального).