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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.11.2010, 19:29
Новичок

Отправить личное сообщение для vmyrik Посмотреть профиль Найти все сообщения от vmyrik
 
Регистрация: 19.11.2010
Сообщений: 6

Генерация простых многоугольников
Пускай задано фиксированное множество S из N точек на плоскости. Необходимо разработать алгоритм генерации простых многоугольников, вершинами которых есть все точки заданной плоскости S и определить многоугольник минимальной площади.
  #2  
Старый 19.11.2010, 23:54
гость

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

Наивный алгоритм
Перебрать все перестановки точек из S. Каждая перестановка порождает многоугольник. Если в мног-ке есть самопересечения, его отбрасываем, если нет, считаем его площадь и отбираем нужный.
  #3  
Старый 20.11.2010, 00:32
Новичок

Отправить личное сообщение для vmyrik Посмотреть профиль Найти все сообщения от vmyrik
 
Регистрация: 19.11.2010
Сообщений: 6

Сообщение от гость Посмотреть сообщение
Перебрать все перестановки точек из S. Каждая перестановка порождает многоугольник. Если в мног-ке есть самопересечения, его отбрасываем, если нет, считаем его площадь и отбираем нужный.
Слишком большая сложность. Может есть что-нибудь оптимальнее?

Как вариант: Для этого множества построить выпуклую оболочку, а потом в цикле для оставшихся точек и ребер оболочки искать треугольник максимальной площади, который можно отрезать, и таких треугольников мы выбросим столько, сколько точек было внутри оболочки.
Сложность порядка O(N^4)
Но вопросом остается то, получим ли мы в итоге именно минимальную возможную площадь(хотя по логике - да, ведь на каждом шаге отрезаем максимум)
  #4  
Старый 20.11.2010, 10:10
гость

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

Ваше решение не достигает результата. Представьте себе тонкую спираль на пару-тройку витков. Она и есть оптимум, т.к. ее площадь можно как угодно уменьшать. А Ваш greedy алгоритм ее пропустит.
А вот перебор перестановок, с отсечением всех подмножеств сразу после появления пересечения, хотя бы гарантирует полный ответ. При правильной организации перебора не будет лишних\повторных вычислений.
  #5  
Старый 20.11.2010, 10:16
гость

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

Да, насчет сложности. Сложность определяется количеством многугольников. Мне кажется, это экспонента, поэтому задача NP-hard.
А хорошо оценить число многоугольников так сразу не берусь.
  #6  
Старый 20.11.2010, 11:45
Новичок

Отправить личное сообщение для vmyrik Посмотреть профиль Найти все сообщения от vmyrik
 
Регистрация: 19.11.2010
Сообщений: 6

Сообщение от гость Посмотреть сообщение
Ваше решение не достигает результата. Представьте себе тонкую спираль на пару-тройку витков. Она и есть оптимум, т.к. ее площадь можно как угодно уменьшать. А Ваш greedy алгоритм ее пропустит.
А вот перебор перестановок, с отсечением всех подмножеств сразу после появления пересечения, хотя бы гарантирует полный ответ. При правильной организации перебора не будет лишних\повторных вычислений.
То есть вы хотите сказать, что площадь спирали равна 0? А края, вроде как, не замкнуты? Похоже на вырожденный случай.
  #7  
Старый 20.11.2010, 11:55
гость

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

Нет, я хочу сказать, что площадь спирали можно сделать заведомо меньшей, чем полученная жадным алгоритмом.
  #8  
Старый 20.11.2010, 12:04
Новичок

Отправить личное сообщение для vmyrik Посмотреть профиль Найти все сообщения от vmyrik
 
Регистрация: 19.11.2010
Сообщений: 6

Вы не могли бы показать на рисунке, а то сложно так сразу представить, как уменьшить ее площадь, чтоб она осталась многоугольником
  #9  
Старый 21.11.2010, 00:03
гость

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

Нарисуйте сами ломаную закрученную в спираль. А теперь отступите от
всех ее вершин по биссектрисе угла между соседними ребрами на EPS и замкните многоугольник в первой и последней точке таким же коротким ребром. Площадь такого многоугольника будет (почти) L*Eps, где L - длина ломаной. Поскольку Eps можно сделать как угодно малым, то и площадь можно сделать как угодно малой.
Внимание вопрос! Ваш алгоритм умеет строить такие многоугольники?
  #10  
Старый 21.11.2010, 15:16
Новичок

Отправить личное сообщение для vmyrik Посмотреть профиль Найти все сообщения от vmyrik
 
Регистрация: 19.11.2010
Сообщений: 6

Жаль, но нет, не умеет. Видимо, придется остановиться на методе перебора. Хотя он, даже с улучшениями, за приемлемое время обрабатывает 10-12 точек.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Генерация случайных величин Алехандра Математические алгоритмы (другое) 2 13.12.2009 00:51
пересечение многоугольников гость Вычислительная геометрия 12 09.12.2009 23:17
Вычитание многоугольников BOB4uK Математические алгоритмы 3 19.01.2009 17:33
Генерация перестановок длины n Pahan Математические алгоритмы 12 14.01.2009 09:46
генерация текста как? незарегистрированный Реализация, исходники, языки 0 20.11.2006 11:20