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

[avva]

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

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

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

Comments

[zuber.livejournal.com]

Начальное условие: неупорядоченное множество точек и дерево отобранных прямоугольников, содержащее единственный лист -- исходный прямоугольник.

Берём точку и перебираем листья дерева прямоугольников, проверяя принадлежность точки. Если точка лежит в пределах очередного листа, пристраиваем к нему 4 новых листа (деление этого прямоугольника вертикалью и горизонталью, проходящей через точку). Если точка лежит на границе, будет только 2 листа. Если на углу -- точка повторяется, делить нечего. Переходим к следующей точке и повторяем, пока они не кончатся.

По окончании ещё раз перебираем листья и находим самый большой.

[zuber.livejournal.com]

Upd: когда точка лежит на границе, новых листьев добавлять не надо.

[zuber.livejournal.com]

Например, такое дерево:

[zuber.livejournal.com]

И очевидное направление оптимизации: не перебирать все листья для очередной точки, а "спускать" точку из вершины, отсекая сразу ложные направления.

Если в указанном примере была бы четвёртая точка вблизи левого верхнего угла, перебор множества листьев второй и четвёртой ветви заведомо не даст результата.

[zuber.livejournal.com]

Следующий этап оптимизации заключается в упорядочивании точек. Есть ощущение, что надо начинать с точки, вертикаль и горизонталь через которую поделит точки на примерно равное количество. На следующих этапах в каждом из полученных горизонтальных и вертикальных прямоугольников берётся "средняя" точка, лежащая в их пределах. Это сделает "спуск" точки более эффективным.