Pytania otagowane jako cg.comp-geom

Geometria obliczeniowa to badanie problemów geometrycznych z perspektywy obliczeniowej. Przykłady problemów obejmują: obliczanie obiektów geometrycznych, takich jak wypukłe kadłuby, redukcja wymiarowości, problemy z najkrótszą ścieżką w przestrzeniach metrycznych lub znalezienie małego podzbioru punktów, który aproksymuje pewną miarę całego zestawu (tj. Zestawu podstawowego).

2
Problem z Super Mario Galaxy
Załóżmy, że Mario chodzi po powierzchni planety. Jeśli zacznie chodzić ze znanego miejsca, w ustalonym kierunku, na określoną odległość, jak szybko możemy ustalić, gdzie się zatrzyma? Bardziej formalnie, załóżmy, że otrzymujemy wypukły politop w 3-przestrzeni, punkt początkowy na powierzchni , wektor kierunku (w płaszczyźnie pewnej ścianki zawierającej ) i odległość …
3
Jakie są powody, dla których badacze geometrii obliczeniowej preferują model BSS / real-RAM?
tło Obliczenia na liczbach rzeczywistych są bardziej skomplikowane niż obliczenia na liczbach naturalnych, ponieważ liczby rzeczywiste są obiektami nieskończonymi i istnieje niezliczona liczba liczb rzeczywistych, dlatego liczb rzeczywistych nie można wiernie przedstawić za pomocą ciągów skończonych nad skończonym alfabetem. W przeciwieństwie do klasycznego obliczania ciągów skończonych, w którym różne modele …
3
Sparametryzowana złożoność zestawu uderzeń w skończonym wymiarze VC
Interesuje mnie sparametryzowana złożoność problemu, który nazywam d-Dimensional Hitting Set: biorąc pod uwagę przestrzeń zakresu (tj. Układ zestawu / hipergraph) S = (X, R) mający wymiar VC co najwyżej d dodatnia liczba całkowita k, czy X zawiera podzbiór wielkości k, który uderza w każdy zakres w R? Sparametryzowana wersja problemu …
17
Przykłady, w których wgląd w geometrię był przydatny do rozwiązania czegoś całkowicie niegeometrycznego
Jedną z miłych rzeczy w ewolucji we wszechświecie o trzech wymiarach przestrzennych jest to, że rozwinęliśmy umiejętności rozwiązywania problemów dotyczące obiektów w przestrzeni. Tak więc na przykład możemy myśleć o tryplecie liczb jako o punkcie 3-d, a zatem obliczenia o tripletach liczb jako o obliczeniach o punktach w 3-d, które …
1
Izometryczne osadzanie L2 w L1
Wiadomo, że biorąc pod uwagę podzbiór (to znaczy, biorąc pod uwagę punktów w z odległością euklidesową), możliwe jest osadzenie ich izometrycznie w \ ell ^ {n \ wybierz 2 } _1 .nnnℓd2ℓ2d\ell_2^dnnnRdRd{\mathbb R}^dℓ(n2)1ℓ1(n2)\ell^{n\choose 2}_1 Czy izometria jest obliczalna w (ewentualnie losowym) czasie wielomianowym? Ponieważ istnieją problemy z precyzją skończoną, dokładne …
3
Wypukły korpus z minimalną oczekiwaną normą l2
Rozważmy wypukłe ciało wyśrodkowane na początku i symetryczne (tj. Jeśli to ). Chcę znaleźć inne ciało wypukłe tak aby i następująca miara zostały zminimalizowane:x ∈ K - x ∈ K L K ⊆ L.KKKx∈Kx∈Kx\in K−x∈K−x∈K-x\in KLLLK⊆LK⊆LK\subseteq L xf(L)=E(xT⋅x−−−−−√)f(L)=E(xT⋅x)f(L)=\mathbb{E}(\sqrt{x^T \cdot x}) , gdzie jest punktem losowo wybranym losowo z L.xxx Nic …
1
Próbkowanie w przybliżeniu z wypukłych wielościanów za pomocą komputerów kwantowych
Komputery kwantowe są bardzo dobre do dystrybucji próbkowania, których nie wiemy jak próbkować przy użyciu klasycznych komputerów. Na przykład, jeśli f jest funkcją logiczną (od do ), którą można obliczyć w czasie wielomianowym, to za pomocą komputerów kwantowych możemy skutecznie próbkować zgodnie z rozkładem opisanym przez Rozwinięcie Fouriera f. (Nie …
5
Pakowanie prostokątów w wypukłe wielokąty, ale bez rotacji
Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i zapytano, ile identycznych kopii prostokąta można upakować w wielokącie. Uważam, …
2
Wykrywanie dwóch rodzajów prawie prostych wielokątów
Interesuje mnie złożoność decydowania, czy dany nie-prosty wielokąt jest prawie prosty, w jednym z dwóch różnych formalnych zmysłów: słabo prostym lub nie-samokreślącym . Ponieważ te terminy nie są powszechnie znane, zacznę od niektórych definicji. Wieloboku jest zamknięty cykl odcinków łączenia kilku skończoną sekwencję punkty na płaszczyźnie. Punkty nazywane są wierzchołkami …
1
Złożoność obliczania najkrótszych ścieżek w płaszczyźnie z wielokątnymi przeszkodami
Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że współrzędne s i t oraz współrzędne każdego wierzchołka …
1
Maksymalny zestaw rozłączny: jaki jest faktyczny współczynnik przybliżenia chciwego algorytmu?
Rozważ problem znalezienia maksymalnego zestawu rozłącznego - maksymalnego zestawu nie nakładających się kształtów geometrycznych z danej kolekcji kandydatów. Jest to problem NP-zupełny, ale w wielu przypadkach następujący chciwy algorytm daje przybliżenie o stałym współczynniku: Dla każdego kandydującego kształtu x oblicz jego rozłączny numer przecięcia DIN(x)DIN(x)DIN(x) = największa liczba rozłącznych kształtów …
2
Struktura danych dla zapytań o minimalną liczbę kropek
RnRn\mathbb{R}^n⟨⋅,⋅⟩⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmmv1,v2,…,vmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx∈Rnx \in \mathbb{R}^nmini⟨x,vi⟩mini⟨x,vi⟩\min_i \langle x, v_i \rangleO(nm)O(nm)O(nm)n=2n=2n = 2O(log2m)O(log2⁡m)O(\log^2 m) Jedyne, co mogę wymyślić, to: Bezpośrednią konsekwencją lematu Johnsona-Lindenstraussa jest to, że dla każdego i rozkładu na występuje liniowe mapowanie (które można ocenić w czasie ) tak, że . Tak więc w czasie O …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.