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...
Problem z tradycyjną galerią sztuki tworzy region i strażników z pewnym pojęciem widoczności i prosi o minimalną liczbę strażników, którzy muszą być umieszczeni, aby zobaczyć cały region. Czy ktoś kiedykolwiek oglądał warianty galerii sztuki, w których obszar widoczności jest definiowany przez...
Johnson-Lindenstrauss lemat mówi przybliżeniu że każdy zbiór z n punktów R d , istnieje mapę F : R d → R k , gdzie k = O ( log n / ε 2 ) tak, że dla wszystkich x , y ∈ S : ( 1 - ϵ ) | | f ( x ) - f ( y ) | | 2)S.S.SnnnRreRre\mathbb{R}^dfa: Rre→ Rkfa:Rre→Rkf:\mathbb{R}^d \rightarrow \mathbb{R}^kk =...
Według książki Topological Graph Theory autorstwa Grossa i Tuckera, biorąc pod uwagę komórkowe osadzenie wykresu na powierzchni (przez „powierzchnię” rozumiem tutaj kulę z pewnymi uchwytami , a poniżej odnosi się do kuli o dokładnie uchwyty), można zdefiniować podwójny multigraf, traktując twarze...
Biorąc pod uwagę dwa podzbiory hipersześcianu wymiarowego (tj. ), szukam algorytmu, który pobiera punkty Hammer odległość (lub odległość na hipersześcianie) jest minimalna. Naiwny algorytm sprawdzający tylko każdą parę potrzebuje czas, czy jest jakiś lepszy znany wynik?M , N ⊆ { 0 , 1 } d m ∈ M , n...
Próbuję pokryć prosty wklęsły wielokąt minimalnymi prostokątami. Moje prostokąty mogą mieć dowolną długość, ale mają maksymalną szerokość, a wielokąt nigdy nie będzie miał ostrego kąta. Pomyślałem o próbie rozłożenia mojego wklęsłego wielokąta na trójkąty, które wytwarzają zestaw minimalnie...
Biorąc pod uwagę zestaw hiperpłaszczyzn określonych przez wektory normalne , wszystkie typy komórek (lub wektory znakowe) to wszystkie wektory t ∈ { + , - } m, dla których istnieje wektor tak, że i dla wszystkich . W tym przypadku oznacza wewnętrzny produkt, a oznacza znak (...
Czy były prace nad odzyskaniem nachylenia segmentu linii po digitalizacji? Oczywiście nie można tego zrobić z idealną dokładnością; to, czego się chce, to metoda wyprowadzenia z linii cyfrowej przedziału możliwych nachyleń. (Pojęcie cyfrowej linii, której używam, to Rosenfelda: zbiór par gdzie...
Rozważmy dwie przestrzenie metrycznych i ( Y , F ) i z obszaru wstawiania ľ : X → Y . Tradycyjne osadzanie przestrzeni metrycznej mierzy jakość μ jako najgorszy stosunek pierwotnej odległości do odległości końcowej: ρ = max p , q ∈ X { d ( x , y )( X, d)(X,d)(X, d)( Y, f)(Y,f)(Y, f)μ : X→...
Studenci, których nadzoruję, otrzymali następujące ćwiczenie: Biorąc pod uwagę punktów na płaszczyźnie, opracuj algorytm, który znajdzie parę punktów, których odległość jest minimalna wśród wszystkich par punktów. Algorytm powinien działać w czasie .o ( N 2 )nnno(n2)o(n2)o(n^2) Istnieje...
Dane wejściowe: zbiór punktów w R 3 i liczba całkowita k ≤ n .nnnR3R3\mathbb{R}^3k≤nk≤nk \le n Dane wyjściowe: Najmniejsza obwiednia wyrównana do osi, która zawiera co najmniej tych n punktów.kkknnn Zastanawiam się, czy znane są algorytmy tego problemu. Najlepsze, co mogłem wymyślić, to czas ,...
W SODA 1995 Jeff Erickson wykazały niższe granice liniowego spełnialności (sprawdzenie, czy niektóre -subset z n liczb rzeczywistych spełnia równanie liniowe o r zmiennych). Metoda dowodowa wykorzystuje nieskończenie małe i zasadę transferu Tarskiego .rrrnnnrrr Czy ktoś mógłby wyjaśnić intuicję,...
Biorąc pod uwagę zbiór punktów w d wymiarowej przestrzeni euklidesowej, problemem jest ustalenie, czy wypukłe kadłuba zawiera piłka jednostki skupione na pochodzenie.nnnrered Czy to problem w NP? Jest w ko-NP, ponieważ można dać punkt w kuli poza wypukłym kadłubem jako świadek i zweryfikować...
Jaki jest obecnie najlepszy sposób wykonywania zapytań zliczających zakres półprzestrzeni na zbiorze punktów wymiarowych, wyrażony w formie kompromisu czas / przestrzeń. Zgodnie z przełomowym referatem Matouseka z 1993 r. (Twierdzenie 6.2, Wyszukiwanie zasięgu za pomocą wydajnych wycinków...
Niech będzie wykresem z (dodatnio) ważonymi krawędziami. I chcemy określić schemat Voronoi dla zestawu węzłów / miejsca , do wiązania się z węzła subgraph w indukowanej przez wszystkie węzły ściśle bliżej niż jakiegokolwiek innego węzła , pomiar długości ścieżki za pomocą sumy wag na łukach. jest...
Niech będzie zbiorem punktów w . Dla każdego , A -spanner jest nieukierunkowane wykres odważony w euklidesowej mierze tak, że na jednym z dwóch punktów , najkrótsza odległość w , jest co najwyżej razy odległość euklidesową między i ,(zwróć uwagę, że definicję tę można łatwo rozszerzyć na dowolne...
Załóżmy, że mam prosty wielokąt i liczbę całkowitą k . Jakie są istniejące podejścia do znalezienia najmniejszego promienia r takie, że mogę pokryć S z k okręgi o promieniu R ? A może r zostanie naprawiony i chcę zminimalizować k
Biorąc pod uwagę zestaw punktów w trójwymiarowej przestrzeni kartezjańskiej, szukam algorytmu, który posortuje te punkty, tak aby zminimalizować minimalną odległość euklidesową między dwoma kolejnymi punktami. Byłoby również korzystne, gdyby algorytm miał tendencję do wyższej średniej odległości...
Twierdzenie o strefie mówi, że jeśli dźgniemy układ n linii inną linią, całkowita złożoność jego strefy , zbiór wszystkich ścian 0, 1 i 2 sąsiadujących z nią, wynosi O (n). Rzeczywista stała to mniej więcej 6n, jak podano w różnych podręcznikach, a dowodem jest indukcja z rozsądnie ostrożnym...
Sumę Minkowskiego dwóch zbiorów wektorów podajeA , B ∈ RreA,B∈RdA, B \in R^d A ⊕ B = { a + b ∣ a ∈ A , b ∈ B }A⊕B={a+b∣a∈A,b∈B} A \oplus B = \{ a + b \mid a \in A, b \in B \} Właśnie usłyszałem interesujący problem (przypisany Danowi Halperinowi): Czy mając kształt , istnieje taki kształt , że ?A...