Дано:

N-мерное пространство (декартовы координаты), в котором определено M N-мерных прямоугольных параллелепипедов.

Каждый параллелепипед задан значениями N отрезков (ребер параллелепипеда) по каждой оси координат:
X1: [Ax1; Bx1)
X2: [Ax2; Bx2)
X3: [Ax3; Bx4)
...
XN: [AxN; BxN)

Для любого параллелепипеда Аx,i > 0 и Вx,i > 0. А и В принадлежат к пространству непрерывных чисел, но в принципе могут быть дискретизированы с шагом 0.0001.

Значения N, М на этапе разработки неизвестны. На практике значение N — от 1 до 5, значение M — от 1 до 30 000-50 000.

Требуется:

Произвести вычитание из N-мерного параллелепипеда вида
X1: [0; ∞)
X2: [0; ∞)
X3: [0; ∞)
...
XN: [0; ∞)

всех М параллелепипедов, заданных в условии. Разность разбить на минимально возможное число непересекающихся N-мерных параллелепипедов.
Представить параллелепипеды в виде:

X1: [Ax1; Bx1)
X2: [Ax2; Bx2)
X3: [Ax3; Bx4)
...
XN: [AxN; BxN)

Проблема:

Уже неделю ломаю над этой задачей голову. В поисковиках ничего похожего не нашел — возможно, задавал неправильные запросы. Приходилось ли кому-нибудь решать аналогичные задачи в своей практике? Существуют ли алгоритмы и их работоспособные реализации? Возможно, существуют библиотеки, в которых есть средства для решения задачи?

Все, что мне приходит в голову — тупые варианты полного перебора. Но, может быть, есть более изящное и менее тормозное решение?

PS. Ах да, язык предполагаемой реализации — C#. Но сгодится и любой другой.

R>Произвести вычитание из N-мерного параллелепипеда вида
R>всех М параллелепипедов, заданных в условии. Разность разбить на минимально возможное число непересекающихся N-мерных параллелепипедов.
R>Все, что мне приходит в голову — тупые варианты полного перебора. Но, может быть, есть более изящное и менее тормозное решение?

задача родственна нахождению минимальных днф/кнф

Здравствуйте, Radomir, Вы писали:

R>Дано:

R>N-мерное пространство (декартовы координаты), в котором определено M N-мерных прямоугольных параллелепипедов.

R>Каждый параллелепипед задан значениями N отрезков (ребер параллелепипеда) по каждой оси координат:
R>X1: [Ax1; Bx1)
R>X2: [Ax2; Bx2)
R>X3: [Ax3; Bx4)
R>...
R>XN: [AxN; BxN)

R>Для любого параллелепипеда Аx,i > 0 и Вx,i > 0. А и В принадлежат к пространству непрерывных чисел, но в принципе могут быть дискретизированы с шагом 0.0001.

R>Значения N, М на этапе разработки неизвестны. На практике значение N — от 1 до 5, значение M — от 1 до 30 000-50 000.

R>Требуется:

R>Произвести вычитание из N-мерного параллелепипеда вида
R>X1: [0; ∞)
R>X2: [0; ∞)
R>X3: [0; ∞)
R>...
R>XN: [0; ∞)

R>всех М параллелепипедов, заданных в условии. Разность разбить на минимально возможное число непересекающихся N-мерных параллелепипедов.
R>Представить параллелепипеды в виде:

R>X1: [Ax1; Bx1)
R>X2: [Ax2; Bx2)
R>X3: [Ax3; Bx4)
R>...
R>XN: [AxN; BxN)

R>Проблема:

R>Уже неделю ломаю над этой задачей голову. В поисковиках ничего похожего не нашел — возможно, задавал неправильные запросы. Приходилось ли кому-нибудь решать аналогичные задачи в своей практике? Существуют ли алгоритмы и их работоспособные реализации? Возможно, существуют библиотеки, в которых есть средства для решения задачи?

R>Все, что мне приходит в голову — тупые варианты полного перебора. Но, может быть, есть более изящное и менее тормозное решение?

R>PS. Ах да, язык предполагаемой реализации — C#. Но сгодится и любой другой.

Вычислительная геометрия