Алгоритм нахождения вершин объединения выровненных по оси гиперкубоидов в неотрицательном ортанте, все с одной вершиной в начале координат

Question

Предположим, у меня есть коллекция из N выровненных по оси гиперкубоидов в измерениях D.

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

Вы можете предположить, что я уже удалил из списка гиперкубоидов любые гиперкубоиды, которые строго содержатся внутри другого. (В настоящее время я делаю это с помощью наивного алгоритма O (N ^ 2 * D). Дополнительный вопрос: могу ли я сделать лучше?)

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

В двух измерениях существует N-1 таких вершин, и их можно эффективно найти, отсортировав вершины по одной (произвольной) координате, т. Е. В O (N log (N)).

Сколько таких вершин в D измерениях? (С двумя кубами, кажется, есть только одна новая вершина, так что, возможно, все еще N-1?) Как я могу эффективно найти эти вершины?

Answer 1

Некоторая аббревиатура: Hj означает «Гиперкубоид j» и имеет одну вершину в начале координат, а противоположную в {xi, yi, zi, wi, etc}.

Если Hi содержится внутри Hj, то xi<=xj,yi<=yj, zi<=zj и т. Д.

Если у вас есть D отсортированные списки координат, по одному для каждого измерения, тогда легко проверить, является ли Hi внутренним дляHj простым запросом индексов координат: posXi<posXj и posYi<posYj и posZi<posZj и т. Д. Обратите внимание на условие "и", а не "или".

Если некоторые Hiне соблюдайте правила "и" для всех Hj, тогда вершина i является новой вершиной.
Если какая-то координата T "вне": posTi > posTlast, то вершина i является новой вершиной.