?

Log in

No account? Create an account
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

алгоритмическая задачка [апр. 23, 2008|12:17 am]
Anatoly Vorobey
(будет интересно только программистам)

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: spamsink
2008-04-22 09:36 pm
В голову пока лезет только инверсия плюс convex hull. Буду думать дальше.
(Ответить) (Thread)
From: ex_decil
2008-04-22 09:46 pm
Навскидку решение следующее:
1. Через каждую точку проводим горизонтальную и вертикальную прямую, в результате наш лист металла оказывается разбит следующим образом:

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

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


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

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

Естественно, процесс можно слегка оптимизировать, например, прямоугольник 3 из последней иллюстрации можно не включать в список вовсе, а также не рассматривать точки на пересечении линий, которые уже находятся в списке добавленных ранее прямоугольников
(Ответить) (Thread)
From: ex_lost_docs526
2008-04-22 09:59 pm
Апиридил :)
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: spartach
2008-04-22 09:58 pm
Точек не очень много? Я бы добавлял их по одной. Когда стоит одна точка, есть четыре возможных максимальных прямоугольника (слева-сверху-справа-снизу от этой точки); при постановке каждой новой точки каждый из прямоугольников, на которые она попала, аналогично заменяем на четыре. Все время, таким образом, храним все потенциально максимальные многоугольники.
(Ответить) (Thread)
[User Picture]From: avva
2008-04-22 10:22 pm
Суть в том, чтобы построить алгоритм, достаточно быстро работающий как фунцкия от n (числа точек).
(Ответить) (Parent) (Thread) (Развернуть)
From: ex_lost_docs526
2008-04-22 09:58 pm
что касается первой задачи, то самый простой способ, пусть и тупой это
1. провести через каждую точку вертикальные и горионтальные линии
2. Получаем сетку из прямоугольников, причем точно знаем что внутри любого прямоугольника дефектных точек нет
3. Теперь тупой перебор всех пар точек А и B (узлов сетки), где В всегда правее и ниже А. Проверяем входит ли дефектная точка в полученный прямоугольник, если нет, то считаем плащадь
4. Выбираем большую площадь из полученных
(Ответить) (Thread)
From: ex_lost_docs526
2008-04-22 10:20 pm
Вторая задачу можно решить также, нужно только поворачивать систему координат.
(Ответить) (Parent) (Thread)
[User Picture]From: egorfine
2008-04-22 10:01 pm
Мне кажется что вторая задача - NP ?
(Ответить) (Thread)
[User Picture]From: avva
2008-04-22 10:22 pm
Почему? Т.е. может быть, я не знаю, но не вижу, почему да.
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: lnvp
2008-04-27 02:46 am
Мне кажется, ваше решение будет выдавать неверный результат. Представьте равномерно густо заполненный точками лист с узкой чистой полосой у одного из краёв. Вы эту полосу выкините как заштрихованную, и пойдёте искать в остатке - где найдёте в результате что-то более мелкое, чем отброшенный на первом шаге узкий край.
(Ответить) (Parent) (Thread)
From: renatm
2008-04-22 11:40 pm
Первую задачу можно решить за 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++.
(Ответить) (Thread)
[User Picture]From: avva
2008-04-23 12:13 am
Неплохо! А быстрее сможете? :-)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: averros
2008-04-23 01:23 am
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).
(Ответить) (Thread)
From: tr1gger
2008-04-23 10:19 am
>> 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).
(Ответить) (Parent) (Thread)
[User Picture]From: raindog_2
2008-04-23 01:27 am
Классная задача. У меня две идеи, обе до конца не доведены.

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

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

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

P.S. У меня есть смутные подозрения, что если обе идеи работают, то идея (2) даст лучшее теоретическое решение, а (1) лучше на практике :)
(Ответить) (Thread)
[User Picture]From: sasha_gil
2008-04-27 04:25 am
По-моему, обе идеи работают. По идее 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). Я лично был стал реализовывать первую идею :)
(Ответить) (Parent) (Thread)
From: jluonel
2008-04-23 03:42 am
Эх, построим эпюры внешних нагрузок, моментов сил и перемещений... раскроем статическую неопределимостьи замутим Основную и эквивалентную систему)
(Ответить) (Thread)
[User Picture]From: denspb
2008-04-23 05:41 am
Интересно, а правда ли, что в случае, если возможен поворот, то стороны повёрнутого прямоугольника-ответа будут параллельны/перпендикулярны либо сторонам исходного листа, либо прямой, проведённой через какую-то пару слабых точек? Тогда за N^2 * время исходного алгоритма можно решить и её.
(Ответить) (Thread)
[User Picture]From: muchacho
2008-04-23 06:06 am
Чукча не читатель, чукча писатель.
Сортируем точки по возрастанию х (х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).
(Ответить) (Thread)
[User Picture]From: oxfv
2008-04-23 07:29 am
А если так: начинаем так же, сортируем точки по х, вбрасываем по одной. В каждый момент имеем набор "открытых" прямоугольников, т.е. тех, которые могут расти вправо с добавлением новых точек. Добавление точки, во-первых, закрывает те прямоугольники, в горизонтальный створ которых она попадает, а во-вторых, образует новые "открытые" прямоугольники. Каждая горизинтальная линия проассоциирована с образовавшей ее точкой, и новые "открытые" прямоугольники получаются между текущей точкой, более ранней точкой (эти перебираются в обратном х-порядке) и ограничивающей горизонталью сверху либо снизу, причем эта ограничивающая горизонталь сперва - верх или низ исходного прямоугольника, а с каждой обработанной ранней точкой сужается. Таким образом, на каждом шаге у нас поддерживается список "открытых" прямоугольников, который, кажется, натуральным образом получается отсортирован по верхней координате. И проходить список точек нужно один раз всего. O(n^2), если не ошибаюсь, но среди "открытых" прямоугольников, кажется, окажутся заведомо неоптимальные (перекрываемые другими "открытыми"), и их надо выкидывать, либо список будет сильно расти.
(Ответить) (Parent) (Thread) (Развернуть)
From: ext_77409
2008-04-23 09:39 am

Жызнено

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

Каждая бы точка, закрывала правым краем все текущие, била бы "напополам" тот, в который бы попала и начинала бы новый левый край.
(Ответить) (Thread)
From: ext_77409
2008-04-23 09:57 am

Re: Жызнено

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

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

Все операции O(log n). Итого O(n log n) с начальной сортировкой.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2008-04-23 10:47 am
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.

(Ответить) (Thread)
[User Picture]From: powerbar
2008-04-23 02:14 pm
many thanks
(Ответить) (Parent) (Thread) (Развернуть)
From: captain_tylor
2008-04-23 01:39 pm
Ну, за 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]) )
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>