Еще одна задачка на комбинаторику

Lokomotiv59

Есть два n-мерных кирпича
K1 = [a_1,b_1]x...x[a_n,b_n]
и
K2 = [c_1,d_1]x...x[c_n,d_n]
1. Когда их можно заменить одним кирпичом ?
2. Пусть наряду с интервалами разрешено брать множества [inf,-a]+[b,+inf]. Как тогда решается задачка?
3. Пусть есть N кирпичей. Как тогда решается задачка ?

griz_a

а) Наверное, если у них (n-1) мерные основания совпадают или если один в другом лежит. Вроде всё.
б) Не вижу разницы

Xephon

а) не совсем верно. рассмотрим длинный кирпич, и его же, сдвинутый на половину своей длины.
у этих двух нет общего основания, но объединение - кирпич

griz_a

Доказательство.
Рассмотрим точки (a_1,a_2,a_3...a_n (b_1,b_2,...,b_n (c_1,c_2...,c_n (d_1,d_2...d_n)
Поменяем направления осей так, чтобы c_i стало не меньше a_i.
Если теперь все b_i>=d_i, то первый кирпич содержит второй.
Пусть b_1<d_1, тогда d_1,b_2,..,b_n в объединении, но не в первом, т.е. во втором, т.е
b_i<=d_i
Аналогично d_1,a_2,...a_n не в первом, значит
c_i=a_i, i=2...n
Теперь берем a_1,d_2,...d_n
Если она опять не в первом, то c_1=a_1
Если в первом, то b_i=d_i, i=2..n
В первом случае у них совпали c_i=d_i и b_i<=d_i, i=1..n, т.е. второй содержит первый
Во втором у них совпадают n-1 координата у крайних точек, а значит совпадает n-1 куб, т.е. основания совпадают

griz_a

Я имел ввиду a_2=c_2,a_3=c_3....a_n=c_n,b_2=d_2,....b_n=d_n, c_1<=b_1<=d_1 (с точностью до замены 1->i или (а->c, b->d

Lokomotiv59

Угу, понятно. А с N кирпичами неподъемная задача ?
Сойдет алгоритм объединения.

griz_a

Для N старые критерии - связность и принадлежность вершин будущего кирпича - уже не подходят. Можно объединить 5 кирпичей в связную фигуру, у которой все вершины содержащего их кирпича будут в объединении, но кирпича не получится.
Как бы два кирпича, сверху один такой же, а сверху еще 2.
Оставить комментарий
Имя или ник:
Комментарий: