Dados los puntos en R d y una distancia l, encuentre el subconjunto más grande de estos puntos de tal manera que la distancia euclidiana de ninguno de ellos exceda l .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll ¿Cuál es la complejidad de este problema? En el gráfico sobre los puntos que...
Para una incrustación plana de un gráfico plano en un plano con bordes rectos, defina un vértice como un vértice afilado si el ángulo máximo entre dos bordes consecutivos a su alrededor es más de 180. O, en otras palabras, si existe una línea que pase por ese vértice en la incrustación de modo que...
¿Cuál es la complejidad computacional del siguiente problema: dados dos complejos matrices y verifique si hay una matriz de permutación tal que: n × nnorte×norten\times nUNUNAsisiBPAGPAGPB = PA PT.si=PAGUNPAGT.B = P A P^T. Si ayuda, uno puede suponer que y son hermitianos (o incluso que y son...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...
¿Existen ahora algoritmos / pruebas más simples para triangular un polígono plano en tiempo lineal? ¿Cuál es un buen recurso sobre el estado del arte de este famoso
En este documento sobre "Empaque circular para diseño de origami es difícil" por Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, en la página 15, figura 13, afirman que la longitud lateral del cuadrado más pequeño que encierra dos círculos de área 1/2 cada uno es 1.471299. Según mis cálculos,...
Hay un hermoso teorema de Koebe (ver aquí ) que establece que cualquier gráfico plano se puede dibujar como un gráfico de besos de discos (muy romántico ...). (Dicho de otra manera, cualquier gráfico plano se puede dibujar como el gráfico de intersección de los discos). El teorema de Koebe no es...
Tengo serios problemas para comprender un paso en el documento de Dobkin y Kirkpatrick sobre la separación de los poliedros. Estoy tratando de entender esta versión: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Se argumenta que después de que conocemos la mejor...
Después de escuchar a Emo Welzl hablar sobre el tema este verano, sé que el número de triangulaciones de un conjunto de puntos en el plano está entre Ω ( 8.48 n ) y O ( 30 n ) . Disculpas si estoy desactualizado; actualizaciones bienvenidas.nortenortenΩ ( 8.48norte)Ω(8.48norte)\Omega(8.48^n)O (...
Asigné a mis alumnos el problema de encontrar un triángulo consistente con una colección de puntos en , etiquetado con . (Un triángulo es consistente con la muestra etiquetada si contiene todos los puntos positivos y ninguno de los negativos; por supuesto, la muestra admite al menos 1 triángulo...
Suponga que tiene un conjunto de n puntos en el plano y desea verificar si forman un polígono convexo n, es decir, si todos se encuentran en el casco convexo. Me preguntaba si alguien sabe cómo hacer esto en o (nlogn) tiempo, es decir, sin calcular el
Estoy buscando una estructura de datos que mantenga una tabla entera de tamaño , y que permita las siguientes operaciones en el tiempo .n O ( log n )tttnortenortenO ( logn )O(Iniciar sesiónnorte)O(\log n) aumento ( a , b )incrementar(un,si)\text{increase}(a,b) , que aumenta .t [ a ] , t [a + 1 ]...
Encontré este problema en un área de la física bastante alejada de la informática, pero parece ser el tipo de pregunta que se ha estudiado en CS, así que pensé en probar suerte preguntándola aquí. Imagine que le dan un conjunto de puntos y una lista de algunas de las distancias entre los puntos ....
Es fácil verificar que, dada la cuadrícula d dimensional de los puntos enteros , con la adyacencia regular, se puede encontrar un separador de tamaño n d - 1 (simplemente elija cualquier hiperplano medio y elimine todos sus vértices). Tampoco es demasiado difícil (pero definitivamente no es...
¿Hay algún problema que sea NP completo cuando se usa geometría euclidiana pero que está bien definido y puede resolverse en tiempo polinómico para alguna geometría no
¿Qué se sabe sobre el siguiente problema? Dada una colección de funciones , encuentre una subcolección más grande sujeta a la restricción que VC-Dimension para algún entero .f : { 0 , 1 } n → { 0 , 1 } S ⊆ C ( S ) ≤ k kCCCF: { 0 , 1 }norte→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆...
Deje puntos distintos 1...n1...n1 ... n sentarse en R2R2\mathbb{R}^2 . Decimos que los puntos iii y jjj son vecinos si , lo que significa que cada punto es vecino con puntos con índices dentro de 2 , envolviendo.|i−j|<3(modn−2)|i−j|<3(modn−2)|i-j| < 3 \pmod{n-2}222 El problema es: Para...
Esto pretende ser una pregunta de seguimiento a la publicación anterior de Robin Kothari sobre los resultados de la dureza del tiempo polinomial . Específicamente, estoy interesado en ver algunas pruebas de dureza para problemas que se cree que tienen límites inferiores aproximadamente , y digo...
CCC es un rectángulo paralelo al eje. C1,…,CnC1,…,CnC_1,\dots,C_n son rectángulos paralelos entre ejes pares tal que , así:C1∪⋯∪Cn⊊CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Una partición de C que preserva los rectángulosCCC es una partición C=E1∪⋯∪ENC=E1∪⋯∪ENC = E_1\cup\dots\cup E_N , de modo...
La geometría computacional es un área que me parece bastante interesante, y me gustaría dedicar aproximadamente un mes o dos a un proyecto que me presente a esto y me ayude a aprender conceptos clave. ¿Cuál es una buena manera de abordar esto y cuáles son los conceptos clave que debería estar...