Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.07.2009, 01:36
Tatiana

 
Сообщений: n/a

Квадрат минимальной площади покрывающий множество точек
Здравствуйте,
Есть какие нибудь идеи по поводу вот такой задачи:
Дано множество точек на плоскости, найти минимальный квадрат, который бы их покрывал.
Спасибо заранее
  #2  
Старый 03.07.2009, 02:23
гость

 
Сообщений: n/a

Квадрат с осями параллельными координатными, или произвольный квадрат?

Сколько точек? (т.е. с какой ассимптотикой желательно получить решение?)
  #3  
Старый 03.07.2009, 04:28
Tatiana

 
Сообщений: n/a

For a given set of (x,y) coordinates, find the smallest square that contains them all. If the points land on the edge of the square with four decimal places of precision or better, they will be considered “Contained within the square”. The square is not necessarily parallel to the axes.
  #4  
Старый 03.07.2009, 05:25
гость

 
Сообщений: n/a

Не цитируйте, приводите ссылку на источник задачи!

Длину стороны можно искать двоичным поиском. Любой квадрат параллельным переносом и сжатием можно преобразовать так, чтобы на двух его параллельных сторонах лежали точки из покрываемого множества. Соответственно можно перебрать все возможные пары точек, по любой паре точек на противоположных сторонах и длине стороны почти однозначно (возможна всего пара вариантов) восстанавливаются параллельные прямые-стороны квадрата, на которых лежат эта пара точек. Остальные две стороны получаются просто проецироваение всех точек на эти прямые, и нахождением минимума/максимума.
Итого получаем время работы алгоритма O(n^3 log 1/ε), где ε - требуемая точность нахождения длины стороны.
  #5  
Старый 03.07.2009, 08:38
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Прямоугольник минимальной площади можно найти, если не ошибаюсь, за O(nlogn) с помощью rotаting calipers. Можно ли подобным образом найти квадрат - не знаю, могут быть тонкости...
  #6  
Старый 06.07.2009, 07:35
Tatiana

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Не цитируйте, приводите ссылку на источник задачи!

Длину стороны можно искать двоичным поиском. Любой квадрат параллельным переносом и сжатием можно преобразовать так, чтобы на двух его параллельных сторонах лежали точки из покрываемого множества. Соответственно можно перебрать все возможные пары точек, по любой паре точек на противоположных сторонах и длине стороны почти однозначно (возможна всего пара вариантов) восстанавливаются параллельные прямые-стороны квадрата, на которых лежат эта пара точек. Остальные две стороны получаются просто проецироваение всех точек на эти прямые, и нахождением минимума/максимума.
Итого получаем время работы алгоритма O(n^3 log 1/ε), где ε - требуемая точность нахождения длины стороны.
Спасибо большое за идею! пришлось хорошенько вспомнить геометрию, но в итоге программа написана и сейчас тестирую...
Ссылку на источник оставить не могу к сожалению - задачка в интернете не опубликована.
  #7  
Старый 22.12.2009, 15:54
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

у меня несколько похожая проблема:
нужно опуклую оболочку описать треугольником наименьшей площади.
Есть какие-то идеи?
  #8  
Старый 22.12.2009, 18:49
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

У меня есть решение и программа на С++.
А вот объяснять, как это работает слишком долго и сложно.
Демо находится здесь здесь.
Если коротко, то берётся прямоугольный равнобедренный треугольник и ищется такое аффинное преобразование, которое преобразует этот треугольник в минимальный по площади и такой, что все заданные точки лежат внутри него.
  #9  
Старый 23.12.2009, 03:07
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

Спасибо большое за такую многофункциональную программу!
Но мне бы хотелось углубиться в алгоритм поиска афинного преобразования(или, возможно, какой-то другой пригодный для этой задачи алгоритм) и определить его сложность. Из кода это сделать - не самое тривиальное задание.
Лучшее что я нашел по этой теме - это вот эту статью: http://www.cccg.ca/proceedings/2004/38.pdf
Но там приведено описание для конкретного заданого угла и треугольник берется равнобедренный (хотя, я кажется уже доказал для себя, что он должен быть именно равнобедренным).
Может быть, у Вас есть какой-то теоретический материал?

Последний раз редактировалось saqwer, 23.12.2009 в 04:29.
  #10  
Старый 23.12.2009, 11:53
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

У меня есть статья о том, как получить описанный треугольник минимального периметра. Сам я её ещё не изучал ( отложил на будущее ). Посмотрите, может пригодится ( файл приложен ). Замечу, что в данном случае треугольник с мин. периметром мне кажется более естественным, чем треугольник с мин. площадью.
Вложения:
Тип файла: zip Мин.треугольник.zip (64.4 Кб, 36 просмотров)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение фигуры максимальной площади alienlab Вычислительная геометрия 1 28.04.2009 20:14
Гамильтонов путь минимальной длины гость Графы 5 24.02.2009 01:27
Квадрат гость Задачи 2 17.02.2009 06:48
Покрытие минимальной мощности Marat Galeyev Графы 5 03.01.2008 18:36
максимальны поток минимальной стоимости незарегистрированный Графы 1 28.12.2006 17:37