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...
Entrada: Un conjunto de puntos en R 3 y un número entero k ≤ n .nortennR3R3\mathbb{R}^3k ≤ nk≤nk \le n Salida: el cuadro delimitador alineado al eje del volumen más pequeño que contiene al menos de estos n puntos.kkknnn Me pregunto si se conocen algoritmos para este problema. Lo mejor que se me...
Dado un conjunto de hiperplanos determinados por los vectores normales , sus tipos de células (o vectores de signos) son todos los vectores t ∈ { + , - } m para los que existe un vector v ∈ R d de modo que ⟨ v , h i ⟩ ≠ 0 y t i = signo ( ⟨ v , h i ⟩ )h1, ... , hmetro∈ Rreh1,…,hm∈Rdh_1,\dots,h_m \in...
Estoy tratando de cubrir un polígono cóncavo simple con un mínimo de rectángulos. Mis rectángulos pueden tener cualquier longitud, pero tienen anchuras máximas y el polígono nunca tendrá un ángulo agudo. Pensé en tratar de descomponer mi polígono cóncavo en triángulos que produjeran un conjunto de...
El siguiente ejercicio ha sido entregado a los estudiantes que superviso: Dados nnn puntos en el plano, diseñe un algoritmo que encuentre un par de puntos cuya distancia sea mínima entre todos los pares de puntos. El algoritmo debe ejecutarse en el tiempo o(n2)o(n2)o(n^2) . Existe un algoritmo...
El problema de la galería de arte tradicional establece una región y guardias con alguna noción de visibilidad, y solicita el número mínimo de guardias que deben colocarse para ver toda la región. ¿Alguien ha mirado alguna vez las variantes de la galería de arte donde la región de visibilidad está...
El lema de Johnson-Lindenstrauss dice aproximadamente que para cualquier colección SSS de nnn puntos en RdRd\mathbb{R}^d , existe un mapa f:Rd→Rkf:Rd→Rkf:\mathbb{R}^d \rightarrow \mathbb{R}^k donde k=O(logn/ϵ2)k=O(logn/ϵ2)k = O(\log n/\epsilon^2) tal que para todos x,y∈Sx,y∈Sx, y \in S :...
¿Ha habido algún trabajo para recuperar la pendiente de un segmento de línea desde su digitalización? Uno no puede hacer esto con perfecta precisión, por supuesto; lo que uno quiere es un método para derivar de una línea digitalizada un intervalo de posibles pendientes. (El concepto de una línea...
Dados dos subconjuntos del hipercubo dimensional (es decir, M , N ⊆ { 0 , 1 } d ), estoy buscando un algoritmo que recupere los puntos m ∈ M , n ∈ N st la distancia de Hamming (o L 1 - distancia en el hipercubo) d H ( m , n ) es mínima. El ingenuo algoritmo que verifica cada par necesita | M | ⋅ |...
De acuerdo con el libro Topological Graph Theory de Gross y Tucker, dada una incrustación celular de un gráfico en una superficie (por 'superficie' me refiero aquí a una esfera con algunos asas, y debajo de refiere a la esfera con exactamente tiradores), se puede definir un multigrafo dual tratando...
Consideremos dos espacios métricos y ( Y , f ) , y una incrustación μ : X → Y . Las incrustaciones tradicionales de espacio métrico miden la calidad de μ como la peor relación de la distancia original a la final: ρ = max p , q ∈ X { d ( x , y )( X, d)(X,d)(X, d)( Y, f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X...
Dado un conjunto de puntos en un espacio cartesiano 3D, estoy buscando un algoritmo que clasifique estos puntos, de modo que se maximice la distancia euclidiana mínima entre dos puntos consecutivos. También sería beneficioso si el algoritmo tuviera una tendencia hacia una distancia euclidiana...
Supongamos que tengo un polígono simple y un entero . ¿Cuáles son algunos enfoques existentes para encontrar el radio más pequeño de modo que pueda cubrir con círculos de radio ? ¿Qué tal si es fijo y quiero minimizar ?k r S k r r
Dado un conjunto de puntos en el espacio euclidiano d dimensional, el problema es determinar si el casco convexo contiene la bola unitaria centrada en el origen.nortenortenrered ¿Es este problema en NP? Está en co-NP, ya que uno puede dar un punto en la pelota fuera del casco convexo como...
Sea un conjunto de N puntos en R d . Para cualquier t ≥ 1 , un t -spanner es un gráfico no dirigido G = ( P , E ) ponderado bajo la medida euclidiana, de modo que para cualquiera de los dos puntos v , u , la distancia más corta en G , d ( v , u ) , es a lo sumo t veces la distancia euclidiana entre...
Deje que sea un gráfico con aristas ponderadas (positivamente). Quiero definir el diagrama de Voronoi para un conjunto de nodos / sitios , para asociar con un nodo el subgrafo de inducido por todos los nodos estrictamente más cercanos a que a cualquier otro nodo en , midiendo la longitud de un...
El teorema de la zona dice que si apuñalamos una disposición de n líneas con otra línea, la complejidad total de su zona , el conjunto de todas las caras 0, 1 y 2 adyacentes a ella, es O (n). La constante real es algo así como 6n al menos como se indica en varios libros de texto, y la prueba es por...
La suma de Minkowski de dos conjuntos de vectores viene dada porA,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 \} Acabo de escuchar un problema interesante (atribuido a Dan Halperin): Dada una forma , ¿existe una forma A tal que A ⊕ A = B...
¿Cuál es el mejor límite actual para realizar consultas de conteo de rango de medio espacio en un conjunto de puntos dimensionales, expresados en forma de una compensación tiempo / espacio. De acuerdo con el artículo seminal de 1993 de Matousek (Teorema 6.2, Búsqueda de rangos con cortes...
Muchos aquí probablemente estén al tanto de los límites inferiores súper lineales recientes de Alon para redes en un entorno geométrico natural [PDF] . Me gustaría saber qué implica, en todo caso, un límite inferior acerca de la aproximación de los problemas asociados de Set Cover / Hitting Set....