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

[avva]

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

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

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

Comments

[spamsink.livejournal.com]

В голову пока лезет только инверсия плюс convex hull. Буду думать дальше.

[ex-decil.livejournal.com]

Навскидку решение следующее:
1. Через каждую точку проводим горизонтальную и вертикальную прямую, в результате наш лист металла оказывается разбит следующим образом:

2. Находим точки на пересечении этих прямых между собой (и прямых с краями листа, естественно):

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


4. Для полученных прямоугольников сохраняем в список координаты углов и площадь.

5. По окончанию 3-4 находим прямоугольник максимальной площади в списке.

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

[ex-lost-docs526.livejournal.com]

Апиридил :)

[ex-lost-docs526.livejournal.com]

и не лень рисовать было....

[ex-decil.livejournal.com]

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

Только надо будет учесть фактор появления непрямых углов между линиями и краями листа.

Где-то так.

[avva.livejournal.com]

Выглядит как O(n^4), я прав? Кол-во точек после второго шага O(n^2), и для каждой точки мы рассматриваем вообще говоря до n разных прямоугольников, и для каждого ищем правую границу за O(n) времени.

Работает, но очень медленно :)

[tr1gger.livejournal.com]

Попробую посчитать: исходных точек -- N. Точек пересечения линий -- N^2. В шаге 3 для одной точки движение вправо -- N, движение вниз -- N, итого -- N^2. Это было для каждой точки пересечения, таким образом время работы = O(N^4). Так?

[spartach.livejournal.com]

Точек не очень много? Я бы добавлял их по одной. Когда стоит одна точка, есть четыре возможных максимальных прямоугольника (слева-сверху-справа-снизу от этой точки); при постановке каждой новой точки каждый из прямоугольников, на которые она попала, аналогично заменяем на четыре. Все время, таким образом, храним все потенциально максимальные многоугольники.

[avva.livejournal.com]

Суть в том, чтобы построить алгоритм, достаточно быстро работающий как фунцкия от n (числа точек).

[ex-lost-docs526.livejournal.com]

что касается первой задачи, то самый простой способ, пусть и тупой это
1. провести через каждую точку вертикальные и горионтальные линии
2. Получаем сетку из прямоугольников, причем точно знаем что внутри любого прямоугольника дефектных точек нет
3. Теперь тупой перебор всех пар точек А и B (узлов сетки), где В всегда правее и ниже А. Проверяем входит ли дефектная точка в полученный прямоугольник, если нет, то считаем плащадь
4. Выбираем большую площадь из полученных

[ex-lost-docs526.livejournal.com]

Вторая задачу можно решить также, нужно только поворачивать систему координат.

[egorfine.livejournal.com]

Мне кажется что вторая задача - NP ?

[avva.livejournal.com]

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

[tsv.livejournal.com]

1. если точек нет - задача решена

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

Делается так:
представить систему координат (для облегчения ориентирования)
расположить прямоугольник более длинной стороной вдоль оси X
находим 4 точки - ближайшую к верхней, левой, правой и нижней границе.

Считаем расстояние от точки до соответствующей границы

если максимальное расстояние >= (0.5*длина соответствующей стороны) то задача решена.
(т.е. если максимальное расстояние - это расстояние от точки до правого края и оно больше либо равно половине длинной стороны прямоугольника)

в противном случае через ближайшую к краю очку проводится прямая, параллельная этому краю, и пространство между проведенной прямой и краем заштриховывается

К оставшемуся прямоугольнику процедура применяется повторно, начиная с шага 1.

P.S. по крайней мере сам понял что написал :)

[lnvp.livejournal.com]

Мне кажется, ваше решение будет выдавать неверный результат. Представьте равномерно густо заполненный точками лист с узкой чистой полосой у одного из краёв. Вы эту полосу выкините как заштрихованную, и пойдёте искать в остатке - где найдёте в результате что-то более мелкое, чем отброшенный на первом шаге узкий край.

[renatm.livejournal.com]

