Сложность головоломки скрытого многоугольника на квадратных сетках?

10

Hiroimono является популярной головоломкой Complete. Я заинтересован в вычислительной сложности связанной головоломки.NP

Проблема в:

Входные данные : заданный набор точек на квадратной сетке x n и целое число knnk

Вопрос : существует ли прямолинейный многоугольник (его стороны параллельны оси или y ), такой, что количество точек на углах многоугольника не меньше k ?xyk

Каждый угол многоугольника должен находиться в одной из точек ввода (поэтому изгибы допускаются только в точке ввода).

В чем сложность этой проблемы? В чем сложность решения, ограниченного выпуклыми прямолинейными многоугольниками?

РЕДАКТИРОВАТЬ 13 апреля: Альтернативная формулировка: Найти прямолинейный многоугольник с максимальными углами на заданных точках.

Мухаммед Аль-Туркистани
источник
4
Разве выпуклые прямолинейные многоугольники не должны быть разрешимы за полиномиальное время динамическим программированием?
Питер Шор
4
Да, так и должно быть.
Джефф
@JeffE, как насчет общего невыпуклого случая? Каков твой наклон?
Мухаммед Аль-Туркистани
2
для многих из этих проблем лучше всего начать с чего-то вроде плоского 3SAT или даже плоского NAE-SAT. Это будет ужасно уродливо, но планарность дает вам структуры, которые вам могут понадобиться.
Суреш Венкат
5
@Suresh Просто примечание: поглядывая вокруг, я обнаружил, что планарная версия NAE3SAT находится в P ( portal.acm.org/… ).
Марцио Де Биаси

Ответы:

6

3yx значение ) содержали не более одного узла. График можно масштабировать, а каждый узел можно заменить квадратным гаджетом со многими точками; горизонтальные связи между гаджетами (края исходного графика) выполняются с использованием пар точек в разных строках, вертикальные ссылки - с использованием пары точек в разных столбцах. Обходы узлов вынуждены использовать «много точек» квадратных гаджетов.

Гаджет узла представлен на следующем рисунке:

введите описание изображения здесь

[W,N,E]C×CC2C2C+2C×C4+6[N,E,S][E,S,W][S,W,N]

(x1,y1),(x2,y2)x1x2y1y24×3

введите описание изображения здесь

EW

введите описание изображения здесь

4+2C2e

neC>(4n+2e)k=2Cn

Марцио де Биаси
источник