Que sait-on du problème suivant? Étant donné une collection de fonctions f : { 0 , 1 } n → { 0 , 1 } , trouver une plus grande sous-collection S ⊆ C soumise à la contrainte VC-Dimension ( S ) ≤ k pour un entier k .CCCF: { 0 , 1 }n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆ CS⊆CS...
Le problème des galeries d'art traditionnelles met en place une région et des gardes avec une certaine notion de visibilité, et demande le nombre minimum de gardes à placer pour voir toute la région. Quelqu'un a-t-il déjà examiné des variantes de galeries d'art où la zone de visibilité est plutôt...
Le lemme de Johnson-Lindenstrauss dit grosso modo que pour toute collection de points dans , il existe une carte où tel que pour tout : Il est connu que des instructions similaires ne sont pas possibles pour la métrique , mais est-il connu s'il existe un moyen de contourner une telle baisse limites...
Selon le livre Topological Graph Theory de Gross et Tucker, étant donné l'incorporation cellulaire d'un graphique sur une surface (par `` surface '', je veux dire ici une sphère avec quelques poignées, et ci-dessous réfère à la sphère avec exactement poignées), on peut définir une multigraphe...
Étant donné deux sous-ensembles de l' hypercube à dimensions (c'est-à-dire ), je cherche un algorithme qui récupère les points st le hamming la distance (ou la distance sur l'hypercube) est minimale. L'algorithme naïf qui vérifie juste chaque paire a besoin de time, existe-t-il un meilleur résultat...
J'essaie de couvrir un simple polygone concave avec un minimum de rectangles. Mes rectangles peuvent avoir n'importe quelle longueur, mais ils ont des largeurs maximales, et le polygone n'aura jamais d'angle aigu. J'ai pensé à essayer de décomposer mon polygone concave en triangles qui produisent...
Etant donné un ensemble d'hyperplans déterminé par les vecteurs normaux , ses types de cellules (ou vecteurs de signe) sont tous des vecteurs t ∈ { + , - } m pour lesquels il existe un vecteur v ∈ R d de sorte que ⟨ v , h i ⟩ ≠ 0 et t i = signe ( ⟨ v , h i ⟩ )h1, … , Hm∈ Rréh1,…,hm∈Rdh_1,\dots,h_m...
Y a-t-il eu des travaux pour récupérer la pente d'un segment de ligne de sa numérisation? On ne peut pas le faire avec une précision parfaite, bien sûr; ce que l'on veut, c'est une méthode pour dériver d'une ligne numérisée un intervalle de pentes possibles. (La notion de ligne numérisée que...
(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)} \} Il existe cependant d'autres...
L'exercice suivant a été remis aux étudiants que je supervise: Étant donné points dans le plan, imaginez un algorithme qui trouve une paire de points dont la distance est minimale parmi toutes les paires de points. L'algorithme doit s'exécuter au temps .nnno(n2)o(n2)o(n^2) Il existe un algorithme...
Entrée: Un ensemble de points dans R 3 et un entier k ≤ n .nnnR3R3\mathbb{R}^3k≤nk≤nk \le n Sortie: le plus petit cadre de délimitation aligné sur l'axe du volume qui contient au moins de ces n points.kkknnn Je me demande si des algorithmes sont connus pour ce problème. Le mieux que je pouvais...
Dans SODA 1995 , Jeff Erickson a montré des limites inférieures pour la satisfiabilité linéaire (vérifier si un certain ensemble de n nombres réels satisfait une équation linéaire sur r variables). La méthode de preuve utilise des infinitésimales et le principe de transfert de Tarski .rrrnnnrrr...
Étant donné un ensemble de points dans l' espace euclidien de dimension , le problème est de déterminer si la coque convexe contient la boule unitaire centrée à l'origine.nnnréréd Ce problème est-il dans NP? Il est en co-NP car on peut donner un point dans la balle en dehors de la coque convexe...
Quelle est la meilleure limite actuelle pour effectuer des requêtes de comptage de demi-espace sur un ensemble de points dimensionnels, exprimée sous la forme d'un compromis temps / espace. Selon l'article fondamental de Matousek de 1993 (Théorème 6.2, Recherche de plage avec des coupes...
Soit un graphique avec des arêtes pondérées (positivement). Je veux définir le diagramme de Voronoi pour un ensemble de nœuds / sites S , associer à un nœud v ∈ S le sous-graphe R ( v ) de G induit par tous les nœuds strictement plus proche de v que de tout autre nœud en S , mesurant la longueur...
Soit un ensemble de points dans . Pour tout , une clé est un graphique non orienté pondéré sous la mesure euclidienne, de sorte que pour deux points , , la distance la plus courte en , , est au plus fois la distance euclidienne entre et ,(notez que cette définition peut facilement être étendue à...
Supposons que j'ai un polygone simple et un entier k . Quelles sont les approches existantes pour trouver le plus petit rayon r tel que je puisse couvrir S avec k cercles de rayon r ? Que diriez-vous si r est fixe, et je veux minimiser k
Étant donné un ensemble de points dans un espace cartésien 3D, je recherche un algorithme qui triera ces points, de sorte que la distance euclidienne minimale entre deux points consécutifs soit maximisée. Il serait également avantageux que l'algorithme tende vers une distance euclidienne moyenne...
Le théorème de zone dit que si nous poignardons un arrangement de n lignes avec une autre ligne, la complexité totale de sa zone , l'ensemble de toutes les faces 0, 1 et 2 adjacentes, est O (n). La constante réelle est quelque chose comme 6n au moins comme indiqué dans divers manuels, et la preuve...
La somme de Minkowski de deux ensembles de vecteurs est donnée parA , B ∈ RréA,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 \} Je viens d'entendre un problème intéressant (attribué à Dan Halperin): étant donné une forme ,...