jueves, 4 de julio de 2019

TEMAS DE GEOMETRÍA


La geometría computacional es una rama de la informática dedicada al estudio de algoritmos que se puede establecer en términos de geometría . Algunos problemas puramente geométricos surgen del estudio de los algoritmos geométricos computacionales , y estos problemas también se consideran parte de la geometría computacional. Si bien la geometría computacional moderna es un desarrollo reciente, es uno de los campos más antiguos de computación con una historia que se remonta a la antigüedad.
La complejidad computacional es fundamental para la geometría computacional, con una gran importancia práctica si los algoritmos se utilizan en conjuntos de datos muy grandes que contienen decenas o cientos de millones de puntos. Para tales conjuntos, la diferencia entre O ( n 2 ) y O ( n log n ) puede ser la diferencia entre días y segundos de cálculo.
El principal impulso para el desarrollo de la geometría computacional como disciplina fue el progreso en los gráficos por computadora y el diseño y fabricación asistidos por computadora ( CAD / CAM ), pero muchos problemas en la geometría computacional son de naturaleza clásica y pueden provenir de la visualización matemática .
Otras aplicaciones importantes de la geometría computacional incluyen robótica (planificación de movimiento y problemas de visibilidad), sistemas de información geográfica (GIS) (ubicación geométrica y búsqueda, planificación de rutas), diseño de circuitos integrados (diseño y verificación de geometría de circuitos integrados), ingeniería asistida por computadora (CAE) (Generación de malla), Visión por computador ( Reconstrucción 3D).
Las principales ramas de la geometría computacional son:
  • Geometría computacional combinatoria , también llamada geometría algorítmica , que trata los objetos geométricos como entidades discretas . Un libro de base en el tema por Preparata y Shamos fecha el primer uso del término "geometría computacional" en este sentido en 1975. [1]
  • Geometría computacional numérica , también llamada geometría de máquina , diseño geométrico asistido por computadora (CAGD, por sus siglas en inglés) o modelado geométrico , que se ocupa principalmente de representar objetos del mundo real en formas adecuadas para cálculos computacionales en sistemas CAD / CAM. Esta rama puede verse como un desarrollo adicional de la geometría descriptiva y, a menudo, se considera una rama de gráficos de computadora o CAD. El término "geometría computacional" en este sentido ha estado en uso desde 1971.


Combinatoria geometría computacional [ editar ]

El objetivo principal de la investigación en geometría computacional combinatoria es desarrollar algoritmos y estructuras de datos eficientes para resolver problemas planteados en términos de objetos geométricos básicos: puntos, segmentos de línea, polígonos , poliedros , etc.
Algunos de estos problemas parecen tan simples que no fueron considerados como problemas hasta la llegada de las computadoras . Considere, por ejemplo, el problema de par más cercano :
  • Dados n puntos en el plano, encuentra los dos con la menor distancia entre sí.
Uno podría calcular las distancias entre todos los pares de puntos, de los cuales hay n (n-1) / 2 , luego elegir el par con la distancia más pequeña. Este algoritmo de fuerza bruta lleva tiempo O ( n 2 ); Es decir, su tiempo de ejecución es proporcional al cuadrado del número de puntos. Un resultado clásico en geometría computacional fue la formulación de un algoritmo que toma O ( n log n ). También se han descubierto los algoritmos aleatoriosque toman O ( n ) el tiempo esperado, [3] , así como un algoritmo determinista que toma el tiempo O ( n log log n), [4] .

Clases de problemas [ editar ]

Los problemas centrales de la geometría computacional se pueden clasificar de diferentes maneras, según diversos criterios. Las siguientes clases generales pueden ser distinguidas.

Problemas estáticos [ editar ]

En los problemas de esta categoría, se da alguna entrada y la salida correspondiente necesita ser construida o encontrada. Algunos problemas fundamentales de este tipo son:
La complejidad computacional para esta clase de problemas se estima por el tiempo y el espacio (memoria de la computadora) necesarios para resolver una instancia de problema dada.

