Соседние грани многогранника в n-мерном пространстве (алгори

[igrishin]

Уважаемые форумчане,
столкнулся с такой несложной задачей (на первый взгляд), однако ничего толкового не идет в голову.
В n-мерном пространстве многогранник задан системой линейных неравенств. Берем одну из граней этого многогранника (неравенство, ее задающее, известно). Требуется определить соседние грани (неравенства, их задающие).
Буду благодарен, если кто-нибудь натолкнет на мысль.

[Dandan]

Для начала неплохо бы понять, что такое соседние грани многогранника в n-мерном пространстве
Если $a_i\geqslant0$ это данные неравенства, то, как я понимаю, грани m и k будут соседними, если $ (a_m=0) \bigwedge (a_k=0) \bigwedge (a_i\geqslant0 , \forall i) \neq \emptyset $

[незваный гость]

Я полагаю, что здесь идет о неравенствах вида $\sum_j a_{i, j} x_j \leqslant b_i$.

igrishin,
Я правильно понимаю, что Вы имеете в виду, что известно неравенство, задающее плоскость грани (грань, т.е. конкретный многоугольник, задается совокупностью неравенств)?

Если известна именно грань, то найти соседей легче легкого (ну, если затраты не в счет): надо найти все неравенства, для которых выполняется строгое равенство в одной из вершин грани (есть, конечно, ньюансы с бесконечно-удаленными вершинами, но мы их пока опустим…).

[igrishin]

Если известна именно грань, то найти соседей легче легкого (ну, если затраты не в счет):

В том-то и дело, что вычислительные затраты очень важны. Вы предлагаете осуществить полный перебор, а n может быть равно 100 или 1000.
Может кто-нибудь знает более хитрый способ.

[Руст]

Dandan писал(а):

Для начала неплохо бы понять, что такое соседние грани многогранника в n-мерном пространстве
Если $a_i\geqslant0$ это данные неравенства, то, как я понимаю, грани m и k будут соседними, если $ (a_m=0) \bigwedge (a_k=0) \bigwedge (a_i\geqslant0 , \forall i) \neq \emptyset $

Это может дать не соседнюю грань (например пересечение только по вершине). Для соседней грани размерность пересечения n-2 (грани имеют размерность n-1).

[незваный гость]

igrishin писал(а):

В том-то и дело, что вычислительные затраты очень важны. Вы предлагаете осуществить полный перебор, а n может быть равно 100 или 1000.

Интересное кино. Полный перебор делается за линейное время. Куда уж лучше? Любое из $n$ неравенств может задавать плоскость соседней грани.

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

Приведу бесполезный пример такой структуры. Мы строим граф вершин многогранника, и для каждого ребра храним список неравенств, его задающих. Плюс для каждого неравенства — список лежащих на его плоскости ребер.

Теперь все понятно: Ваша задача решается быстро. Правда, за какое время строятся эти предварительные данные — вопрос отдельный. Но его можно решать заметно эффективнее, чем проходя по списку неравенств и ища каждый раз смежные грани.

[igrishin]

незваный гость писал(а):

Теперь все понятно: Ваша задача решается быстро. Правда, за какое время строятся эти предварительные данные — вопрос отдельный. Но его можно решать заметно эффективнее, чем проходя по списку неравенств и ища каждый раз смежные грани.

Как раз и хотелось бы увидеть, что означает "эффективнее". В процессе решения задачи приходится многократно решать задачу определения смежных граней. Можно конечно составить матрицу смежности, однако это экспоненциальная задача, а не линейная. Да и в процессе решения приходится проецировать многогранник в пространство n-1 размерности. А после этого снова необходим расчет матрицы смежности.

[незваный гость]

Какова сложность построения такой структуры? Зависит от единиц измерения, но, может быть и экспоненциальна (симплекс-метод имеет экспоненциальную в худшем случае сложность, а это значит, что количество ребер растет экспоненциально). Ну и что? Мы же оптимизируем поиск соседних граней, а не построение этой структуры. Структура свыше нам дана, замена счастию она.

Видите ли, Ваш вопрос очень нечетко поставлен. Вы так и не затруднили себя ответом, что у Вас есть — неравенство (плоскость) или грань (многоугольник). Но самое главное, что не понятно — что Вы делаете, какую задачу решаете (даже из какой области — линейное ли программирование, вычислительная ли геометрия), в каком методе пытаетесь разобраться.

[Dandan]

незваный гость писал(а):

:evil:
Видите ли, Ваш вопрос очень нечетко поставлен. Вы так и не затруднили себя ответом, что у Вас есть — неравенство (плоскость) или грань (многоугольник). Но самое главное, что не понятно — что Вы делаете, какую задачу решаете (даже из какой области — линейное ли программирование, вычислительная ли геометрия), в каком методе пытаетесь разобраться.

Вопрос стоит четко. Грань - это когда мы одно из неравенств превращаем в равенство, т.е. множество решений полученной системы неравенств + равенство. Определение соседних граней здесь прозвучало (действительно лучше считать что размерность пересечения должна быть n-2). Че тут непонятного. Для заданной грани перебираем все остальные и проверяем являются ли они соседними. Никакие хитрости, я думаю, этот процесс существенно ускорить не смогут.

[незваный гость]

Dandan писал(а):

Вопрос стоит четко. Грань - это когда мы одно из неравенств превращаем в равенство, т.е. множество решений полученной системы неравенств + равенство. Определение соседних граней здесь прозвучало (действительно лучше считать что размерность пересечения должна быть n-2).

Вашими бы устами, да мёды пить.

Ну, во-первых, прозвучало Ваше определение (многоугольник). А вопрос обращен все-таки к igrishin, поскольку задача его. Ваша трактовка исходных неравенств как-то не совпадает с моей, и igrishin не комментирует и этого.

Во-вторых, нечеткость не в определении грани, а в постановке задачи. Например, грань, несомненно, может быть задана указанием неравенства, превращаемого в равенство (задает ли это превращение грань я оставлю, с Вашего позволения, в стороне. Может задавать). Вопрос — известны ли при этом границы оной грани или нет? Это, знаете ли, зависит от задачи (а точнее, от того, чего ради мы ищем эти соседние грани). Как они заданы? Линейное время решения задачи (так не понравившееся igrishin) — это хорошо или плохо?

В-третьих, а откуда известно, что в решении системы неравенств есть хотя бы одна грань (размерности $n-1$)?!? Ну, да это уже занудство, признаю.

[igrishin]

незваный гость писал(а):

нечеткость не в определении грани, а в постановке задачи. Например, грань, несомненно, может быть задана указанием неравенства, превращаемого в равенство (задает ли это превращение грань я оставлю, с Вашего позволения, в стороне. Может задавать). Вопрос — известны ли при этом границы оной грани или нет? Это, знаете ли, зависит от задачи (а точнее, от того, чего ради мы ищем эти соседние грани). Как они заданы? Линейное время решения задачи (так не понравившееся igrishin) — это хорошо или плохо?

Многогранник задан системой линейных неравенств. Грань, для которой требуется определить смежные, задается равенством, полученным из неравенства. Границы неизвестны, хотя из можно расчитать, но это - время. Линейное время - очень хорошо, но если надо перебрать все грани для построения матрицы смежности, то оно становится отнюдь не линейным.

[незваный гость]

Спасибо. Осталось пара-тройка вопросов:
1) Правильно ли я понимаю тип неравенств?

