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

Учитывая набор точек в трехмерном декартовом пространстве, я ищу алгоритм, который будет сортировать эти точки так, чтобы минимальное евклидово расстояние между двумя последовательными точками было бы максимальным.

Было бы также полезно, если бы алгоритм имел тенденцию к увеличению среднего евклидова расстояния между последовательными точками.

graph-algorithms cg.comp-geom optimization Лиор Коган
источник

Crossposted , мотивация .

Юкка Суомела

Похоже на максимизацию версии узкого места TSP . Или узкая версия самой длинной проблемы пути . У него есть имя?

Юкка Суомела

Я бы порекомендовал использовать эвристику k-кластеризации Гонсалеса (жадная стратегия). не думая об этом полностью, кажется, что это должно привести к 2-приближению?

Суреш Венкат

К сожалению, как уже говорилось, Гонсалес не даст хорошего ответа (рассмотрим точки (-100,0), (99,0) и (100,0)). Например, если мы начнем с неправильной точки (-100,0), мы получим ужасный ответ. Все еще возможно, что запуск Гонсалеса из любой точки и принятие наилучшего ответа будет работать.

Суреш Венкат

Ответы:

ETA: все ниже в статье « О максимальном разбросе TSP », Arkin et al, SODA 1997.

Я не знаю точных ответов, но вот другой подход, который немного отличается от предложения Суреша о кластеризации Гонсалеса:

Предположим для простоты, что четно. Для каждой вершины найдите медиану из расстояний . Сформируйте неориентированный граф, в котором каждая вершина соединена с другими вершинами, которые находятся на расстоянии, по меньшей мере, среднего расстояния. Минимальная степень в этом графе не менее , поэтому по теореме Дирака в этом графе можно найти гамильтонов цикл. $n$ $p$ $n-1$ $d(p,q)$ $p$ $n/2$

С другой стороны, в диске есть вершин с центром в точке с радиусом , их слишком много, чтобы образовать независимое множество в цикле, поэтому любой гамильтонов цикл должен иметь ребро, соединяющее некоторые две из этих вершин длиной не более . Следовательно, гамильтонов цикл, найденный этим алгоритмом, в худшем случае является 2-приближением цикла максимума узкого места. $n/2 + 1$ $p$ $d(p,q)$ $2d(p,q)$

Это будет работать в любом метрическом пространстве и дает оптимальный коэффициент аппроксимации среди алгоритмов, которые работают в любом метрическом пространстве. Ибо, если бы вы могли приблизиться лучше, чем с точностью до двух, то вы могли бы точно решить задачи о гамильтоновом цикле, сведя входной граф к задаче о гамильтоновом цикле в метрическое пространство с расстоянием 2 для каждого ребра графа и расстоянием 1 для каждого не -Станок.

Вероятно, с некоторой осторожностью вы можете втирать это в алгоритм приближения для путей вместо циклов.

Дэвид Эппштейн
источник

Есть ли основания полагать, что в евклидовом случае нет PTAS?

Юкка Суомела

Нет причин, о которых я знаю. Но обычные методы PTAS для задач проектирования евклидовых сетей работают только для минимизации, а не максимизации.

Дэвид Эппштейн

Единственное исключение, о котором я знаю, это статья Чена и Хар-Пеледа о PTAS для спортивного ориентирования в самолете. Это проблема максимизации.

Чандра Чекури

Мы загрузили препринт, который решает этот вопрос, то есть дает PTAS для TSP максимального рассеяния в евклидовом случае. arxiv.org/abs/1512.02963 (Ласло Козма, Тобиас Момке: PTAS для TSP для евклидового максимального рассеяния)

Ласло Козма

Мы загрузили препринт, который решает этот вопрос, то есть дает PTAS для TSP максимального рассеяния в евклидовом случае. http://arxiv.org/abs/1512.02963 (Ласло Козма, Тобиас Момке: PTAS для TSP для евклидового максимального рассеяния)

Ласло Козьма
источник