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

37

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

Знает ли кто-нибудь о проблеме, которая разрешима по полимеру для и , но является NP-полной для ? $R^1$ $R^2$ $R^d,d\geq3$

В более общем смысле, существуют ли проблемы, NP-полные для но многократные, разрешимые для , где ? $R^k$ $R^{k-1}$ $k\geq3$

cc.complexity-theory reference-request cg.comp-geom Боб Фрейзер
источник

Является ли трехмерное сопоставление геометрическим?

Юкка Суомела

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

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

Ёсио Окамото
источник

2

\exists R

$\exists\mathbb{R}$

Я не видел эту проблему раньше, спасибо.

Боб Фрейзер

Опять же, как и ответ Дэвида Эппштейна, сложнее (вероятно), чем завершить NP.

Питер Шор

11

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

$\ell_\infty^2$ $\ell_\infty^3$

Бумага

Zouzias
источник

Это также хороший пример.

Суреш Венкат

-2

$R^2$ $R^3$ $Z^2$ $Z^3$

$k = 2$ $Z^2$ $Z^k$ $k > 2$ ,

Каушик Шанкар
источник

что значит сказать, что 2SAT находится "в" R ^ 2?

Суреш Венкат

R^{2}

$R^2$

11

-1: я не вижу, как 2SAT в R ^ 2. Я не вижу, как 2SAT является «геометрической проблемой».

Робин Котари

Я прошу прощения за то, что не представил геометрическую проблему, но хотя заголовок спрашивает о геометрических проблемах, два вопроса в комментариях не указывают, что это геометрическая проблема. Кроме того, 2-выполнимость имеет графическое представление, известное как 2-мерное сопоставление, то есть в P, где 3-выполнимость соответствует 3-мерному сопоставлению, которым является NP.

Каушик Шанкар

@Robin Я продолжил и разъяснил в своем первоначальном комментарии.

Каушик Шанкар

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

Ответы: