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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.05.2010, 19:12
гость

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

Минимальное число тетраедров
Пожалуйста, помогите найти полиномиальный алгоритм
нахождения минимального количества тетраедров для триангуляции выпуклого многоугольника
  #2  
Старый 27.05.2010, 21:28
MBo MBo вне форума
Местный

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

Тетраэдр - трехмерный, а многоугольник - двумерный. Уж определитесь, "кто на ком стоял"...
  #3  
Старый 28.05.2010, 15:55
гость

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

Постановка не совсем правильна, имееться ввиду 3хмерные фигуры
  #4  
Старый 28.05.2010, 17:07
MBo MBo вне форума
Местный

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

ОК, значит, выпуклых многогранников
Гугл подсказал, что эта задача NP-Hard:
http://portal.acm.org/citation.cfm?i...TOKEN=12745921
  #5  
Старый 06.06.2010, 12:36
гость

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

Cпасибо большое!
Если кому-то еще нужно, вот эта статья в кеше
http://hub.hku.hk/bitstream/123456789/45628/1/57601.pdf
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
второе минимальное остовное дерево sawe Реализация, исходники, языки 7 04.09.2008 19:15
минимальное расстояние между окружностями в 3-х мерном пространстве Miranda Вычислительная геометрия 3 02.09.2008 16:28
Минимальное расстояние между двумя конусами Vektor64 Вычислительная геометрия 1 26.08.2008 14:07
минимальное стягивающее дерево по критерию максимальной живучести ТРСО andrew_zol Графы 0 21.06.2007 03:08
минимальное расстояние andy_84 Математические алгоритмы 3 16.12.2006 16:01