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
Znajdź największą kostkę zawartą w unii prostopadłościanów
Mam dużo prostopadłościanów w przestrzeni 3D, każda ma punkt początkowy na (x, y, z) i ma rozmiar (Lx, Ly, Lz). Zastanawiam się, jak znaleźć największą kostkę w tej przestrzeni 3D, która jest zawarta w unii prostopadłościanów. Czy istnieje na to wydajny algorytm? Na przykład, jeśli mam następujące prostopadłościany: prostopadłościan zaczynający …
1
Poczwórna struktura danych (Delaunay / Voronoi)
2 pytania do geometrii obliczeniowej lub algebraistów: Właśnie zaczynam nurkować w geometrii obliczeniowej i uwielbiam ją =) Próbuję przeczytać słynny artykuł Guibasa i Stolfiego zatytułowany „Prymitywy do manipulowania ogólnymi poddziałami i obliczaniem diagramów Voronoi” w celu zaimplementowania algorytmu triangulacji Delaunaya. Kusi mnie, aby pominąć wszystkie teoretyczne rzeczy i po prostu …
1
Jak nie obliczyć najmniejszego okręgu zawierającego skończony zestaw kół
Załóżmy, że mamy skończony zbiór LLL dysków w R2R2\mathbb{R}^2 , i chcemy obliczyć najmniejszą dysku DDD , dla którego ⋃L⊆D⋃L⊆D\bigcup L\subseteq D . Standardowy sposób ten jest użycie algorytmu Matousek, Sharir i Welzl [1], aby znaleźć podstawę BBB z LLL i pozwolić D=⟨B⟩D=⟨B⟩D=\langle B\rangle najmniejsza dysku zawierającej ⋃B⋃B\bigcup B . …
2
Sortowanie według odległości euklidesowej
jest zbiorem punktów na płaszczyźnie. Losowy punkt x ∉ S jest podany na tej samej płaszczyźnie. Zadanie to rozwiązać wszystkie y ∈ S przez euklidesową odległość pomiędzy x i y .SS.Sx∉Sx∉S.x \notin Sy∈Sy∈S.y \in Sxxxyyy Podejście no-mózg jest obliczenie odległości między i Y dla wszystkich y ∈ S , a …
3
Czy istnieje algorytm aproksymacji stałego współczynnika dla problemu kolorowania prostokąta 2D?
Problem, który rozważamy tutaj, to rozszerzenie znanego problemu kolorowania interwałów. Zamiast przedziałów uważamy prostokąty o bokach równoległych do osi. Celem jest pokolorowanie prostokątów przy użyciu minimalnej liczby kolorów, tak aby każdemu z dwóch nachodzących na siebie prostokątów przypisano różne kolory. Ten problem jest znany jako trudny dla NP. Xin Han, …
2
Znalezienie największego zestawu punktów o ograniczonej średnicy
Biorąc pod uwagę punkty w i odległość znajduję największy podzbiór tych punktów, tak że odległość euklidesowa nie jest większa niż .p1, … , Snp1,…,pnp_1,\ldots,p_nRreRre\mathbb{R}^{d}llllll Jaka jest złożoność tego problemu? Na wykresie nad punktami, które mają krawędź, ilekroć odległość dwóch punktów wynosi co najwyżej , problem jest równoznaczny ze znalezieniem maksymalnej …
1
Rysujesz wykresy z kilkoma „ostrymi” wierzchołkami?
W przypadku płaskiego osadzenia wykresu płaskiego na płaszczyźnie o prostych krawędziach, zdefiniuj wierzchołek jako ostry wierzchołek, jeśli maksymalny kąt między dwiema kolejnymi krawędziami wokół niego jest większy niż 180. Innymi słowy, jeśli istnieje linia przechodząca przez ten wierzchołek wierzchołek w osadzeniu, tak że wszystkie krawędzie padające na ten wierzchołek leżą …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
1
Czy dolna granica dowodu w tym dokumencie jest poprawna?
W tym artykule Erika D. Demaine'a, Sandora P. Fekete, Roberta J. Langa na stronie 15, ryc. 13, „Opakowanie w koło do projektowania origami jest trudne”, twierdzą, że długość boku najmniejszego kwadratu obejmującego dwa koła każdy z obszaru 1/2 wynosi 1,471299. Z moich obliczeń wynika, że ​​długość boku wynosi 1,362 i …
1
Obliczanie elipsoidy wielościanu Löwnera-Johna
Elipsoida Löwnera-Johna z wypukłego zestawu jest elipsoidą o minimalnej objętości (MVE), która ją otacza. Elipsoidę można obliczyć metodą Khachiyana i istnieje wiele przybliżeń, jeśli C jest (wypukłym kadłubem) zbiorem punktów.dodoCdodoC Czy istnieją szybkie (tj. Oparte na metodzie nieelipsoidalnej) aproksymacje MVE ograniczonego wielościanu przedstawione tylko w odniesieniu do półpłaszczyzn, których przecięcia …
3
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 PiPiP_{i} i SSS , realizowanego przez ririr_i i sisis_i , można znaleźć oddzielenie Pi−1Pi−1P_{i-1} i SSS w O(1)O(1)O(1) schodów. Odbywa się to w …
2
Liczba triangulacji zbioru
Po tym, jak tego lata Emo Welzl przemawia na ten temat, wiem, że liczba triangulacji zbioru punktów na płaszczyźnie wynosi między około Ω ( 8,48 n ) a O ( 30 n ) . Przepraszam, jeśli jestem nieaktualny; aktualizacje mile widziane.nnnΩ ( 8,48n)Ω(8.48n)\Omega(8.48^n)O ( 30n)O(30n)O(30^n) Wspomniałem o tym na zajęciach …
6
Graf płaski na przecięciu grubych rzeczy?
Istnieje piękne twierdzenie Koebe'a (patrz tutaj ), które stwierdza, że ​​każdy płaski wykres można narysować jako wykres całowania dysków (bardzo romantyczny ...). (Mówiąc nieco inaczej, każdy wykres płaski można narysować jako wykres przecięcia dysków.) Twierdzenie Koebe'a nie jest łatwe do udowodnienia. Moje pytanie: czy istnieje łatwiejsza wersja tego twierdzenia, w …
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.