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

[avva]

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

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

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

Comments

[sasha-gil.livejournal.com]

По-моему, обе идеи работают. По идее 1 averros отписал: http://avva.livejournal.com/1907181.html?thread=50699245#t50699245 - вес у него просто площадь, а точки лежат в quad tree. Я честно пытался придумать контрпример, но не смог - скорость, с которой плодятся прямоугольники, пропорциональна количеству точек, которые необходимы для полной замены очередного поколения прямоугольников следующим. Разве что можно заставить quad tree себя нехорошо вести - я с quad tree знаком плохо, и не знаю, как это делать.

Решение в духе идеи 2 подробно расписано здесь: http://portal.acm.org/citation.cfm?id=41958.41988 - сложность доказана, но уж больно геморройная сшивка в пункте 3). Я лично был стал реализовывать первую идею :)