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...
Czy istnieją teraz prostsze algorytmy / dowody do triangulacji płaskiego wielokąta w czasie liniowym? Co jest dobrym źródłem wiedzy na temat najnowszego znanego
Jaka jest złożoność obliczeniowa następującego problemu: dane dwie złożone macierzy i sprawdzają, czy istnieje macierz permutacji taka, że: B P B = P P T .n × nn×nn\times nZAZAAbbBP.P.PB = PA P.T..b=P.ZAP.T..B = P A P^T. Jeśli to pomoże, można założyć, że i są pustelnikami (lub nawet, że i są...
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...
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...
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ść...
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...
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 ,...
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...
Załóżmy, że otrzymujesz zestaw n punktów na płaszczyźnie i chcesz sprawdzić, czy tworzą one wypukły n wielokąt, tj. Czy wszystkie leżą na wypukłym kadłubie. Zastanawiałem się, czy ktoś wie, jak to zrobić w czasie o (nlogn), tj. Bez obliczania
Zetknąłem się z tym problemem w dziedzinie fizyki dość dalekiej od informatyki, ale wydaje się, że jest to pytanie, które było badane w CS, więc pomyślałem, że spróbuję szczęścia, zadając to tutaj. Wyobraź sobie, że otrzymałeś zestaw punktów oraz listę niektórych odległości między punktami d i j ....
Szukam struktury danych, która utrzymywałaby tablicę liczb całkowitych o rozmiarze , i pozwalała na następujące operacje w czasie .tttnnnO(logn)O(logn)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , który zwiększa
Łatwo jest zweryfikować, że biorąc pod uwagę wymiarową siatkę punktów całkowitych , przy regularnym sąsiedztwie można znaleźć separator o rozmiarze (wystarczy wybrać dowolny środkowy hiperpłaszczyzna i usuń wszystkie jego wierzchołki). Nie jest też zbyt trudne (ale zdecydowanie nie natychmiastowe)...
Czy są jakieś problemy, które są NP-całkowite przy stosowaniu geometrii euklidesowej, ale są dobrze zdefiniowane i możliwe do rozwiązania w czasie wielomianowym dla niektórych geometrii
I przypisany Moi studenci problem znalezienia trójkąt spójne z kolekcją punktów w R 2 , oznaczonego ± 1 . (Trójkąt T jest zgodny z próbką oznaczoną, jeśli T zawiera wszystkie punkty dodatnie i żaden z punktów ujemnych; z założenia próbka przyjmuje co najmniej 1 spójny...
dodoC jest prostokątem równoległym do osi. do1, … , Cndo1,…,donC_1,\dots,C_ndo1∪ ⋯ ∪ C.n⊊ C.do1∪⋯∪don⊊doC_1\cup\dots\cup C_n \subsetneq C Prostokąta zachowaniem podziału na jest partycja , tak że The są parami-Wnętrze rozłączne równoległoosiowym prostokąty, a każdy : , tj. każdy istniejący...
Geometria obliczeniowa jest obszarem, który wydaje mi się bardzo interesujący i chciałbym poświęcić około miesiąca lub dwóch na projekt, który zapozna mnie z tym i pomoże mi nauczyć się kluczowych pojęć. Jaki jest dobry sposób podejścia do tego i jakie są kluczowe koncepcje, których powinienem się...
Niech wyraźne punkty 1...n1...n1 ... n siedzieć R2R2\mathbb{R}^2 . Mówimy, że punkty iii i jjj są sąsiadami, jeśli , co oznacza, że każdy punkt jest sąsiadem z punktami o indeksach w obrębie 2 , otaczających.|i−j|<3(modn−2)|i−j|<3(modn−2)|i-j| < 3 \pmod{n-2}222 Problemem jest: Dla...
Co wiadomo na temat następującego problemu? Biorąc pod uwagę zbiór funkcji f : { 0 , 1 } n → { 0 , 1 } , znajdź największą podkolekcję S ⊆ C z zastrzeżeniem ograniczenia, że VC-Wymiar ( S ) ≤ k dla jakiejś liczby całkowitej k .CCCf:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆CS⊆CS...
Jest to pytanie uzupełniające do poprzedniego postu Robina Kothari na temat wyników twardości wielomianowej . Interesuje mnie w szczególności sprawdzenie niektórych dowodów twardości dla problemów, które mają z grubsza dolne granice, i mówię z grubsza, aby pozwolić na nieco subkubiczne ulepszenia,...