Problemas de consulta geométrica [ editar ]

En los problemas de consulta geométrica, conocidos comúnmente como problemas de búsqueda geométrica, la entrada consta de dos partes: la parte de espacio de búsqueda y la parte de consulta , que varía según las instancias del problema. Por lo general, el espacio de búsqueda debe procesarse previamente , de manera que se puedan responder de manera eficiente a múltiples consultas.
Algunos problemas fundamentales de consulta geométrica son:
  • Búsqueda de rango : preprocesar un conjunto de puntos, para contar de manera eficiente el número de puntos dentro de una región de consulta.
  • Ubicación del punto : Dada una partición del espacio en celdas, produzca una estructura de datos que indique de manera eficiente en qué celda se encuentra el punto de consulta.
  • Vecino más cercano : preprocesar un conjunto de puntos, para encontrar de manera eficiente el punto más cercano a un punto de consulta.
  • Rastreo de rayos : dado un conjunto de objetos en el espacio, produzca una estructura de datos que indique de manera eficiente qué objeto se interseca primero un rayo de consulta.
Si el espacio de búsqueda es fijo, la complejidad computacional para esta clase de problemas generalmente se estima por:
  • El tiempo y el espacio necesarios para construir la estructura de datos a buscar en
  • el tiempo (y, a veces, un espacio adicional) para responder a las consultas.
En el caso de que el espacio de búsqueda pueda variar, consulte " Problemas dinámicos ".

Problemas dinámicos [ editar ]

Otra clase importante son los problemas dinámicos , en los cuales el objetivo es encontrar un algoritmo eficiente para encontrar una solución repetidamente después de cada modificación incremental de los datos de entrada (elementos geométricos de entrada o eliminación). Los algoritmos para problemas de este tipo generalmente involucran estructuras de datos dinámicos . Cualquiera de los problemas geométricos computacionales se puede convertir en uno dinámico, al costo de un mayor tiempo de procesamiento. Por ejemplo, el problema de búsqueda de rango se puede convertir en el problema de búsqueda de rango dinámico al proporcionar la adición y / o eliminación de los puntos. El dinámico casco convexo. El problema es hacer un seguimiento del casco convexo, por ejemplo, para el conjunto de puntos que cambian dinámicamente, es decir, mientras se insertan o eliminan los puntos de entrada.
La complejidad computacional para esta clase de problemas es estimada por:
  • El tiempo y el espacio necesarios para construir la estructura de datos a buscar en
  • el tiempo y el espacio para modificar la estructura de datos buscados después de un cambio incremental en el espacio de búsqueda
  • el tiempo (y, a veces, un espacio adicional) para responder a una consulta.

Variaciones [ editar ]

Algunos problemas pueden tratarse como pertenecientes a cualquiera de las categorías, según el contexto. Por ejemplo, considere el siguiente problema.
En muchas aplicaciones, este problema se trata como de un solo disparo, es decir, pertenece a la primera clase. Por ejemplo, en muchas aplicaciones de gráficos de computadora, un problema común es encontrar en qué área de la pantalla se hace clic con un puntero . Sin embargo, en algunas aplicaciones, el polígono en cuestión es invariante, mientras que el punto representa una consulta. Por ejemplo, el polígono de entrada puede representar un borde de un país y un punto es una posición de un avión, y el problema es determinar si el avión violó el borde. Finalmente, en el ejemplo mencionado anteriormente de gráficos de computadora, en las aplicaciones CAD , los datos de entrada cambiantes a menudo se almacenan en estructuras de datos dinámicos, que pueden aprovecharse para acelerar las consultas de punto en polígono.
En algunos contextos de problemas de consulta, existen expectativas razonables sobre la secuencia de las consultas, que pueden aprovecharse para estructuras de datos eficientes o para estimaciones de complejidad computacional más estrictas. Por ejemplo, en algunos casos es importante conocer el peor de los casos para el tiempo total para la secuencia completa de N consultas, en lugar de una sola consulta. Ver también " análisis amortizado ".

