Геометрические задачи, NP-полные в

37

Ряд геометрических проблем прост, если рассматривать их в , но они являются NP-полными в R d для d 2 (включая одну из моих любимых задач - покрытие диска устройства).R1Rdd2

Знает ли кто-нибудь о проблеме, которая разрешима по полимеру для и R 2 , но является NP-полной для R d , d 3 ? R1R2Rd,d3

В более общем смысле, существуют ли проблемы, NP-полные для но многократные, разрешимые для R k - 1 , где k 3 ?RkRk1k3

Боб Фрейзер
источник
Является ли трехмерное сопоставление геометрическим?
Юкка Суомела
1
на самом деле, нет. «3-мерное» в картезианском, а не евклидовом смысле.
Суреш Венкат

Ответы:

25

Установить покрытие полупространствами.

При заданном наборе точек на плоскости и наборе полуплоскостей, вычисляющих минимальное количество полуплоскостей, покрывающих множества точек, можно решить за полиномиальное время на плоскости. Проблема, однако, заключается в том, что NP трудна в 3d (это сложнее, чем найти минимальное покрытие подмножеством дисков точек в 2d). В 3d вы получаете подмножество полупространств и точек, и вы ищете минимальное количество полупространств, покрывающих точки.

Алгоритм polytime в 2d описан здесь: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

Сариэль Хар-Пелед
источник
Я немного смущен тем, что не знал этого результата, учитывая, насколько он близок к проблемам, над которыми я работаю :-) Это также именно тот ответ, на который я надеялся. Когда вы говорите, что это сложнее, чем обложка диска в 2D, я полагаю, вы имеете в виду, что это APX-сложно?
Боб Фрейзер
1
2d проблема является полиномиальной. Другой - NP-Hard. Тем не менее, я не думаю, что проблема с 3D является APX трудно. Есть веские основания полагать, что PTAS может быть возможен с помощью локального поиска ...
Сариэль Хар-Пелед
... и под этим я подразумевал, что проблема с диском может быть поднята (т.е. уменьшена) до проблемы полупространства в 3d.
Сариэль Хар-Пелед
29

Это не совсем то, что вы спрашиваете, потому что 3d-версия еще сложнее, чем NP-полная, но: Найти кратчайший путь между двумя точками среди полигональных препятствий на плоскости за полиномиальное время (проще всего, построить график видимости двух терминалов и вершины многоугольника и применять Dijkstra, также есть более сложный алгоритм O (n log n) из-за Hershberger и Suri, SIAM J. Comput. 1999), но поиск кратчайшего пути среди многогранных препятствий в 3d является PSPACE-полным (Canny и Reif, FOCS 1987).

Дэвид Эппштейн
источник
10
Вы уверены в плоском корпусе? Алгоритмы, которые вы цитируете, в основном требуют точной реальной арифметики! cstheory.stackexchange.com/questions/4034/…
Джеффс
Er. Хорошая точка зрения. И я не могу выйти из этого, говоря, что нужно использовать плавающую точку и приближенное значение, потому что трехмерная задача может быть хорошо аппроксимирована. К сожалению. Я предполагаю, что существует «точный реальный арифметический» смысл, в котором одно полиномиальное, а другое сложное, но все же, вы правы, это еще один способ, которым он не отвечает на вопрос.
Дэвид Эппштейн
6
Это действительно интересно. Проблема суммы квадратных корней вкрапляется в ряд проблем в cg, где эта проблема будет легкой, если не считать этой детали. В каком-то смысле это здорово, потому что это одна из тех проблем, которые вам нужны, чтобы убедить людей в том, что это сложно. Спасибо за указатели.
Боб Фрейзер
20

Любой невыпуклый многоугольник на плоскости может быть триангулирован за O (n) раз без точек Штейнера; то есть каждая вершина триангуляции является вершиной многоугольника. Более того, каждая триангуляция имеет ровно n-2 треугольника.

Однако определение того, можно ли триангулировать невыпуклый многогранник в R ^ 3 без точек Штейнера, является NP-полным. Результат NP-твердости сохраняется, даже если вам дана триангуляция с одной точкой Штейнера, поэтому даже аппроксимация минимального количества требуемых точек Штейнера является NP-сложностью. [Джим Рупперт и Раймунд Зайдель. О сложности триангуляции трехмерных невыпуклых многогранников. Дискретный компьютер Геом. 1992]

Если данный многогранник является выпуклым, найти триангуляцию легко, но найти триангуляцию с минимальным количеством тетраэдров NP-сложно. [Александр Белов, Хесус де Лоэра и Юрген Рихтер-Геберт. Сложность нахождения малых триангуляций выпуклых 3-многогранников . J. Алгоритмы 2004.]

Jeffε
источник
2
Спасибо за указатели, Джефф. В частности, я думаю, что последний результат, который вы упомянули, интересен. Немного удивительно, что, находясь в плоскости, число симплексов, составляющих многоугольник, является постоянным, но это больше не сохраняется в более высоких измерениях и фактически трудно оптимизировать. Это именно тот ответ, на который я надеялся.
Боб Фрейзер
16

Задача реализуемости для мерных многогранников является кандидатом. Когда d 3 , это разрешимо за полиномиальное время (по теореме Стейница ), но когда d 4 , это NP-трудно. Для получения дополнительной информации, пожалуйста, посмотрите « Пространства реализации 4-многогранников универсальны » Рихтера-Геберта и Циглера (также есть версия arxiv ) и книгу « Лекции по многогранникам » (2-е издание) Циглера.dd3d4

Ёсио Окамото
источник
2
R
Я не видел эту проблему раньше, спасибо.
Боб Фрейзер
Опять же, как и ответ Дэвида Эппштейна, сложнее (вероятно), чем завершить NP.
Питер Шор
11

Решить, является ли метрическое пространство изометрически вложимым в R ^ 2, легко. Тем не менее, NP-трудно решить для встраиваемости R ^ 3.

23

Бумага

Zouzias
источник
Это также хороший пример.
Суреш Венкат
-2

R2R3Z2Z3

k=2Z2Zkk>2,

Каушик Шанкар
источник
что значит сказать, что 2SAT находится "в" R ^ 2?
Суреш Венкат
R2
11
-1: я не вижу, как 2SAT в R ^ 2. Я не вижу, как 2SAT является «геометрической проблемой».
Робин Котари
Я прошу прощения за то, что не представил геометрическую проблему, но хотя заголовок спрашивает о геометрических проблемах, два вопроса в комментариях не указывают, что это геометрическая проблема. Кроме того, 2-выполнимость имеет графическое представление, известное как 2-мерное сопоставление, то есть в P, где 3-выполнимость соответствует 3-мерному сопоставлению, которым является NP.
Каушик Шанкар
@Robin Я продолжил и разъяснил в своем первоначальном комментарии.
Каушик Шанкар