Rozdzielenie wstępnie przetworzonego wielościanu i płaszczyzny

Mam poważne problemy ze zrozumieniem jednego kroku w pracy Dobkina i Kirkpatricka o rozdzieleniu wielościanów. Próbuję zrozumieć tę wersję: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

Twierdzi się, że gdy znamy najlepsze oddzielenie $P_{i}$ i $S$ , realizowanego przez $r_i$ i $s_i$ , można znaleźć oddzielenie $P_{i-1}$ i $S$ w $O(1)$ schodów. Odbywa się to w następujący sposób. Bierzemy płaszczyznę równoległą do $S$ przez $r_i$ przecinamy nią $P_{i-1}$ na dwie części. Z jednej strony najbliższym punktem $S$ jest $r_i$ a z drugiej mamy `` elementarny '' wielościan, który możemy sprawdzić w czasie . Mój problem polega na tym - jak znaleźć ten elementarny wielościan? Należy pamiętać, że stopień w może być nieograniczona. $O(1)$ $r_i$ $P_{i-1}$

W pliku pdf, aby udowodnić Thm 5.1 ze strony 9, używają Thm 3.1 ze strony 4, co utrudnia śledzenie całej sprawy.

ds.algorithms cg.comp-geom domotorp
źródło

Naprawdę zastanawiam się, czy jeśli zaoferuję nagrodę, w opisie której mówię, że odpowiedź Jeffa nie jest dla mnie jasna, a w komentarzu do jego odpowiedzi określam mój problem z nią, to dlaczego ludzie wciąż go głosują, nie odpowiadając na moje pytanie? Zastanawiam się też, czy jego odpowiedź automatycznie otrzyma nagrodę?

domotorp,

entuzjazm wskazuje, że odpowiedź ma coś wartościowego, co zrobiła! po prostu nie dokładnie to, czego chciałeś. rzeczywiście potrzebna odpowiedź wydawała się udoskonaleniem ogólnej sugestii. Ponadto, po co martwić się opiniami innych osób?

Suresh Venkat,

Odpowiedzi:

Odpowiedz zaktualizowane i przepisane od nowa.

Dostaniesz Polytope . Uruchom Dobkin-Kirkpatric hierarchię na P. To daje sekwencję polytops . Załóżmy, że chcesz znaleźć punkt najbliższy punkt kwerendy . Podstawowy algorytm zaczyna się od obliczenia najbliższego punktu do na , a następnie uwzględnia wszystkie nowe regiony (namioty) przylegające do , znajduje najbliższy punkt do $P$ $P_1 \subseteq P_2 \subseteq \ldots \subseteq P_k = P$ $P$ $q$ $c_1$ $q$ $P_1$ $c_1$ $c_2$ $q$ w tych nowych regionów, a dalej w ten sposób, aż docieramy . $P_k$

Teraz, jeśli jest na krawędzi, nie ma problemu - tylko dwa namioty mogą dotykać tej krawędzi lub tylko jeden z nich może zakrywać krawędź. W związku z tym aktualizacja z w tym przypadku zajmuje stały czas. $c_i$ $c_{i+1}$ $C_i$

Problem pojawia się wtedy, gdy leży na wierzchołku wysokiego stopnia, ponieważ wtedy liczba nowych namiotów przylegających do niego przy przejściu do może być duża. Aby temu zaradzić, będziemy symulować wierzchołek dużego stopnia jako zbiór wierzchołków o niskim stopniu. W szczególności na każdym etapie, jeżeli leży na wierzchołku , będziemy pamiętać dwie kolejne krawędzie przylegające do , tak że najbliższy punkt do $c_i$ $P_{i+1}$ $c_i$ $v$ $e_i, e_i'$ $v$ w $q$ $P_{i+1}$ leży na namiocie, który jest przyległy lub zakrywa jedną z tych dwóch krawędzi. W związku z tym możemy wykonać wymagane obliczenia w stałym czasie.

Pozostaje nam więc problem śledzenia tych dwóch krawędzi podczas wspinania się.