Numerical geometría computacional [ editar ]

Artículo principal: diseño geométrico asistido por ordenador.
Esta rama también se conoce como modelado geométrico y diseño geométrico asistido por computadora(CAGD).
Los problemas centrales son el modelado y la representación de curvas y superficies.
Los instrumentos más importantes aquí son las curvas paramétricas y las superficies paramétricas , como las curvas de Bézier , las curvas spline y las superficies. Un importante enfoque no paramétrico es el método de nivel establecido .
Las áreas de aplicación de la geometría computacional incluyen la construcción naval, aeronaves y las industrias automotrices.








geometría conformal es el estudio del conjunto de transformaciones ( conformales ) de preservación de ángulo en un espacio.
En un espacio bidimensional real, la geometría conforme es precisamente la geometría de las superficies de Riemann . En el espacio superior a dos dimensiones, la geometría conforme puede referirse al estudio de las transformaciones conformes de lo que se denomina "espacios planos" (como los espacios o esferas euclidianas), o al estudio de las variedades conformales que son variedades Riemannianas o pseudo-Riemannianas con una clase de métricas que se definen a escala. El estudio de las estructuras planas a veces se denomina geometría de Möbius y es un tipo de geometría de Klein .

Colectores conformes [ editar ]

Una variedad conforme es una variedad pseudo-Riemanniana equipada con una clase de equivalencia de tensores métricos , en la que dos medidas g y h son equivalentes si y solo si
donde λ es una función suave de valor real definida en la variedad. Una clase de equivalencia de tales métricas se conoce como una métrica conforme o clase conforme . Por lo tanto, una métrica conforme se puede considerar como una métrica que solo se define "a escala". A menudo, las métricas conformes se tratan seleccionando una métrica en la clase conforme, y aplicando solo construcciones "invariablemente conformes" a la métrica elegida.
Una métrica conforme es conformemente plana si hay una métrica que la representa plana, en el sentido habitual de que el tensor de curvatura de Riemann se desvanece. Es posible que solo sea posible encontrar una métrica en la clase conforme que sea plana en un vecindario abierto de cada punto. Cuando es necesario distinguir estos casos, este último se denomina localmente conformemente plano , aunque a menudo en la literatura no se mantiene ninguna distinción. La n- esferaes un colector plano de conformidad local que no es globalmente plano en este sentido, mientras que un espacio euclidiano, un toro o cualquier colector conformado que esté cubierto por un subconjunto abierto de espacio euclidiano es (globalmente) plano en este sentido. Un colector plano de conformidad local es acorde a la geometría de Möbius , lo que significa que existe un ángulo que preserva el difeomorfismo local desde el colector hasta la geometría de Möbius. En dos dimensiones, cada métrica conformal es localmente conformalmente plana. En la dimensión n > 3, una métrica conforme es localmente plana si y solo si su tensor de Weyl se desvanece; en dimensión n = 3 , si y solo si el tensor de algodón desaparece
La geometría conforme tiene una serie de características que la distinguen de la geometría (pseudo-) riemanniana. La primera es que, aunque en (pseudo) geometría riemanniana, una tiene una métrica bien definida en cada punto, en la geometría conforme solo tiene una clase de métrica. Por lo tanto, la longitud de un vector tangente no se puede definir, pero el ángulo entre dos vectores aún puede definirse. Otra característica es que no hay conexión Levi-Civita porque si g y λ 2 g son dos representantes de la estructura conforme, entonces los símbolos de Christoffel de g y λ 2 g no estarían de acuerdo. Los asociados con λ 2g implicaría derivados de la función λ mientras que los asociados con g no.
A pesar de estas diferencias, la geometría conforme todavía es manejable. La conexión y el tensor de curvatura de Levi-Civita , aunque solo se definen una vez que se ha seleccionado a un representante particular de la estructura conforme, sí satisfacen ciertas leyes de transformación que involucran a la λ y sus derivados cuando se elige un representante diferente. En particular, (en una dimensión superior a 3) el tensor de Weyl no depende de λ , por lo que es un invariante conforme . Además, aunque no hay una conexión Levi-Civita en una variedad conforme, se puede trabajar con una conexión conforme , que puede manejarse como un tipo de conexión Cartan.modelado en la geometría de Möbius asociada, o como una conexión Weyl . Esto permite definir la curvatura conformal y otros invariantes de la estructura conformal.