незваный гость писал(а):

Я полагаю, что здесь идет о неравенствах вида $\sum_j a_{i, j} x_j \leqslant b_i$.

2)

незваный гость писал(а):

Но самое главное, что не понятно — что Вы делаете, какую задачу решаете (даже из какой области — линейное ли программирование, вычислительная ли геометрия), в каком методе пытаетесь разобраться.

3) Вы пишите "многогранник задан". Можно ли сделать вывод, что дано, что область удовлетворяющая неравенствам именно многогранник, то есть (а) ограничена, (б) имеет размерность равную размерности пространства. (В общем случае оба эти условия могут быть не верны.)

[igrishin]

незваный гость писал(а):

:evil:
Спасибо. Осталось пара-тройка вопросов:
1) Правильно ли я понимаю тип неравенств?

незваный гость писал(а):

Я полагаю, что здесь идет о неравенствах вида $\sum_j a_{i, j} x_j \leqslant b_i$.

2)

незваный гость писал(а):

Но самое главное, что не понятно — что Вы делаете, какую задачу решаете (даже из какой области — линейное ли программирование, вычислительная ли геометрия), в каком методе пытаетесь разобраться.

3) Вы пишите "многогранник задан". Можно ли сделать вывод, что дано, что область удовлетворяющая неравенствам именно многогранник, то есть (а) ограничена, (б) имеет размерность равную размерности пространства. (В общем случае оба эти условия могут быть не верны.)

1)Да, именно такие неравенства.
2)Область - линейное программирование.
3) В общем случае об а) и б) утверждать нельзя. Впрочем на практике а) чаще всего выполняется.

[worm2]

Не знаю, поможет ли Вам это:

Часто задаваемые вопросы по линейному программированию.

[igrishin]

Спасибо большое, посмотрю, там много интересного.