W tym celu wcześniej obliczyć dla każdego wierzchołka o kierunek stycznej . Niech będzie wypukłym wielokątem, który jest figurą wierzchołka dla wielokąta (z płaszczyzną definiującą figurę wierzchołka ma normalną w kierunku ). Koncepcyjnie, $v$ $P$ $t_v$ $Q_i(v)$ $v$ $P_i$ $t_v$ $Q_1(v), Q_2(v), ..., Q_k(v)$ zachowuje się jak hierarchia 2d DK. Jeśli najbliższy punkt na do spoczywa na wierzchołku następnie odpowiada a sąsiednią krawędzią w , gdzie krawędź przecina płaszczyznę rysunku na wierzchołek . Jeśli najbliższy punkt na do leży na krawędzi , pamiętasz, że dwie sąsiednie krawędzie $Q_i(v)$ $q$ $w$ $v$ $e$ $P_i$ $e$ $w$ $Q_i(v)$ $q$ $e'$ $P_i$ , które określają dwa wierzchołki (tutaj $e'$ należy do ). $e'$ $Q_i(v)$

A teraz skończymy ... Rzeczywiście, jeśli jest również na możemy go aktualizować w stałym czasie (ponieważ jest to tylko hierarchia 2d DK). Jeśli z drugiej strony nie jest już na to musi należeć do nowego namiotu, który sąsiaduje lub obejmuje poprzedni punkt . W obu przypadkach możemy go aktualizować w stałym czasie. $c_{i+1}$ $Q_{i+1}(v)$ $c_{i+1}$ $Q_{i+1}(v)$ $c_{i}$

Sariel Har-Peled
źródło

Zaktualizowana odpowiedź. Sprawdź, czy ma to teraz sens. Tak myślę o tej strukturze danych. Może nie mieć związku z tym, co jest w gazecie.

Sariel Har-Peled,

Rozumiem teraz, dziękuję! Sztuka polega na tym, że wybieramy styczne kierunki na początku i utrzymujemy je bez zmian przez cały czas! Usunąłem moje poprzednie komentarze, które były związane z twoją starą odpowiedzią. Jeszcze raz dziękuję!

domotorp

Tak. Chętnie pomoże!

Sariel Har-Peled,

Twierdzenie 3.1 wymaga, aby hierarchiczna reprezentacja była zwarta . Jednym z wymagań dla zwięzłości, że stopień w jest ograniczona przez stałą. Zobacz dół strony 3. $P$ $r_i$ $P_{i-1}$

Definicja i konstrukcja hierarchii Dobkina-Kirkpatricka jest o wiele bardziej wyraźna we wcześniejszych artykułach (odniesienia [9,10,11] w czytanym dokumencie). Zdecydowanie polecam je najpierw przeczytać.

Jeffε
źródło

P_{i - 1} ∖ P_{i}

$P_{i-1}\setminus P_i$

r_{i}

$r_i$

With one of the other vertices, which all have degree 4. (In fact, with an independent subset of the degree-4 vertices.) The point

r_{i}

$r_i$ is a vertex of

P_{i - 1}

$P_{i-1}$ but not a vertex of

P_{i}

$P_i$ .

Jeffε

So there is the misunderstanding. I think that

r_{i}

$r_i$ is a vertex of

P_{i}

$P_i$ as well in the algorithm that I have described, notably the one closest to

S

$S$ . Am I wrong?

domotorp

Wydaje się, że jest to jedno z tych standardowych, ale żmudnych ogólnych założeń. Jeśli nie zależy Ci na czasie działania, zawsze możesz zamienić wierzchołek stopnia

d

$d$ by two extremely close vertices of degree

d / 2 + 3

$d/2 + 3$ (if you insist on triangular faces). Repeat this till all the vertices till all the degrees are smaller than 10.

Sariel Har-Peled

@Sariel: I was thinking the same but then why would the process end? Notice that when we delete a vertex, then its neighbors might not form a face, so we might have to add new edges, in fact, we might have to increase the degree of a vertex.

domotorp

In case somebody would still be interested by the question: the snag in the Dobkin Kirpatrick explanation has also been pointed out in Barba and Langerman's Optimal detection of intersections between convex polyhedra.

They observe in the paper (SODA 2015 version, not arxiv) that O'Rourke's Computational Geometry in C, chap 7 already details a workaround (which is essentially Sariel's answer). The SODA paper also introduces an alternative solution; defining a variant of the DK hierarchy in which each vertex has bounded degree.

Joseph Stack
źródło