Geometría de Möbius [ editar ]

La geometría de Möbius es el estudio del " espacio euclidiano con un punto agregado en el infinito", o un espacio" Minkowski (o pseudo-euclidiano) con un cono nulo agregado en el infinito". Es decir, el escenario es una compactación de un espacio familiar; La geometría se ocupa de las implicaciones de preservar ángulos.
En un nivel abstracto, los espacios euclidianos y pseudo-euclidianos se pueden manejar de la misma manera, excepto en el caso de la dimensión dos. El plano compacta de Minkowski bidimensional exhibe una amplia simetría conformal . Formalmente, su grupo de transformaciones conformes es infinito-dimensional. Por el contrario, el grupo de transformaciones conformes del plano euclidiano compactado es solo de 6 dimensiones.

Dos dimensiones [ editar ]

Avion Minkowski [ editar ]

El grupo conforme para la forma cuadrática de Minkowski q ( x , y ) = 2 xy en el plano es el grupo de Lie abeliano
con Lie algebra cso (1, 1) que consta de todas las matrices 2 × 2 diagonales reales .
Considere ahora el avión Minkowski, ℝ 2 equipado con la métrica
Un grupo de 1 parámetro de transformaciones conformes da lugar a un campo vectorial X con la propiedad de que la derivada de Lie de g a lo largo de X es proporcional a g . Simbólicamente,
L X g = λg   para algunos λ .
En particular, utilizando la descripción anterior del álgebra de Lie cso (1, 1) , esto implica que
  1. L X   dx = a ( x ) dx
  2. L X   dy = b ( y ) dy
para algunas funciones de valores reales a y b que dependen, respectivamente, de x e y .
A la inversa, dado cualquier par de funciones de valor real, existe un campo vectorial X que satisface 1. y 2. Por lo tanto, el álgebra de Lie de simetrías infinitesimales de la estructura conformal, el álgebra de Witt , es de dimensión infinita .
La compactación conforme del plano de Minkowski es un producto cartesiano de dos círculos S 1 × S 1 . En la cubierta universal , no hay obstrucción para integrar las simetrías infinitesimales, por lo que el grupo de transformaciones conformes es el grupo de Lie infinito-dimensional.
donde Diff ( S 1 ) es el grupo difeomorfismo del círculo. [1]
El grupo conformal CSO (1, 1) y su álgebra de Lie son de interés actual en la teoría bidimensional del campo conformal .
Ver también: álgebra de Virasoro.

Espacio euclidiano [ editar ]

Una cuadrícula de coordenadas antes de una transformación de Möbius
La misma rejilla después de una transformación de Möbius.
El conjunto de simetrías conformales de la forma cuadrática.
es el grupo GL 1 ( C ) = C × , el grupo multiplicativo de los números complejos. Su álgebra de Lie es gl 1 ( C ) = C .
Considere el plano complejo (euclidiano) equipado con la métrica
Las simetrías conformales infinitesimales satisfacen.
donde f satisface la ecuación de Cauchy-Riemann , y por lo tanto es holomorfo sobre su dominio. (Ver el álgebra de Witt .)
Las isometrías conformes de un dominio, por lo tanto, consisten en auto-mapas holomorfos. En particular, en la compactación conformal, la esfera de Riemann , las transformaciones conformes vienen dadas por las transformaciones de Möbius.
donde ad - bc es distinto de cero.

