Teoretyczne informatyka cg.comp-geom

2

Pokryj wielokąt wklęsły minimalną liczbą prostokątów

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 nakładających się prostokątów minimalnie ograniczających każdy trójkąt, a następnie łączenie tych prostokątów …

11 co.combinatorics cg.comp-geom

3

Znajdź najkrótszą parą odległość punktów w o (n log n)?

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 (stosunkowo) prosty algorytm dzielenia i zdobywania, który rozwiązuje zadanie w czasie .Θ(nlogn)Θ(nlog⁡n)\Theta(n \log …

11 ds.data-structures cg.comp-geom

2

Warianty galerii sztuki z widocznością parą?

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 parę strażników. Na przykład, jedną z formuł może być …

11 reference-request cg.comp-geom

2

Średnie osadzenia zniekształceń

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 )( …

11 approximation-algorithms cg.comp-geom embeddings

4

Redukcja wymiarów z luzem?

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 - ϵ ) | …

11 ds.algorithms approximation-algorithms cg.comp-geom metrics embeddings

1

Znalezienie podwójnego wykresu

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 osadzonego wykresu jako wierzchołki i dodając krawędź między dwoma …

11 ds.algorithms reference-request graph-theory cg.comp-geom topological-graph-theory

4

Odzyskiwanie nachylenia cyfrowej linii

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 rozciąga się na liczbach całkowitych (lub bloku kolejnych liczb …

11 reference-request cg.comp-geom cv.computer-vision image-processing

1

Czy w NP należy sprawdzić, czy wypukły kadłub zawiera kulę jednostkową?

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ć ten fakt za pomocą programowania liniowego. Nie …

10 cc.complexity-theory cg.comp-geom

1

Najdłuższa krawędź chciwego klucza w równomiernie rozmieszczonych zestawach punktów w

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 przestrzenie miar).N …

10 cg.comp-geom

2

Granice kompromisowe dla liczenia zakresu półprzestrzeni

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 hierarchicznych), możemy wykonać zliczanie zasięgu dla zapytań, które są przecięciem półprzestrzeni , dla …

10 reference-request ds.data-structures cg.comp-geom

1

Schemat Voronoi na wykresie

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 „s Woronoja obszar . …

10 reference-request graph-theory cg.comp-geom

2

Pokrycie prostego wielokąta okręgami

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 ?SSSkkkrrrSSSkkkrrrrrrkkk

10 cg.comp-geom planar-graphs set-cover

2

Sortowanie punktów, aby zminimalizować minimalną odległość euklidesową między kolejnymi punktami

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 euklidesowej między kolejnymi punktami.

10 graph-algorithms cg.comp-geom optimization

1

Miejsca, w których przydatna jest kolejność punktów wzdłuż przechodzącego przez nie prostokąta

Wiemy, że znalezienie wypukłego kadłuba punktów na płaszczyźnie ma dolną granicę w czasie jego działania. Jeśli jednak punkty są podane w kolejności, w jakiej występują wzdłuż prostego wielokąta, który ma te punkty jako wierzchołki, to ich wypukły kadłub można znaleźć w czasie liniowym.nnnΩ ( n logn )Ω(nlog⁡n)\Omega(n\log n) Uważam to …

10 cg.comp-geom

1

Zamknięcie w ramach sumy Minkowskiego.

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 …

10 cg.comp-geom

Pytania otagowane jako cg.comp-geom