Первую задачу можно решить за O(N^2*log(N)).
Заранее сортируем все точки по возрастанию x. Перебираем левую границу прямоугольника (она может совпадать с левой границей листа или с x-координатой одной из точек), обозначим её x1. Для заданного x1 находим множество y-координат точек, у которых x > x1. Обозначим это множество s. Включим в s y-координаты верхней и нижней границ листа. Находим максимальную разность r среди соседних элементов в s. Обновляем максимальную площадь значением r*(правая_граница-x1). Идем по точкам в порядке уменьшения x. Для текущей точки удаляем ее y-координату из s. Обновляем r = max(r, элемент_справа_от_удаленного_y -элемент_слева_от_удаленного_y). Обновляем максимальную площадь значением r*(x-x1).
Написал запутанно, но как-то так :) Для множества s надо использовать структуру данных на основе сбалансированных деревьем, к примеру set в C++.

[avva.livejournal.com]

Неплохо! А быстрее сможете? :-)

[itman.livejournal.com]

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

[averros.livejournal.com]

Ok, here's something which looks like O(n log n):

1. Put all the dots in a quad tree O(n log n)
2. Take a sorted (by area) list of rectangles. Put the initial rectangle in - O(1).
3. Find a dot within the biggest rectangle, split that rectangle in four (with 2x overlap), and replace the original rectangle with these four O(log n).
4. Repeat 3 until no splitting dots are found. O(n) iterations (I'm not sure about that one, it may be bigger).

[tr1gger.livejournal.com]

>> 3. Find a dot within the biggest rectangle
We should not throw the dot after splitting the rectangle, because it may split another rectangle that becomes the biggest after the split. So, there are more than O(n) iterations, at least O(n^2).

[raindog-2.livejournal.com]

Классная задача. У меня две идеи, обе до конца не доведены.

(Идея 1) Держим priority queue (PQ) из прямоугольников, каждому из которых присваивается вес, некоторым образом соответствующий верхней оценке максимальной площади. На каждом шаге: выгребаем из PQ прямоугольник с максимальным весом. Если в нем нет точек, задача решена, это оптимум. Если нет, выбираем точку поближе к середине, которая делит прямоугольник на две пары прямоугольников, и кладем эти четыре прямоугольника в PQ. Фокус в том, как выбрать функцию веса, которая была бы монотонной (чтобы гарантировать глобальный оптимум) и которую было бы быстро вычислять.

(Идея 2) Делим прямоугольник горизонтально, примерно пополам. Горизонтальные границы решения лежат
1) обе сверху
2) обе снизу
3) одна сверху, одна снизу.
Случаи (1) и (2) - неинтересные, они уменьшают N вдвое, то есть выгодны для нас. Рассмартивать нужно случай (3). Теперь хорошо бы разделить обе половинки, верхнюю и нижнюю, тоже надвое, и посмотреть, что получается.
Да, точки заранее нужно осортировать по горизонтали или даже положить в kd-tree.
В-общем, идея - свести задачу нахождения верхней и нижней границы к чему-то быстрому, логарифмическому.

Завтра я лечу через океан, будет время обдумать.

P.S. У меня есть смутные подозрения, что если обе идеи работают, то идея (2) даст лучшее теоретическое решение, а (1) лучше на практике :)

[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). Я лично был стал реализовывать первую идею :)

[jluonel.livejournal.com]

Эх, построим эпюры внешних нагрузок, моментов сил и перемещений... раскроем статическую неопределимостьи замутим Основную и эквивалентную систему)

[denspb.livejournal.com]

Интересно, а правда ли, что в случае, если возможен поворот, то стороны повёрнутого прямоугольника-ответа будут параллельны/перпендикулярны либо сторонам исходного листа, либо прямой, проведённой через какую-то пару слабых точек? Тогда за N^2 * время исходного алгоритма можно решить и её.

[muchacho.livejournal.com]

Чукча не читатель, чукча писатель.
Сортируем точки по возрастанию х (х1, х2...).
Первый рассматриваемый прямоугольник - с краю, по высоте листа (Н), площадь прямоугольника = х1*Н. Дальше точка 1 делит его на два, высотой у1 и Н-у1. Точка 2 делит один из этих двух; чтобы найти какой, нужно log(2) операций, если хранить прямоугольники в упорядоченном по у списке. Проверяем площадь прямоугольника, который упирается в точку 2 (у1*х2, либо (Н-у1)*х2). Далее, для каждой точки i нужно log(i) операций для поиска разделяющегося прямоугольника, в сумме O(log(n!))=O(n*log(n)).
Далее повторяем всю процедуру, но стартуем от точки х1, а не с краю. Всё равно получается n^2*log(n).