Dimensiones superiores [ editar ]

En dos dimensiones, el grupo de automorfismos conformes de un espacio puede ser bastante grande (como en el caso de la firma lorentziana) o variable (como en el caso de la firma euclidiana). La falta comparativa de rigidez del caso bidimensional con el de las dimensiones superiores se debe al hecho analítico de que los desarrollos asintóticos de los automorfismos infinitesimales de la estructura están relativamente sin restricciones. En la firma lorentziana, la libertad está en un par de funciones valiosas reales. En Euclides, la libertad está en una sola función holomórfica.
En el caso de dimensiones más altas, los desarrollos asintóticos de simetrías infinitesimales son a lo sumo polinomios cuadráticos. [2] En particular, forman un álgebra de Lie de dimensión finita. Las simetrías conformes infinitesimales puntuales de una variedad pueden integrarse de manera precisa cuando la variedad es un cierto modelo de espacio conformemente plano ( hasta tomar coberturas universales y cocientes de grupo discretos). [3]
La teoría general de la geometría conforme es similar, aunque con algunas diferencias, en los casos de firma euclidiana y pseudo-euclidiana. [4] En cualquier caso, hay varias formas de introducir el espacio modelo de geometría plana conforme. A menos que se indique lo contrario en el contexto, este artículo trata el caso de la geometría conformal euclidiana con el entendimiento de que también se aplica, mutatis mutandis , a la situación pseudo-euclidiana.

El modelo inversivo [ editar ]

El modelo inverso de geometría conformal consiste en el grupo de transformaciones locales en el espacio euclidiano E n generado por la inversión en esferas. Según el teorema de Liouville , cualquier transformación local (conforme) que preserva el ángulo es de esta forma. [5] Desde esta perspectiva, las propiedades de transformación del espacio conformal plano son las de la geometría inversa .

El modelo proyectivo [ editar ]

El modelo proyectivo identifica la esfera conformal con un cierto quadric en un espacio proyectivo . Sea q la forma cuadrática lorentziana en R n +2 definida por
En el espacio proyectivo P ( R n +2 ), sea S el lugar de q = 0 . Entonces S es el modelo proyectivo (o Möbius) de la geometría conforme. Una transformación conforme en S es una transformación lineal proyectiva de P ( R n +2 ) que deja el invariante cuadrático.
En una construcción relacionada, se considera a la S cuadrática como la esfera celeste en el infinito del cono nulo en el espacio R n +1,1 de Minkowski , que está equipado con la forma cuadrática q como arriba. El cono nulo se define por
Este es el cono afín sobre la cuádrica proyectiva S . Deje que N + sea ​​la parte futura del cono nulo (con el origen eliminado). Entonces la proyección tautológica R n +1,1 ∖ {0} → P ( R n 2 ) restringe a una proyección N + → S . Esto le da a N + la estructura de un paquete de línea de más de S . Las transformaciones conformes en S son inducidas por las transformaciones de Lorentz ortocrónicas de R n +1,1, ya que se trata de transformaciones lineales homogéneas que preservan el futuro cono nulo.

El euclidiana esfera [ editar ]

Intuitivamente, la geometría plana de una esfera es menos rígida que la geometría riemanniana de una esfera. Las simetrías conformes de una esfera son generadas por la inversión en todas sus hiperesferas . Por otro lado, las isometrías riemannianas de una esfera se generan mediante inversiones en las hiperesferas geodésicas(consulte el teorema de Cartan-Dieudonné ). La esfera euclidiana se puede mapear a la esfera conforme de una manera canónica, pero no al revés.
La esfera unitaria euclidiana es el lugar en R n +1
Esto se puede asignar al espacio Minkowski R n +1,1 al permitir
Se ve fácilmente que la imagen de la esfera bajo esta transformación es nula en el espacio de Minkowski, por lo que se encuentra en el cono N + . En consecuencia, determina una sección transversal de la línea de haz de N + → S .
Sin embargo, hubo una elección arbitraria. Si κ ( x ) es una función positiva de x = ( z , x 0 , ..., x n ) , entonces la asignación
También da un mapeo en N + . La función κ es una elección arbitraria de escala conforme .

