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...
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 puntos en R d . Estos inducen un diagrama de Voronoi. Si asigno a cada uno de los k puntos una etiqueta ± , estos inducen una función binaria en R d . Pregunta: ¿cuál es la dimensión VC de todas esas funciones binarias posibles inducidas por algunos k puntos y algún etiquetado...
Estoy trabajando en el campo de la ingeniería estructural y me gustaría encontrar un algoritmo eficiente para construir una aproximación (en la métrica de Hausdorff) de un cuerpo convexo por el casco convexo de elipsoides, para algunos fijos . Actualmente solo estoy trabajando en las dimensiones 2...
Estoy buscando un algoritmo para dibujar un gráfico mixto de circunscripción / dependencia (para una aplicación lingüística). Tal gráfico tendría dos tipos diferentes de vértices (tokens, nodos) y dos tipos diferentes de bordes (jerárquico, no jerárquico). Soy nuevo en teoría de gráficos y...
Aquí hay un problema vecino más cercano. Dados los reales (¡muy grande !), Más el objetivo real , encuentre y cuyo SUM sea más cercano a . Permitimos un preprocesamiento / indexación razonable de (hastauna1, ... , unnortea1,…,ana_1, \ldots, a_np a i a j p a 1 , … , a n O ( n log n ) p O ( log n...
Para una aplicación de aprendizaje de máquina, mis necesidades de grupo para calcular la distancia euclídea a la ésimo vecino más cercano en un conjunto para cada (para entre 5 y aproximadamente 100 , y algunos cientos hasta unos pocos millones). Actualmente estamos utilizando el enfoque de fuerza...
Sea una unidad cuadrada. En función de β , ¿cuál es el número máximo de regiones β- grasas disgregadas en pares con un diámetro de al menos 1 que puede intersecar S ?SSSββ\betaββ\betaSSS A continuación, damos una figura que muestra que para , el número máximo es 7. ¿Qué pasa con...
Me gustaría disculparme por todas las publicaciones a continuación. Elegí el foro equivocado para publicar esto originalmente. Sin embargo, en lugar de hacer de esto un desperdicio completo, he reelaborado la pregunta para que sea un verdadero problema de "Ciencia de la Computación...
Estoy buscando la dimensión VC del siguiente sistema establecido. Universo tal que U ⊆ R 3 . En el sistema de conjuntos R, cada conjunto S ∈ R corresponde a una esfera en R 3 de modo que el conjunto S contiene un elemento en U si y solo si la esfera correspondiente lo contiene en R 3 .U= { p1, p2,...
Estoy buscando un software para calcular / estimar el volumen de poliedros convexos de alta dimensión. Más específicamente, estoy interesado en un programa, que puede manejar cuerpos con vértices en d espacio dimensional con los parámetros delimitadas aproximadamente como sigue: d ≤ 50 y n ≤ 1000 ....
Las triangulaciones de Delaunay en el plano maximizan el ángulo mínimo en un triángulo. ¿Es lo mismo válido para la triangulación de puntos de Delaunay en la esfera? (aquí el "ángulo" es el ángulo local en un vecindario alrededor del vértice en el vértice). Inspirado pero no relacionado con esta...
En el Fondo capacitado Localización de problemas (CFLP) , se nos da un conjunto de clientes y un conjunto de posibles instalaciones F . Cada cliente j ∈ C tiene una demanda d j que debe ser atendida por una o más instalaciones abiertas. Cada instalación i ∈ F tiene un coste de apertura f i y tiene...
Tuve dificultades para encontrar algoritmos o artículos publicados sobre triangulación de polígonos auto intersectantes (también polígonos con estructura de agujeros). ¿Alguien puede guiarme para encontrar papel / algoritmo publicado, por favor? PD: alguien etiquete esta pregunta apropiadamente,...
En [1], Garey et al. identifique lo que luego se conocería como el problema de la suma de las raíces cuadradas en el curso de la determinación de la integridad de NP del TSP euclidiano. Dados los enteros y , determine sia1,a2,…,ana1,a2,…,anortea_1, a_2, \ldots, a_nLLLuna1--√+a2−-√+ ⋯ +...
El lema de corte (también conocido como lema de descomposición celular) establece que dadas líneas en el plano, es posible dividirlo en regiones O ( r 2 ) (incluso triángulos) para cualquier 1 ≤ r ≤ n de manera que el interior de cualquier región esté intersectado por líneas O ( n / r ) . Para más...
Editar: Creo que el espíritu de la pregunta era bueno, pero debe mejorarse. Las suposiciones hechas para el lanzamiento de la moneda hicieron esa pregunta trivial, y la tirada del dado todavía no está suficientemente definida. ¿Cuáles son las suposiciones razonables que podemos hacer sobre una...
¿Cuáles son los resultados más conocidos para una estructura de datos que ofrece las siguientes operaciones en conjuntos de puntos en el espacio euclidiano bidimensional: insert(x)insert(x)insert(x) delete(x)delete(x)delete(x) (donde k es un número entero mayor que 0) devuelve los k puntos más...
Un -net para un espacio de rango es un subconjunto de tal que no es vacío para todos tal que.( X , R ) N X N ∩ R R ∈ R | X ∩ R | ≥ ε | X |εε\varepsilon( X, R )(X,R)(X,\mathcal{R})norteNNXXXnorte∩ RN∩RN\cap RR ∈ RR∈RR\in \mathcal{R}El | X∩ R | ≥ ε | XEl ||X∩R|≥ε|X||X\cap R| \ge \varepsilon |X| Dado...
Esta es una publicación cruzada de MathOverflow. El problema de probar si una red de cara simplicial (informalmente, un grupo de caras) es politopal a veces se llama el problema de Steinitz . Sturmfels y Bokowski avanzaron un conjunto de métodos a fines de los años 80 para probar si la red...