алгоритмическая задачка

[avva]

(будет интересно только программистам)

На работе рассказали интересную задачу. Пусть дан прямоугольный лист металла известных размеров. Из-за дефектов производства на листе есть точки, в которых металл слишком слаб - дан список таких точек, с координатами каждой. Задача: найти наибольший по площади прямоугольник внутри листа, не содержащий ни одной дефективной точки внутри себя (на границе - можно).

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

Comments

[avva.livejournal.com]

Почему? Т.е. может быть, я не знаю, но не вижу, почему да.

[marknn.livejournal.com]

Она конечно NP, но в той его части которая заодно является P. Как минимум, есть тривиальное решение за n^5.

[egorfine.livejournal.com]

Я подумал еще раз и растерялся. Я не знаю.

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

Продолжить до тех пор, пока находимые прямоугольники не станут меньше заданого порога.

Это совсем сырая базовая идея. Примерно понятно, как к ней прикрутить вращение. Я бы так думал.

Не NP Меньше или равно N^6

[qaraabayna.livejournal.com]

Перебор всех четверок - O(N^4)

Перебор всех поворотов и соответствующих описанных прямоугольников для каждой четверки. Число поворотов - O(N). На каждом повороте определяется входит ли какая либо точка в прямугольник - O(N)

Re: Не NP Меньше или равно N^6

[qaraabayna.livejournal.com]

Забыл O(N) необходимое для определения каждого следующего поворота.