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

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

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

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

Сообщение от prografix Посмотреть сообщение
Неверно, точки второго множества могут не принадлежать выпуклой оболочки первого множества, но при этом разделяющей плоскости не будет, т.к. точки охватывают выпуклую оболочку снаружи.
Верно, я ошибся.
  #12  
Старый 04.01.2010, 15:56
Новичок

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

Сообщение от prografix Посмотреть сообщение
Неверно, точки второго множества могут не принадлежать выпуклой оболочки первого множества, но при этом разделяющей плоскости не будет, т.к. точки охватывают выпуклую оболочку снаружи.
Ну, для проверки этого факта достаточно проверить лежит ли любая из точек первого множества внутри произвольного тетраедра, построенного на 4х точках второго множества (сложность О(1)).
Но как я понимаю, выпуклую оболочку строить все равно придется, не так ли?
  #13  
Старый 04.01.2010, 17:11
гость

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

Да, это коррекно: дважды проверить принадлежность точек одного множества вып.оболочке другого.
Но все-таки это выглядит сложновато.
Надо найти алгоритм обычным в таких случаях путем: построить разделяющую линию для
плоского случая и поправить его для пространства.
Для 2Д это понятный алгоритм (описывать не буду, как говорится, многабукв).
А решение в 3Д в определенной проекции будет и решением в 2Д для проекций точек.
  #14  
Старый 04.01.2010, 19:26
Местный

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

Сообщение от гость Посмотреть сообщение
Да, это коррекно: дважды проверить принадлежность точек одного множества вып.оболочке другого.
Опять неверно. Вот контр-пример: два куба пересекаются в области рёбер. Все вершины не попадают внутрь выпуклой оболочки, тем не менее разделяющей плоскости не существует.
Я уже писал, как решить эту задачу - надо свести её к задаче линейного программирования ( тут возможны варианты ).
  #15  
Старый 05.01.2010, 08:30
Новичок

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

Сообщение от prografix Посмотреть сообщение
Я уже писал, как решить эту задачу - надо свести её к задаче линейного программирования ( тут возможны варианты ).
Расскажите, если можно, каким образом Вы собираетесь сводить эту задачу к ЗЛП и про какие варианты идет речь?
  #16  
Старый 05.01.2010, 12:18
Местный

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

Пусть точки первого множества имеют координаты ( xi, yi, zi ), а второго множества ( xj, yj, zj ). Тогда разделяющую плоскость можно задать в виде неравенств:
a*xi + b*yi + c*zi + d - h > 0
a*xj + b*yj + c*zj + d + h < 0
Теперь найдём максимальное h. Если оно будет больше нуля, то значит множества разделяемые и разделяемая плоскость имеет параметры ( a, b, c, d ). Сложность в том, что эти неравенства не имеют свободных членов, а значит есть некоторый произвол. Можно поступить так зафиксировать какой-то параметр плоскости, например, а, и решить эту задачу дважды ( один раз а = 1, второй а = -1 ). Если в первом случае множества будут разделяемые, то второй раз решать задачу не надо.
Это один вариант. Я знаю ещё один, но пока думаю, что он сложнее.

Последний раз редактировалось prografix, 05.01.2010 в 12:24.
  #17  
Старый 05.01.2010, 20:40
Новичок

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

Сообщение от prografix Посмотреть сообщение
Опять неверно. Вот контр-пример: два куба пересекаются в области рёбер. Все вершины не попадают внутрь выпуклой оболочки, тем не менее разделяющей плоскости не существует.
Кстати говоря, если изменить определение принадлежности точки выпуклой оболочке, на то, где она принадлежит ей, даже если лежит на гранях или ребрах - то алгоритм вполне рабочий.
Только опять же - строить выпуклую оболочку не так уж приятно.
  #18  
Старый 05.01.2010, 21:39
Новичок

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

Я так подозреваю, вы ЗЛП симплекс-методом собираетесь решать, не так ли?
Но сложность симплекс-метода, увы, - экспоненциальная!
И для 1000 точек решать оно мне будет до второго пришествия.
Нужно что-то более радикальнее. Я уже даже склоняюсь к варианту с оболочками.
  #19  
Старый 06.01.2010, 08:20
гость

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

Сообщение от saqwer Посмотреть сообщение
Я так подозреваю, вы ЗЛП симплекс-методом собираетесь решать, не так ли?
Но сложность симплекс-метода, увы, - экспоненциальная!
Это только в самых самых клинических случаях. Вы в жизни с такими не столкнетесь никогда.

В среднем он работает замечательно. Тем более что у вас тут 4-х (ну или 5-ти мерное пространство в формулировке им. prografix) - тут всего-то O(n^4) или O(n^5) базисных решений - вот вам и верхняя граница на сложность симплекс метода.
  #20  
Старый 06.01.2010, 12:01
Местный

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

Сам я симплекс-метод для решения задач линейного программирования не использую - у меня есть свой метод. И о какой сложности идёт речь - о практической или теоретической? В теории применяются асимптотические оценки, которые могут быть не применимы на практике.
Для поиска пересечения двух выпуклых многогранников опять надо будет решать задачу линейного программирования.
Чтобы избавится от этого можно поступить так: находим все разности векторов первого и второго множества, т.е. все pi - pj ( pi - точка первого множества, pj - точка второго множества ). Множества будут разделяемыми, если точка (0,0,0) не лежит внутри выпуклой оболочки полученных разностей. Строим выпуклую оболочку и смотрим попадает ли в неё точка (0,0,0). Или не строим выпуклую оболочку, а решаем ЗЛП.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разбиение множества. ugo Математические алгоритмы 35 27.09.2010 22:17
Еще одна задача на разбиение множества jungle4ever Математические алгоритмы 7 23.06.2009 17:30
Нахождение множества элементарных циклов графа kilobait Графы 9 17.03.2008 10:02
Покрытие множества кругами Tolran Вычислительная геометрия 3 29.11.2007 01:00
алгоритм нахождения минимального множества сечений контуров обратной связи ikro Графы 0 03.05.2007 11:00