CCC ist ein achsparalleles Rechteck. C1, … , CnC1,…,CnC_1,\dots,C_n sind achsparallele Rechtecke die paarweise im Inneren getrennt sind, so dass wie :C1∪ ⋯ ∪ Cn⊊ CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Eine rechteckerhaltende Partition von CCC ist eine Partition C= E1∪ ⋯ ∪ ENC=E1∪⋯∪ENC =...
Eingabe: Eine Menge von Punkten in R 3 und eine ganze Zahl k ≤ n .nnnR.3R3\mathbb{R}^3k ≤ nk≤nk \le n Ausgabe: Der kleinste an der Volumenachse ausgerichtete Begrenzungsrahmen, der mindestens dieser n Punkte enthält.kkknnn Ich frage mich, ob Algorithmen für dieses Problem bekannt sind. Das Beste,...
Bei einer Menge von Hyperebenen, die durch die Normalenvektoren , sind ihre Zelltypen (oder Vorzeichenvektoren) alle Vektoren t ∈ { + , - } m, für die ein Vektor v ∈ R d existiert so daß ⟨ v , h i ⟩ & ne; 0 und t i = sign ( ⟨ v , h i ⟩ )h1, … , H.m∈ R.dh1,…,hm∈Rdh_1,\dots,h_m \in \mathbf R^dt ∈...
Ich versuche, ein einfaches konkaves Polygon mit einem Minimum an Rechtecken zu bedecken. Meine Rechtecke können beliebig lang sein, aber sie haben maximale Breiten, und das Polygon hat niemals einen spitzen Winkel. Ich dachte darüber nach, mein konkaves Polygon in Dreiecke zu zerlegen, die einen...
Die folgende Übung wurde an von mir betreute Schüler verteilt: Entwickeln Sie bei nnn Punkten in der Ebene einen Algorithmus, der ein Punktpaar findet, dessen Abstand zwischen allen Punktpaaren minimal ist. Der Algorithmus sollte in der Zeit laufen o(n2)o(n2)o(n^2). Es gibt einen (relativ)...
Das Problem der traditionellen Kunstgalerie richtet eine Region und Wachen mit einer gewissen Sichtbarkeit ein und fordert die Mindestanzahl von Wachen an, die platziert werden müssen, um die gesamte Region zu sehen. Hat sich jemals jemand Kunstgalerievarianten angesehen, bei denen der...
Das Johnson-Lindenstrauss-Lemma sagt ungefähr, dass für jede Sammlung von Punkten in eine Karte wobei so dass für alle : Es ist bekannt, dass ähnliche Aussagen für die Metrik nicht möglich sind , aber es ist bekannt, ob es eine Möglichkeit gibt, eine solche niedrigere zu Grenzen durch schwächere...
Wurde daran gearbeitet, die Steigung eines Liniensegments nach seiner Digitalisierung wiederherzustellen? Das kann man natürlich nicht mit perfekter Genauigkeit machen; Was man will, ist eine Methode, aus einer digitalisierten Linie ein Intervall möglicher Steigungen abzuleiten. (Der Begriff einer...
Bei zwei Teilmengen des dimensionalen Hyperwürfels (dh M , N ⊆ { 0 , 1 } d ) suche ich nach einem Algorithmus, der die Punkte m ∈ M , n ∈ N st der Hamming-Distanz (oder L 1 -) abruft Abstand auf dem Hyperwürfel) d H ( m , n ) ist minimal. Der naive Algorithmus, der nur jedes Paar überprüft,...
Nach dem Buch Topological Graph Theory von Gross und Tucker wird bei einer zellulären Einbettung eines Graphen auf einer Oberfläche (mit 'Oberfläche' meine ich hier eine Kugel mit einigen Griffen, und unter bezieht sich auf die Kugel mit genau Griffe) kann ein dualer Multigraph definiert werden,...
(X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow Yμμ\muρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}ρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)} \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \} Es gibt jedoch auch andere...
Angesichts einer Reihe von Punkten in einem kartesischen 3D-Raum suche ich nach einem Algorithmus, der diese Punkte so sortiert, dass der minimale euklidische Abstand zwischen zwei aufeinanderfolgenden Punkten maximiert wird. Es wäre auch vorteilhaft, wenn der Algorithmus zu einem höheren...
Angenommen, ich habe ein einfaches Polygon und eine ganze Zahl . Welche Ansätze gibt es, um den kleinsten Radius so zu finden, dass ich mit Kreisen mit dem Radius abdecken kann ? Wie wäre es, wenn fest ist und ich minimieren möchte ?S.SSr S k r r
Bei einer Menge von Punkten im d- dimensionalen euklidischen Raum besteht das Problem darin, zu bestimmen, ob die konvexe Hülle die am Ursprung zentrierte Einheitskugel enthält.nnnddd Ist das Problem in NP? Es ist in Co-NP, da man als Zeuge einen Punkt in der Kugel außerhalb der konvexen Hülle...
Sei eine Menge von N Punkten in R d . Für jedes t ≥ 1 ist ein t- Schlüssel ein ungerichteter Graph G = ( P , E ), gewichtet nach dem euklidischen Maß, so dass für zwei beliebige Punkte v , u der kürzeste Abstand in G , d ( v , u ) , ist höchstens t mal der euklidische Abstand zwischen v und u , | v...
Sei ein Graph mit (positiv) gewichteten Kanten. Ich möchte das Voronoi-Diagramm für eine Menge von Knoten / Stellen S definieren , um einem Knoten v ∈ S den Teilgraphen R ( v ) von G zuzuordnen, der von allen Knoten induziert wird, die genau näher an v liegen als an jedem anderen Knoten in S , der...
Der Zonensatz besagt, dass, wenn wir eine Anordnung von n Linien mit einer anderen Linie erstechen, die Gesamtkomplexität ihrer Zone , die Menge aller angrenzenden 0-, 1- und 2-Flächen, O (n) ist. Die tatsächliche Konstante ist ungefähr 6n, zumindest wie in verschiedenen Lehrbüchern angegeben, und...
Die Minkowski-Summe zweier Sätze von Vektoren ist gegeben durchA,B∈RdA,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 \} Ich habe gerade ein interessantes Problem gehört (Dan Halperin zugeschrieben): Gibt es bei einer Form eine Form so dass...
Was ist die derzeit beste Grenze für die Durchführung von Abfragen zur Zählung des Halbraumbereichs an einer Reihe von dimensionalen Punkten, ausgedrückt in Form eines Zeit / Raum-Kompromisses. Gemäß Matouseks wegweisender Arbeit von 1993 (Satz 6.2, Bereichssuche mit effizienten hierarchischen...
Viele hier kennen wahrscheinlich Alons jüngste superlineare Untergrenzen für Netze in einer natürlichen geometrischen Umgebung [PDF] . Ich würde gerne wissen, was, wenn überhaupt, eine solche Untergrenze für die Annäherung der damit verbundenen Set-Cover- / Hitting-Set-Probleme bedeutet. ϵϵ\epsilon...