Hoy día 27 de junio de 2011 comienza en la Universidad de Alcalá el XIV Spanish Meeting on Computational Geometry. Este congreso bianual, que concluirá el jueves día 30 de junio, está dedicado en este año 2011 al 60 cumpleaños del profesor Ferrán Hurtado:
Como podéis ver en el título del congreso, la temática del mismo es la Geometría Computacional. Bien, ¿y qué es la Geometría Computacional? Pues de eso trata este artículo. Pero no os lo voy a explicar yo, sino una auténtica especialista en este tema.
En la charla ¿Se puede «hacer» matemáticas a través de un blog? que di en la Universidad de Sevilla nuestra querida ClaraGrima me comentó que no había visto nada relacionado con Geometría Computacional, tema en la que ella es una especialista, en Gaussianos. Por ello la invité a escribir una colaboración sobre ello para que todos pudiéramos introducirnos en esta rama de las matemáticas. Y aquí está, en el mejor momento posible, aprovechando el comienzo de este importante congreso de Geometría Computacional. Vamos con ello.
¿Qué es la Geometría Computacional?
¿Qué harías si una mañana te encuentras en tu mesa, tu bandeja de entrada o tu vida la siguiente colección de problemas?
- Tu primo, Jose, quiere abrir una cadena de tiendas de videojuegos en la región, pero quiere hacerlo, lógicamente, lo mejor posible. Dado que ya existe otra cadena de la competencia, y suponiendo que la gente suele preferir la que está más cerca, porque los precios serán más o menos iguales y los juegos idénticos, Jose te pide que le sitúes sus tiendas para que el área de influencia de las mismas, sea mayor que la de la competencia.
- Por otra parte, tu suegro está terminando de montar una sala de conferencias en su nuevo hotel y necesita saber dónde colocar la pantalla para que el orador sea visto por el mayor número de asistentes. Eso sí, nada de salas rectangulares ni siquiera con planta poligonal regular, que tu suegro es muy moderno y ha diseñado algo inspirado en esto:
- Ah, y de parte de tu suegra, que a ver si pasas por la peluquería nueva para colocar los focos nuevos de forma que iluminen la sala lo mejor posible, con el menor número de focos, que los que sobren se los llevará para la playa.
- En otro mensaje, tienes los datos que te manda un colega tuyo, topógrafo y romántico, que ha estado midiendo en la sierra de su pueblo el entorno de la casa de sus abuelos, porque quiere que un arquitecto le diseñe la cubierta de su nuevo chalet en la playa, imitando la orografía de ese paisaje de infancia:
- Te llama tu madre y te dice que tu prima la que trabaja en la Diputación quiere que le digas dónde colocar el Centro de Salud nuevo de la comarca, para que todos los usuarios estén lo más cerca posible. Y que qué trabajo te cuesta, si a la cuñada de su peor enemiga, Rosa, le dijiste donde colocar la granja de pollos para no molestar a nadie y todo el mundo está contentísimo con la ubicación.
- Una ex pareja con la que tienes buenas relaciones de amistad, te pide que le ayudes con un trabajo de fotografía, calculando el menor rectángulo que encuadra a una serie de objetos que ha fotografiado y con los que quiere hacer un mosaico-collage, o almazuela:
- El Decano de tu ex-facultad te escribe para que le ayudes con la ubicación de unos repetidores de wifi en el centro, de forma que todo el edificio tenga asegurada la cobertura inalámbrica al menos por uno de los repetidores, pero de forma que el decanato esté cubierto por, al menos, 3 de los repetidores, por si se cayera uno de ellos. Eso sí, colocando los menos repetidores posibles, que está la cosa muy achuchá.
- Sí, tu actual pareja trabaja en AENA y te pide, con la nariz arrugadita, que ubiques las escaleras y cintas mecánicas en la nueva terminal de forma que minimicen el tiempo de desplazamiento de los usuarios, que van los pobres luego asfixiaditos corriendo por las cintas mecánicas:
Puede que ante tal panorama, uno pudiese tener la tentación de escapar en busca de aquel famoso Curro que se fue creo que al Caribe, pero, a la vuelta, seguiríamos con los mismos problemas sobre la mesa. Porque el Decano, tu ex y, puede que hasta tu actual pareja, buscaran otra alternativa, pero ni tu suegra ni tu madre iban a flaquear en el intento.
Entonces, para resolver de la forma más eficiente y rápida posible esta lista de tareas, lo más recomendable es buscar (y encontrar, claro) alguien con conocimientos de Geometría Computacional. Evidentemente, cada uno de estos problemas concretos se puede resolver a mano sin necesidad de implicar a un matemático en tu vida, pero las herramientas que proporcionan la Geometría Computacional para éstos y otros problemas servirán en estas situaciones y en otras diferentes.
Pero, ¿qué es la Geometría Computacional (GC) o Geometría Algorítmica?
Se trata, como dicen algunos autores, de la conjunción de la Geometría Clásica con la Informática. Partiendo de la abstracción de problemas de otras áreas (tales como diseño asistido, robótica, CAD/CAM, bases de datos o incluso biología molecular), la GC trata de desarrollar herramientas y técnicas para resolver problemas de naturaleza, principalmente, geométrica, con especial énfasis en el diseño eficiente de algoritmos y estructura de datos.
Fue bautizada en 1975 por Michael Shamos al acuñar este término por primera vez en el título de su tesis doctoral, dirigida por Franco Preparata. El libro de ambos, [Preparata], por cierto, es para muchos de los que nos dedicamos a esto uno de nuestros manuales de cabecera. No obstante, hay publicados trabajos enmarcados dentro del área muy anteriores, sólo que no se les había catalogado aún.
Para explicar de forma más gráfica cómo respira la GC, vamos a ver cómo es el camino que va desde la matemática continua abstracta al diseño de un algoritmo capaz de resolver el problema con nuestra máquina: el ordenador. Para ello, vamos a plantear un problema: el cálculo de la envolvente convexa de un conjunto finito de puntos en el plano.
Un conjunto en el plano es convexo si contiene al segmento que une a cualquier pareja de puntos contenidos en él (concepto del que ya se ha hablado por aquí):
Dado un conjunto de puntos en el plano, definimos la envolvente convexa de
, y la llamamos
, como el menor conjunto convexo que lo contiene:
Se trata, por lo tanto, de, dado un conjunto de puntos
, con
, enseñar al ordenador a calcular la envolvente convexa, como la vemos en la figura anterior.
Evidentemente, la definición no nos sirve para el diseño del algoritmo. No podemos pensar en calcular todos los conjuntos convexos que contienen a y quedarnos con el más pequeño por varias razones. La primera es ¡que hay infinitos! Por lo tanto, el primer paso será acabar con esa infinitud, esto es, tratar de utilizar otras aproximaciones que nos den, al menos, la posibilidad de elegir entre un número finito de conjuntos convexos.
Usemos nuestra intuición geométrica. Si pensamos que sobre cada punto de clavamos (no del todo) un clavo, la frontera de la
sería la forma que adoptaría una goma elástica al soltarla alrededor de ellos, ¿verdad? Pues bien, ya tenemos una primera idea para acabar con la infinitud inicial: la
(concretamente, su frontera, pero vamos a abusar un poco del lenguaje) será un polígono convexo y simple (cada dos lados o se cortan en un vértice o no se cortan) cuyos vértices son puntos de
. Habría que determinar:
- ¿Cuáles son los puntos de
que forman parte de
?
- ¿En qué orden están para definir el polígono? (Un conjunto de
puntos puede definir más de un polígono simple)
¡Tenemos un algoritmo!
Algoritmo 1:
- Considerar todos los posibles subconjuntos de
.
- Para cada subconjunto, considerar todos los posibles polígonos cerrados, simples y convexos que se pueden construir usando los puntos de dichos subconjuntos como vértices.
- Para cada uno de esos polígonos, comprobar si contienen al resto de los puntos de P en su interior.
¿Podemos darnos por satisfecho? Pues no, porque para un conjunto de puntos hay
posibles subconjuntos y eso es demasiado. A ver,
es finito, sí, pero no desde el punto de vista informático: un FLOPS de 1 Giga sólo hace
operaciones ¡en un siglo!
Un pequeño paréntesis para hablar un poco de eficiencia de los algoritmos.
Habitualmente, en Geometría Computacional, se usa para el análisis de eficiencia el modelo teórico RAM real. En este modelo, cada número real se almacena en una unidad de memoria, y las siguientes operaciones pueden realizarse con coste unitario:
- (1) acceso a la memoria;
- (2) operaciones aritméticas básicas (+, -, ×, /);
- (3) comparación de dos números reales (<, [latex]\le[/latex], =, [latex]\ne[/latex], [latex]\ge[/latex], >);
- (4) (ocasionalmente) raíces enésimas, funciones trigonométricas, la exponencial y el logaritmo.
El Algoritmo 1, analizado según este modelo, tiene un coste superior, en el peor de los casos, a (escrito en notación algorítmica es de orden
) y eso, francamente, no sirve pa ná algorítmicamente hablando. Si la unidad de medida es la millonésima de segundo (= 1 microsegundo = 1 µs) y se tienen 60 puntos, un algoritmo de orden
tardaría ¡366 siglos! Parece que tendremos que esforzarnos un poco más, ¿no?
Sigamos usando nuestra intuición geométrica:
Las aristas de son segmentos que unen parejas de puntos de
entre sí y con la propiedad de que la recta que contiene a esos segmentos dejan a los
puntos restantes en uno de los 2 semiplanos que ésta define. Ea, pues ya tenemos otro algoritmo.
Algoritmo 2:
- Considerar todas las posibles parejas de puntos de
(hay del orden de
)
- Para cada pareja, comprobar si los
puntos restantes de
están todos en el mismo semiplano de los dos que define la recta que pasa por dicha pareja de puntos.
Con este algoritmo, identificar la arista a arista, nos tomaría un tiempo de
. ¿Podemos mejorarlo? ¿No está bien ya? Pues bueno, pasar de
a
está francamente bien, pero hay que intentar bajar al máximo el tiempo de ejecución de los algoritmos, porque un algoritmo con coste de
con 10000 datos tarda más de 11 días en ejecutarse y uno
sólo tardaría 1 minuto y 40 segundos.
Pues venga, vamos a explorar aún más la geometría de este problema.
En 1973, en un trabajo de Jarvis, se presenta un algoritmo de cálculo para la con coste computacional, en el peor caso, de
. Este algoritmo se conoce como la Marcha de Jarvis o algoritmo de Gift Wrapping (envoltura de regalos).
- Calcular un punto que sepamos seguro que está en la envolvente convexa, por ejemplo, el de coordenada
más baja (esto nos tomará tiempo
, calcular el mínimo de un conjunto de
puntos). Lo llamamos
.
- Calcular el ángulo que forman los
puntos restantes con él y con la horizontal, y elegir el más pequeño (tardamos tiempo
otra vez). Ese punto será
:
- Seguiríamos este procedimiento en cada nuevo punto encontrado, hasta volver a
. Para
:
Y para
:
Puesto que pudiera ocurrir que todos los puntos de formaran parte de la
(el peor de los casos), tendríamos que calcular los
ángulos
veces, arrastrándonos a un coste en el peor de los casos de
. Qué bien, ¿no?
¿Se puede mejorar? ¿Me estoy poniendo pesada?
Bueno, es que es bastante relevante lo de reducir al máximo la complejidad de los algoritmos, porque si un tarda 1 minuto y 40 segundos en 10000 puntos, uno un pelín más barato, digamos un
tardaría para 10000 datos 0,04 segundos, y oye, en los tiempos que corren…
Vamos a intentarlo, ¿no? ¡Que no decaiga!
Haberlos, haylos, y muchos, algoritmos que calculan la de
puntos en tiempo
. El algoritmo de Graham para el cálculo de la
es uno de los más conocidos, a mí me gusta mucho.
¿Os lo cuento?
Algoritmo 4: Scan de Graham
- Calcular un punto de la
, por ejemplo, el más bajo,
.
- Ordenar angularmente los
restantes respecto de
(esto nos cuesta
, es el mejor tiempo posible para ordenar
números).
- Comenzando en
y siguiendo la lista ordenada, comprobamos cada 3 puntos si el giro por ellos es horario o antihorario, y en función de ese signo decidimos si borrar el central o no (esto nos ocupa del orden de
comprobaciones).
Vamos a verlo con un ejemplo gráfico:
Elegido , etiquetamos los demás puntos siguiendo el orden angular, tal y como se ve en la figura anterior. A continuación, comprobamos el sentido del giro de la primera terna
:
Como el giro es positivo, antihorario, avanzamos y consideramos la siguiente terna
Otra vez el giro es positivo, seguimos con :
Cuando el giro es negativo, como en la figura anterior, eliminamos el punto central de la terna, que por tanto no formará parte de la envolvente convexa, retrocedemos un punto y volvemos a empezar. Ahora :
Y continuamos de la misma forma hasta llegar otra vez a . En la siguiente animación tenéis la traza completa de este ejemplo en particular:
Al final de esta entrada os dejo unas referencia para aquellos que lo quieran ver en detalle.
Recordemos que comenzamos con infinitos conjuntos que manejar y hemos conseguido un algoritmo ¿Seguimos o paramos? ¿Cómo decidimos si seguir mejorando la complejidad o parar? Pues depende. A veces paramos porque no nos sale nada más, y en otras ocasiones, como en este caso, porque hemos llegado al óptimo. No podremos conseguir nada mejor.
¿Qué cómo lo sé? Pues porque calcular la de un conjunto de
puntos en el plano es equivalente a ordenar
números y es sabido que esto último no se puede hacer en menos tiempo.
Espero que al llegar a esta línea ya hayáis percibido el olor y el sabor de la Geometría Computacional en una primera aproximación. Pero no olvidemos los problemas del principio, que fueron los que nos trajeron aquí. Vamos a ir apagando fuegos:
- A tu primo José le dices que estudie los diagramas de Voronoi. El diagrama de Voronoi de un conjunto de puntos asigna a cada uno de ellos la región más cercana del plano.
- A tus suegros, habría que ilustrarlos un poco en la rama de la Geometría Computacional que se ocupa de problemas de Galería de Arte. Aquí podéis ver un ejemplo sencillo de vigilancia e iluminación.
- Para el topógrafo romántico, te recomiendo echarle un vistazo a la triangulación de Delaunay que optimiza los ángulos de los triángulos, proporcionando una representación lo más parecida posible a la real.
- A tu prima, la de la Diputación, dile que coloque el Centro de Salud en el centro del menor círculo que recubra a los usuarios. Para ello habrá que explicarle qué es el diámetro y hablarle del Diagrama de Voronoi de los puntos más alejados.
- Sí, fue más fácil ubicar la granja de pollos para Rosa, porque cuando el servicio es indeseable, se trata de colocarlo en el centro del mayor círculo vacío, y ése está centrado en un vértice del Diagrama de Voronoi.
- A tu ex-pareja háblale del mínimo rectángulo recubridor, le mandas la referencia o te la estudias y se la explicas tomando unas tapas, eso depende de lo que marques la x al decir ex.
- Al Decano los pones en contacto con tus suegros para que le expliquen técnicas para vigilancia e iluminación, y cuando esté al día que se ponga con los nuevos trabajos de la disciplina de ubicación de routers.
- En cuanto a tu pareja actual, te recomiendo que le des algunas referencias sobre diagramas de Voronoi dinámicos, que incluyen escaleras y cintas mecánicas.
No sé si hace falta decir a estas alturas de la entrada que me fascina la Geometría Computacional por muchas razones, pero sobre todo por el reto que supone someter mi razonamiento clásico y continuo, aprendido desde bebé en la Facultad de Matemáticas, a la dura prueba de modelar y discretizar problemas para que puedan ser resueltos por la máquina.
Como se comenta al principio de esta entrada, este año se celebra el XIV Spanish Meeting on Computational Geometry en la Universidad de Alcalá. Os lo recomiendo porque entre otros muchos grandes de la Geometría Computacional estarán Erick Demaine, gran matemático y divulgador, y el magnífico Jin Akiyama, uno de los personajes más conocidos de Japón por hacer matemáticas en TV, al que además tengo la suerte de conocer en persona (y del que nuestro querido twalmar nos habló hace un tiempo)
Y ya en plan Francisco Umbral, D.E.P., os dejo la referencia de nuestro libro Computational Geometry on Surfaces, donde se plantean y se resuelven algunos de los problemas clásicos de la Geometría Computacional pero para puntos localizados, no en el plano ni en el espacio tridemensional, sino en las superficies más simples: cilindro, toro y esfera.
Y ya termino, ahora de verdad, agradeciendo a Gaussianos la oportunidad de asomarme por su ventana para hablar de Geometría Computacional, lo que es un honor sin duda para mí que soy una novata en el mundo de los blogs. Gracias ^DiAmOnD^, te debo una soda ;).
^DiAmOnD^: Gracias a ti Clara, por introducirnos en tu mundo, la Geometría Computacional, con este magnífico artículo y por darme la oportunidad de publicarlo en Gaussianos. Acepto esa soda :).
Bibliografía:
- J. O’Rourke, Computational Geometry in C Second Edition, Cambridge University Press, 1998.
- Mark de Berg, et al., Computational Geometry: Algorithms and Applications, Springer Verlag, 1997.
- F. P. Preparata and M. I. Shamos, Computational Geometry, Springer-Verlag, 1985.
- J. O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
- J. E. Goodman and J. O’Rourke, Eds., Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton, 1997.
Actualmente, las publicaciones más relevantes en Geometría Computacional son:
- Computational Geometry Theory and Applications
- Discrete & Computational Geometry
- Journal of Computational Geometry
Esta entrada es mi primera colaboración a la Edición 2.5 del Carnaval de Matemáticas, que en esta ocasión organiza Mago Moebius.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
¡Bien por la Geometría Computacional!
Felicidades y ¡gracias Clara!.
¡Interesantísimo! Ahora a ver dónde encuentro tiempo para aprenderme algo de esto… 😛 ¡Gracias!
[…] ¿¿Geometría qué?? gaussianos.com/una-interesante-introduccion-a-la-geometri… por ClaraGrima hace 2 segundos […]
Muchas gracias, ^DiAmOnD^, estoy por Alcalá si quieres esa soda 🙂
[…] Una interesante introducción a la Geometría Computacional […]
Gracias por participar en el carnaval.
GeDiCo («Geometria Discreta i Computacional») fue la mejor optativa de la carrera i tuve la suerte de recibirla de parte del propio Ferran Hurtado.
Me lo pasé muy muy bien y tengo pendiente dedicarle algún post a temas tan interesantes como los diagramas de Voronoi.
Uffff, la longitud del texto es directamente proporcional a la cantidad de fórmulas sin traducir de LaTeX. Por otra parte, genial artículo!
Maelstrom, ¿tienes algún problema con las fórmulas en
? Yo las veo bien todas.
Información Bitacoras.com…
Valora en Bitacoras.com: No hay resumen disponible para esta anotación…
Esta pagina muestra ejemplos increibles para hacer en Geogebra. Uno es el caso de las areas de influencia, llamados Diagramas de Voronoi. La pagina en cuestion: http://geogebra.es/color_dinamico/color_dinamico.html Tiene «escaneres» de el punto de Fermat, interseccion de mediatrices, y un algo de un teorema llamado teorema de Steiner-Lehmus. Asi lo explican: «Sea el triángulo de vértices fijos A(0,0), B(1,0) y vértice libre C(x,y). Construimos el triángulo y las bisectrices. Construyamos los bisectores interiores y exteriores en cada vértice. Llamamos aquí “bisector” al segmento o distancia entre cada vértice y el punto de corte de la bisectriz -interior o exterior- que pasa… Lee más »
¡Muy interesante!
Gracias Clara
disculpen mi ignorancia, pero quisiera que alguien me explicara porque el cilindro, el toro y la esfera son superficies más simples que R² y R³.. y a qué se refiere con simple
José David, creo que mezclas conceptos de forma arbitraria y errónea. Pienso que es mejor que estudies de forma separada esos conceptos que enumeras y luego saques tus propias conclusiones:
Espacio vectorial (lo que tu llamas
,
, …
Cilíndro
Toro
Esfera
¡Animo!
Si josejuan, tienes razón, me equivoqué diciendo R² y R³, me refería a la afirmación, cito textualmente para no equivocarme otra vez:
no en el plano ni en el espacio tridemensional, sino en las superficies más simples: cilindro, toro y esfera
Sigo con mi duda
«no en el plano ni en el espacio tridemensional, sino en las superficies más simples: cilindro, toro y esfera»
no entiendo nada…
José David, esa frase no significa que estas superficies sean más simples que
o
, sino que estas superficies son algunas de las más simples de, en este caso,
.
Ahora entiendo.. Y josejuan, cite la última parte del artículo literalmente, eso es lo que dice, si no se entiende es precisamente la razón por la que preguntaba, pero ahora ya entiendo
[…] Una interesante introducción a la Geometría Computacional “Gaussianos” nos ofrece una introducción básica y motivadora de la Geometría Computacional, coincidiendo con el primer día de celebración del “XIV Spanish Meeting on Computational Geometry”, en la Universidad de Alcalá. […]
[…] the pure side, Gaussiano had an excellent guest post by Clara Grima giving an introduction to computational geometr… (translation), The Geomblog remembers the late Bob Morris and his stream algorithms and Gli […]
[…] Geometría Computacional (¿cómo? ¿que no sabéis qué es la GC?), la triangulación de un polígono P es la descomposición de dicho polígono en un conjunto de […]
¿Alguien tiene idea de que conocimientos previos se necesitan para ponerse a leer algo de geometría computacional?
Por el momento tengo conocimientos sobre teoría de grafos y programación y teoría de grafos (esto último a un nivel básico-intermedio) y cuando termine el cuatrimestre,de calculo en varias variables.
Excelente el blog,lo vengo siguiendo hace algunos años y el artículo de la eversión de la esfera fue uno de los que me hizo interesarme seriamente por la geometría (aunque el artículo en sí era sobre topología).
Saludos y felicitaciones!
Federico, pues sólo te faltaría (indispensable) algo de geometrías lineales, pero probablemente también tengas lo básico.
Obviamente no es lo mismo un algorítmo para trazar una recta o determinar la convexidad de un polígono que otro para hacer tracking a partir de imágenes.
En cualquier caso, si te gusta el tema no tienes porqué esperar [1], John Carmack está muy bien considerado entre los gurús de la informática gráfica y sólo tiene estudios medios (no terminó su primer año en la universidad).
[1]: pero mucho mejor estudiar, claro…
Genial,mil gracias josejuan.
Muy buen post.
Lo interesante de esta área de la matemática es que al parecer tiene muchas aplicaciones prácticas.
[…] bien, todo son risas y geometría computacional hasta que la profesora de tu vástago te pide que vayas a clase a contarle a los niños de 3 años […]
Vengo de amazings. Los dos artículos grandiosos.
Gracias por esta alegría mañanera de aprender sobre algo nuevo. 🙂
[…] Look-and-say y la constante de Conway ¿Es más trascendente la cantidad de números algebraicos? Calcular la derivada de una integral Una interesante introducción a la Geometría Computacional […]
[…] ¿no? Siempre digo a mis estudiantes de Geometría Computacional que si no alucinan con esto es porque no les queda sangre en el cuerpo. Me miran […]
[…] ¿no? Siempre digo a mis estudiantes de Geometría Computacional que si no alucinan con esto es porque no les queda sangre en el cuerpo. Me miran […]
[…] a sus alumnos los algoritmos de cálculo de la envolvente convexa, de los que ya nos habló en esta colaboración sobre Geometría Computacional que nos envió gustosamente hace un tiempo, utilizando a los personajes de The Big Bang Theory como […]
[…] me toca explicar qué es la Geometría Computacional, y aunque traté en su tiempo de hacerlo en esta entrada que publiqué en Gaussianos, tras una invitación del editor del mismo y he tratado de convencer de […]
[…] la que centro mi investigación y ^DiAmOnD^ se arriesgó y me invitó a contar de qué iba eso en esta colaboración, os la dejo por si os mata la […]
[…] campo de trabajo es la geometría computacional, de la cual hiciste una estupenda introducción en gaussianos. Las aplicaciones de la geometría computacional van desde el modelado de bosques mediante […]
[…] campo de trabajo es la geometría computacional, de la cual hiciste una estupenda introducción en gaussianos. Las aplicaciones de la geometría computacional van desde el modelado de bosques mediante […]
[…] bien, todo son risas y geometría computacional hasta que la profesora de tu vástago te pide que vayas a clase a contarle a los niños de 3 años […]
[…] reunió a 10 investigadores, de varias universidades y países, para trabajar en problemas de Geometría Computacional. La primera mañana del taller la dedicamos a proponer problemas en los que trabajar y el resto del […]
Interesante tema este.
¿Qué libros puedo leer para comenzar a estudiar el tema?
Hola Romeo. EL libro para empezar en Geometría Computacional es éste:
«Computational Geometry (algorithms and applications)», de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.
Es muy agradable de leer y cubre una buena variedad de temas, entre ellos los más importantes.
Un saludo.
Totalmente de acuerdo con David, también merece la pena mirar «Computational Geometry in C» de Joseph O’Rourke.
Veré si está en español, porque se muy poco de inglés como para leerlo en su idioma original.
Gracias por el dato.
[…] La envolvente convexa se puede definir como el conjunto convexo más pequeño que contiene a tus puntos. También se puede definir como la intersección de todos los conjuntos convexos que contienen a tus puntos. Para calcular de manera eficiente la envolvente convexa de un conjunto de puntos hay múltiples algoritmos, pues es uno de los problemas fundamentales en Geometría Computacional. […]
Magnífico artículo! Una introducción que provoca fascinación por la temática a cualquier lector y una exposición clara y sencilla. Lástima que en la universidad de Compostela no tengamos una optativa en la que se estudie esta rama de la matemática.
TREMENDAMENTE CURIOSO.. soy Fisico aun asi esto se puede aprender ? en que libro vienen :D:D: jajaj me han encantado los ejemplos
[…] artículo, colaboración entre Clara Grima (especialista en geometría computacional) y el redactor principal […]