Teoretyczne informatyka cg.comp-geom

2

Konsekwencje dolnych granic dla -net na przybliżeniu

Wielu tutaj prawdopodobnie zdaje sobie sprawę z ostatnich superliniowych dolnych granic Alon dla -net w naturalnych ustawieniach geometrycznych [PDF] . Chciałbym wiedzieć, co, jeśli w ogóle, taka dolna granica implikuje przybliżenie powiązanych problemów z zestawem Cover / Hitting Set. ϵϵ\epsilon Aby być nieco bardziej szczegółowym, rozważ rodzinę przestrzeni zasięgu, na …

10 cg.comp-geom set-cover hypergraphs approximation-hardness epsilon-nets

2

Dolne granice dla liniowego problemu satysfakcji

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ę, jaką kryje się za tą trasą, aby udowodnić tę granicę? Jaka …

10 cg.comp-geom lower-bounds algebraic-complexity

3

Bardziej intuicyjny dowód twierdzenia o strefie?

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 argumentem ładowania. …

10 cg.comp-geom

1

Dowód problemu dla górnej granicy sumy pierwiastków kwadratowych

W [1] Garey i in. określić, co później będzie znane jako problem sumy pierwiastków kwadratowych w trakcie opracowywania kompletności NP euklidesowej TSP. Podane liczby całkowite a1,a2,…,ana1,a2,…,ana_1, a_2, \ldots, a_n i LLLokreśl, czy a1−−√+a2−−√+⋯+an−−√<La1+a2+⋯+an<L\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L Zauważają, że nie jest nawet oczywiste, że problem ten …

9 reference-request cg.comp-geom na.numerical-analysis

1

Wymiar VC komórek Voronoi w R ^ d?

Załóżmy, że mam punktów w . Indukują one diagram Voronoi. Jeśli przypiszę do każdego z punktów etykietę , wywołają one funkcję binarną na . Pytanie: jaki jest wymiar VC wszystkich takich możliwych funkcji binarnych indukowanych przez niektóre punkty i pewne oznakowanie tych punktów?kkkRdRd\mathbb{R}^dkkk±±\pmRdRd\mathbb{R}^dkkk

9 cg.comp-geom machine-learning lg.learning convex-geometry high-dimensional-geometry

2

Wybierz dwie liczby, które sumują się do , używając sublinearnego czasu zapytania

Oto problem najbliższego sąsiada. Biorąc pod uwagę liczby rzeczywiste (bardzo duże !), Plus cel rzeczywisty , znajdź i których SUMA jest najbliższe . Umożliwiamy rozsądne wstępne przetwarzanie / indeksowanie (do ), ale w czasie zapytania (dane ) wynik powinien zostać zwrócony bardzo szybko (np. czas).za1, ... ,zana1,…,ana_1, \ldots, a_nnnnpppzajaaia_izajotaja_jpppza1, ... …

9 ds.algorithms cg.comp-geom ds.data-structures

1

Algorytm aproksymacji wypukłych ciał przez wypukły kadłub elipsoid

Pracuję w dziedzinie inżynierii budowlanej i chciałbym znaleźć skuteczny algorytm do konstruowania aproksymacji (w metodzie Hausdorffa) ciała wypukłego K.K.K przez wypukły kadłub nnn elipsoidy, dla niektórych naprawione nnn. Obecnie pracuję tylko w wymiarach 2 i 3. Moim pierwszym pomysłem była praca w podwójnej przestrzeni za pomocą funkcji wsparcia hK.hK.h_K z …

9 cg.comp-geom approximation convex-geometry

1

Czy istnieje odpowiedni algorytm do rysowania mieszanego wykresu okręgu / zależności w układzie współrzędnych?

Szukam algorytmu do rysowania mieszanego wykresu okręgów / zależności (dla aplikacji językowych). Taki wykres miałby dwa różne typy wierzchołków (tokeny, węzły) i dwa różne typy krawędzi (hierarchiczne, niehierarchiczne). Jestem nowy w teorii grafów i algorytmach w ogóle i mam nadzieję, że to pytanie nie koliduje np. Z wymaganiami dotyczącymi tej …

9 ds.algorithms graph-algorithms cg.comp-geom graph-drawing

1

Liczenie liczby grubych obszarów pokrywających się z kwadratem