[oxfv.livejournal.com]

А если так: начинаем так же, сортируем точки по х, вбрасываем по одной. В каждый момент имеем набор "открытых" прямоугольников, т.е. тех, которые могут расти вправо с добавлением новых точек. Добавление точки, во-первых, закрывает те прямоугольники, в горизонтальный створ которых она попадает, а во-вторых, образует новые "открытые" прямоугольники. Каждая горизинтальная линия проассоциирована с образовавшей ее точкой, и новые "открытые" прямоугольники получаются между текущей точкой, более ранней точкой (эти перебираются в обратном х-порядке) и ограничивающей горизонталью сверху либо снизу, причем эта ограничивающая горизонталь сперва - верх или низ исходного прямоугольника, а с каждой обработанной ранней точкой сужается. Таким образом, на каждом шаге у нас поддерживается список "открытых" прямоугольников, который, кажется, натуральным образом получается отсортирован по верхней координате. И проходить список точек нужно один раз всего. O(n^2), если не ошибаюсь, но среди "открытых" прямоугольников, кажется, окажутся заведомо неоптимальные (перекрываемые другими "открытыми"), и их надо выкидывать, либо список будет сильно расти.

Жызнено

[failhigh.wordpress.com (from livejournal.com)]

Хорошая задачка, но жызненая.
Сразу приходит в слово Plane Sweep.
Понимаешь, что нужно отсортировать точки.
Потом нужно поддерживать структуру, которая бы содержала текущие прямоугольники. В ней нужно как-то искать и т.д.

Каждая бы точка, закрывала правым краем все текущие, била бы "напополам" тот, в который бы попала и начинала бы новый левый край.

Re: Жызнено

[failhigh.wordpress.com (from livejournal.com)]

Стоп, а у меня O(n * log n).

Пусть H - высота большого прямоугольника.
На каждой точке следующие операции:
* Вставить прямоугольник высотой H с левым краем в точке.
* Найти прямоугольник, который разделяется точкой на два. Выбросить его с правым краем в точке и поделить его на два и тянуть дальше.

Все операции O(log n). Итого O(n log n) с начальной сортировкой.

[(Anonymous)]

Look at

B.Chazelle, R.Drysdale, D.Lee
Computing the largest empty rectangle, SIAM J Comp 15 (1986) 300-315

M.Orlowski
A new algorithm for largest empty rectangle problem, Algorithmica 5 (1990) 65-73

For arbitrary orientation:

A.Mukhopadkhyay, S.Rao
On computing a largest empty arbitrarily oriented rectangle, Internat. J. Comput. Geom. Appl. 13 (2003) 257--271.

[powerbar.livejournal.com]

many thanks

[captain-tylor.livejournal.com]

Ну, за n^2 решается обычным динпрогом.

x[i], y[i] - координаты точки, имеющей порядковый номер i в списке, отсортированном по возрасатанию x.

t и b равны следующему
t[a,b] = min (y[c] : y[c]>=y[a], x[a]<=x[c]<=x[b])
b[a,b] = max (y[c] : y[c]<=y[a], x[a]<=x[c]<=x[b])

Считаются рекурсивно так за n^2
t[a,b] = (y[b-1]>y[a]) ? min(t[a,b-1],y[b-1]) : t[a,b-1]
b[a,b] = (y[b-1]<y[a]) ? max(b[a,b-1],y[b-1]) : b[a,b-1] Ответ - max( (t[a,b] - b[a,b]) * (x[b]-x[a]) )

[dfyz.livejournal.com]

Такая задача была на топкодере (http://www.topcoder.com/tc), есть editorial (http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm357#4593) с её разбором.

(Если не хочется регистрироваться, чтобы читать условие: точки генерируются псевдослучайно внутри квадрата 1×1; гарантируется, что их не больше чем 25000.)

[avva.livejournal.com]

Ага, я не пользуюсь топкодером, факт. Не на мой вкус. Спасибо за ссылку на разбор.

[zuber.livejournal.com]

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

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

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

[zuber.livejournal.com]

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