Hiroimono является популярной головоломкой Complete. Я заинтересован в вычислительной сложности связанной головоломки.
Проблема в:
Входные данные : заданный набор точек на квадратной сетке x n и целое число k
Вопрос : существует ли прямолинейный многоугольник (его стороны параллельны оси или y ), такой, что количество точек на углах многоугольника не меньше k ?
Каждый угол многоугольника должен находиться в одной из точек ввода (поэтому изгибы допускаются только в точке ввода).
В чем сложность этой проблемы? В чем сложность решения, ограниченного выпуклыми прямолинейными многоугольниками?
РЕДАКТИРОВАТЬ 13 апреля: Альтернативная формулировка: Найти прямолинейный многоугольник с максимальными углами на заданных точках.
cc.complexity-theory
np-hardness
puzzles
integer-lattice
Мухаммед Аль-Туркистани
источник
источник
Ответы:
Гаджет узла представлен на следующем рисунке:
источник
Во-вторых, есть прекрасное обновление этой работы Маартена Лёффлера и Елены Мамфорд в статье « Связанные прямолинейные графы на точечных множествах », Журнал вычислительной геометрии , 2 (1), 1–15, 2011. Из их реферата:
источник