Étant donné les points dans R d et une distance l, trouver le plus grand sous-ensemble de ces points de sorte que la distance euclidienne de deux d'entre eux ne dépasse pas l .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll Quelle est la complexité de ce problème? Dans le graphique sur les...
Existe-t-il désormais des algorithmes / preuves plus simples pour trianguler un polygone plan en temps linéaire? Quelle est une bonne ressource sur l'état de l'art de ce fameux
Quelle est la complexité de calcul du problème suivant: étant donné deux matrices complexes et vérifiez s'il existe une matrice de permutation telle que: n×nn×nn\times nAAABBBPPPB=PAPT.B=PAPT.B = P A P^T. Si cela aide, on peut supposer que et B sont hermitiens (ou même que A et B sont réels et...
Pour une incorporation plane d'un graphique plan sur un plan à bords droits, définissez un sommet comme un sommet net si l'angle maximum entre deux bords consécutifs autour de lui est supérieur à 180. Ou en d'autres termes, s'il existe une ligne passant par ce sommet dans l'incorporation de telle...
Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...
Dans cet article sur "L'emballage de cercle pour la conception d'origami est difficile" par Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, à la page 15, figure 13, ils prétendent que la longueur du côté du plus petit carré qui entoure deux cercles de la zone 1/2 chacun est 1,471299. D'après mes...
Il existe un beau théorème de Koebe (voir ici ) qui stipule que tout graphe planaire peut être dessiné comme un graphe de baisers de disques (très romantique ...). (Autrement dit, tout graphique plan peut être dessiné comme le graphique d'intersection des disques.) Le théorème de Koebe n'est pas...
J'ai de la difficulté à comprendre une étape dans le document de Dobkin et Kirkpatrick sur la séparation des polyèdres. J'essaie de comprendre cette version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Il soutient qu'après avoir connu la meilleure séparation de...
Après avoir entendu Emo Welzl parler du sujet cet été, je sais que le nombre de triangulations d'un ensemble de points dans le plan se situe entre environ et . Toutes mes excuses si je ne suis pas à jour; les mises à jour sont les bienvenues.nnnΩ(8.48n)Ω(8.48n)\Omega(8.48^n)O(30n)O(30n)O(30^n) J'ai...
Supposons que l'on vous donne un ensemble de n points dans le plan et que vous souhaitez vérifier s'ils forment un polygone n convexe, c'est-à-dire s'ils se trouvent tous sur la coque convexe. Je me demandais si quelqu'un savait comment faire cela en temps o (nlogn), c'est-à-dire sans calculer le...
J'ai rencontré ce problème dans un domaine de la physique assez éloigné de l'informatique, mais cela semble être le type de question qui a été étudié en CS, alors j'ai pensé tenter ma chance en le posant ici. Imaginez que l'on vous donne un ensemble de points et une liste de certaines des distances...
Je recherche une structure de données qui maintiendrait une table entière ttt de taille nnn , et permettant les opérations suivantes dans le temps O(logn)O(Journaln)O(\log n) . increase(a,b)augmenter(une,b)\text{increase}(a,b) , ce qui
Il est facile de vérifier que, étant donné la grille dimensionnelle d des points entiers , avec la contiguïté régulière, on peut trouver un séparateur de taille n d - 1 (il suffit de choisir n'importe quel hyperplan central et de supprimer tout ses sommets). Il n'est pas non plus trop difficile...
Y a-t-il des problèmes qui sont NP-complets lors de l'utilisation de la géométrie euclidienne mais qui sont bien définis et résolubles en temps polynomial pour une géométrie non
J'ai assigné à mes élèves le problème de trouver un triangle cohérent avec une collection de points dans , étiqueté avec . (Un triangle est cohérent avec l'échantillon étiqueté si contient tous les points positifs et aucun des points négatifs; par hypothèse, l'échantillon admet au moins 1 triangle...
CCC est un rectangle à axe parallèle. C1,…,CnC1,…,CnC_1,\dots,C_n sont des rectangles parallèles axe-parallèle disjoints tels que , comme ceci:C1∪⋯∪Cn⊊CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Une partition préservant le rectangle de CCC est une partition C=E1∪⋯∪ENC=E1∪⋯∪ENC = E_1\cup\dots\cup...
La géométrie informatique est un domaine que je trouve assez intéressant, et j'aimerais consacrer environ un mois ou deux à un projet qui va m'initier à cela et m'aider à apprendre les concepts clés. Quelle est la bonne façon d'aborder cela et quels sont les concepts clés dont je devrais être sûr...
Soit des points distincts asseyez-vous dans R 2 . On dit que les points i et j sont voisins si | i - j | < 31 . . . n1...n1 ... nR2R2\mathbb{R}^2jeiijjj , ce qui signifie que chaque point est voisin avec des points avec des index à moins de 2 , s'enroulant autour.| i-j | <3( modn - 2...
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...
Ceci est destiné à être une question complémentaire au précédent article de Robin Kothari sur les résultats de la dureté polynomiale . Plus précisément, je suis intéressé à voir des preuves de dureté pour des problèmes qui sont censés avoir environ des limites inférieures, et je dis à peu près pour...