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-мерных параллелепипедов.
Представить параллелепипеды в виде:
Уже неделю ломаю над этой задачей голову. В поисковиках ничего похожего не нашел — возможно, задавал неправильные запросы. Приходилось ли кому-нибудь решать аналогичные задачи в своей практике? Существуют ли алгоритмы и их работоспособные реализации? Возможно, существуют библиотеки, в которых есть средства для решения задачи?
Все, что мне приходит в голову — тупые варианты полного перебора. Но, может быть, есть более изящное и менее тормозное решение?
PS. Ах да, язык предполагаемой реализации — C#. Но сгодится и любой другой.