Métricas representativas [ editar ]

Una métrica Riemannian representativa en la esfera es una métrica que es proporcional a la métrica de esfera estándar. Esto da una realización de la esfera como una variedad conforme . La métrica de esfera estándar es la restricción de la métrica euclidiana en R n +1
a la esfera
Un representante conforme de g es una métrica de la forma λ 2 g , donde λ es una función positiva en la esfera. La clase conforme de g , denotada [ g ], es la colección de todos esos representantes:
Una incrustación de la esfera euclidiana en N + , como en la sección anterior, determina una escala conforme en S . A la inversa, cualquier incrustación conforme a S viene dada por tal incrustación. Por lo tanto, el conjunto de líneas N + → S se identifica con el conjunto de escalas conformes en S : dar una sección de este conjunto equivale a especificar una métrica en la clase conforme [ g ].

Modelo métrico ambiental [ editar ]

Ver también: construcción ambiental.
Otra forma de realizar las métricas representativas es a través de un sistema de coordenadas especial en R n +1, 1 . Supongamos que la euclidiana n -sphere S lleva un sistema de coordenadas estereográfica . Consiste en el siguiente mapa de R n → S ⊂ R n +1 :
En términos de estas coordenadas estereográficas, es posible proporcionar un sistema de coordenadas en el cono nulo N + en el espacio de Minkowski. Usando la incrustación dada anteriormente, la sección métrica representativa del cono nulo es
Introduzca una nueva variable t correspondiente a las dilataciones hasta N + , de modo que el cono nulo esté coordinado por
Finalmente, sea ρ la siguiente función definitoria de N + :
En las coordenadas t , ρ , y en R n +1,1 , la métrica de Minkowski toma la forma:
donde g ij es la métrica en la esfera.
En estos términos, una sección del paquete N + consiste en una especificación del valor de la variable t = t ( y i )en función de la y i a lo largo del cono nulo ρ = 0 . Esto produce el siguiente representante de la métrica conforme en S :

El modelo Kleinian [ editar ]

Consideremos primero el caso de la geometría plana conforme en la firma euclidiana. El modelo n- dimensional es la esfera celeste del espacio lorentziano ( n + 2) R n +1,1 . Aquí el modelo es una geometría de Klein : un espacio homogéneo G / H donde G = SO ( n + 1, 1) que actúa sobre el espacio lorentziano ( n + 2) R n +1,1 y H es el grupo de isotropía de un rayo nulo fijo en elcono de luz . Así, los modelos conformemente planos son los espacios de geometría inversa . Para el pseudo-euclidiano de la firma métrica ( p , q ) , la geometría plana del modelo se define de manera análoga como el espacio homogéneo O ( p + 1, q + 1) / H , donde H se toma nuevamente como el estabilizador de una línea nula. Tenga en cuenta que tanto los espacios modelo euclidianos como los pseudo euclidianos son compactos .

Las álgebras de Lie conforme [ editar ]

Para describir los grupos y las álgebras involucradas en el espacio del modelo plano, corrija el siguiente formulario en R p +1, q +1 :
donde J es una forma cuadrática de firma ( p , q ) . Entonces G = O ( p + 1, q + 1) consta de ( n + 2) x ( n + 2)matrices estabilizador Q  : t MQM = Q . El álgebra de Lie admite una descomposición de Cartan.
dónde
Alternativamente, esta descomposición concuerda con una estructura de álgebra de Lie natural definida en R n ⊕ cso ( p , q ) ⊕ ( R n ) ∗ .
El estabilizador del rayo nulo que apunta hacia arriba el último vector de coordenadas viene dado por la subalgebra de Borel
h = g 0 ⊕ g 1 .
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)