Объем трехмерного выпуклого корпуса малой точки устанавливает все на корпус

11

У меня есть вопрос, похожий на тот, который задавался ранее, за исключением 3D, и мне нужен только объем, а не фактическая форма корпуса.

Точнее, мне дан небольшой набор точек (скажем, 10-15) в 3D, все из которых, как известно, лежат на выпуклой оболочке набора точек (поэтому все они «имеют значение» и определяют оболочку). Я только хочу вычислить объем корпуса, меня не волнует вычисление фактического многогранника. Есть ли эффективный алгоритм для этого?

Виктор Лю
источник
Вы знаете, что точки - это вершины многогранника. Вы знаете лица (многоугольники на корпусе)? Если это так, вы можете вычислить объем довольно легко (как сумма «конических» объемов).
hardmath
1
Ленивый способ будет сначала триангулировать, а затем складывать объемы тетраэдров (очень легко вычислить).
Шухао Цао
@hardmath: Нет. Я знаю, что если бы я знал, что фасетные формы это было бы легко.
Виктор Лю
@Shuhao Cao: есть ли простой алгоритм триангуляции для этого особого случая? Обычно алгоритмы трехмерной тетраэдризации довольно сложны, и я ожидаю, что мне придется решать эту проблему тысячи или миллионы раз.
Виктор Лю

Ответы:

5

O(n2)n4n=15vTv4×4

Джозеф О'Рурк
источник
2

N=100[0,1]

N = 100;
p=rand(N,3);
tic;
T = delaunayTri(p(:,1),p(:,2),p(:,3));
t = T.Triangulation;
e1 = p(t(:,2),:)-p(t(:,1),:);
e2 = p(t(:,3),:)-p(t(:,1),:);
e3 = p(t(:,4),:)-p(t(:,1),:);
V = abs(dot(cross(e1,e2,2),e3,2))/6;
Vol = sum(V);
time_elapse = toc;

Результат:

time_elapse =
              0.014807
Vol =
      0.67880219135839

106

convhull

4×4N=105

time_elapse =
              3.244278
Vol =
     0.998068316875714

7×1051[0,1]3

Шухао Цао
источник
Кстати, тест проводится на моем старом Core 2 T61p 2007 года.
Шухао Цао
2

Из FAQ по многогранным вычислениям Комеи Фукуда :

Rd

Известно, что вычисление объема V-многогранника (или H-многогранника) является # P-сложным, см. [DF88] и [Kha93]. Существуют теоретически эффективные рандомизированные алгоритмы для аппроксимации объема выпуклого тела [LS93], но, кажется, никакой реализации не существует. Существует сравнительное исследование [BEF00] различных алгоритмов вычисления объема для выпуклых многогранников. Это указывает на то, что не существует единого алгоритма, который бы хорошо работал для многих различных типов многогранников.

[DF88] ME Дайер и AM Frieze. Сложность вычисления объема многогранника. SIAM J. Comput. 17: 967-974, 1988.

[Ха93] Л.Г. Хачиян. Сложность вычисления объема многогранника. В J. Pach, редактор, Новые Тенденции в Дискретной и Вычислительной Геометрии , страницы 91-101. Springer Verlag, Берлин, 1993.

[LS93] Л. Ловаш и М. Симоновиц. Случайные блуждания в выпуклом теле и улучшенный алгоритм объема. Случайные структуры и алгоритмы , 4: 359-412, 1993.

[BEF00] Б. Бюлер, А. Энге и К. Фукуда. Вычисление точного объема для выпуклых многогранников: практическое исследование. В G. Kalai и GM Ziegler, редакторы, Polytopes - Combinatorics and Computing , DMV-Seminar 29, pages 131-154. Бирхаузер, 2000.

Может показаться, что это скрывает специфику трехмерной проблемы среди трудностей более высоких измерений, несмотря на название статьи Дайера и Фриза. Из их аннотации: «Мы показываем, что вычисление объема многогранника, заданного либо в виде списка фасетов, либо в виде списка вершин, так же сложно, как вычисление перманента матрицы».

PPNvvPPPP={xR3:Axb}

P

hardmath
источник