Pozwolić S.SSbyć kwadratem jednostkowym. W funkcjiββ\beta, jaka jest maksymalna liczba ββ\beta-tłuszczowe regiony rozłączne parami o średnicy co najmniej 1, które mogą się przecinaćS.SS? Poniżej podajemy liczbę, która to pokazuje β= 1β=1\beta=1, maksymalna liczba to 7. Po co β=2,3,…,nβ=2,3,…,n\beta = 2, 3, \ldots, n? Przywołaj definicję tłuszczu dla regionów w płaszczyźnie. …

9 cg.comp-geom

2

Wymiar VC kulek w 3 wymiarach

Szukam wymiaru VC następującego zestawu układów. Wszechświat U={p1,p2,…,pm}U={p1,p2,…,pm}U=\{p_1,p_2,\ldots,p_m\} takie, że U⊆R3U⊆R3U\subseteq \mathbb{R}^3. W ustawionym systemieRR\mathcal{R} każdy zestaw S∈RS∈RS\in \mathcal{R} odpowiada kuli w R3R3\mathbb{R}^3 tak, że zestaw SSS zawiera element w UUU tylko wtedy, gdy zawiera odpowiednią kulę R3R3\mathbb{R}^3. Szczegóły, które już znam. Wymiar VC jest co najmniej 4. Jest tak, …

9 cg.comp-geom machine-learning vc-dimension

2

Wielokąt w ramach problemu generalizacji wielokąta

Chciałbym przeprosić wszystkie poniższe posty. Wybrałem niewłaściwe forum, aby pierwotnie to opublikować. Jednak zamiast uczynić to kompletnym marnotrawstwem, przerobiłem pytanie, aby było prawdziwym problemem „teoretycznej informatyki”. Problem: Utwórz algorytm, który pobiera zestaw n uporządkowanych punktów na płaszczyźnie 2D, które tworzą kontur prostego wielokąta A, który może, ale nie musi, być …

9 ds.algorithms cg.comp-geom polygon

1

Objętość obliczeniowa wielowymiarowych wypukłych wielościanów

Szukam oprogramowania do obliczania / szacowania objętości wielowymiarowych wypukłych wielościanów. Mówiąc dokładniej, jestem zainteresowany programem, który może obsługiwać ciałannn wierzchołki w rered-wymiarowa przestrzeń z parametrami z grubsza określonymi następująco: re≤ 50re≤50d \le 50 i n ≤ 1000n≤1000n \le 1000. Pamiętaj, że nie ma gwarancji liczby twarzy. Strona Jeffa Ericksona zawiera …

9 cg.comp-geom software convex-geometry high-dimensional-geometry

1

Czy triangulacje Delaunaya na sferze maksymalizują minimalny kąt?

Triangulacje Delaunaya w płaszczyźnie maksymalizują minimalny kąt w trójkącie. Czy to samo dotyczy triangulacji punktów w kuli ziemskiej przez Delaunaya? (tutaj „kąt” to kąt lokalny w sąsiedztwie wierzchołka na wierzchołku). Zainspirowany, ale niezwiązany z tym pytaniem na Math.SE.

9 cg.comp-geom delaunay-triangulation

2

Obliczanie odległości do k-tego najbliższego sąsiada dla wszystkich punktów w zestawie

W przypadku aplikacji uczenia maszynowego moja grupa musi obliczyć odległość euklidesową do tego najbliższego sąsiada w zbiorze dla każdego (dla od 5 do około 100 oraz kilkaset do kilku milionów). Obecnie podejście albo oczywiste z drzewem kd na , które gdy jest wysokie, ajest stosunkowo niski, nigdy nie wygrywa. (Wszystko …

9 reference-request cg.comp-geom near-neighbors

1

Euklidesowy problem z pojemną lokalizacją obiektu

W instrumentu Capacitated Lokalizacja problem (CFLP) , daje nam szereg klientów oraz zestaw potencjalnych obiektów . Każdy klient ma żądanie które musi być obsługiwane przez jedno lub więcej otwartych obiektów. Każdy obiekt ma koszt otwarcia i ma pojemność , które jest popyt, że maksymalny zakład może służyć. Koszt obsługi jednej …

9 ds.algorithms cg.comp-geom approximation-algorithms

Pytania otagowane jako cg.comp-geom