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

[avva]

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

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

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

Comments

[zuber.livejournal.com]

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

[zuber.livejournal.com]

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

[zuber.livejournal.com]

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

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

[zuber.livejournal.com]

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