Graduado en Matemáticas e Informática Universidad Politécnica de Madrid Escuela Técnica Superior de Ingenieros Informáticos TRABAJO FIN DE GRADO

Algoritmos geométricos sobre la esfera Autor: Germán Francisco Quintero Rey Director: Manuel Abellanas Oar

MADRID, JUNIO 2016

RESUMEN En este trabajo de fin de grado se realiza un estudio del cierre convexo, la triangulaci´on de Delaunay, y el diagrama de Voronoi de puntos en posici´on general situados sobre la superficie de una esfera. Adem´as se proponen algoritmos geom´etricos eficientes para el c´omputo de las estructuras mencionadas, fundamentales en el ´ambito de la Geometr´ıa Computacional, sobre la esfera. Para la realizaci´on de este estudio, se hace uso del cierre convexo tridimensional, que, al igual que en el plano, se encuentra estrechamente relacionado con el objeto del trabajo, y de operaciones esenciales de la Geometr´ıa Computacional como son el volumen signado de cuatro puntos o el vector normal de una superficie. Adicionalmente se han implementado los algoritmos propuestos en SageMath, un sistema de software matem´atico libre basado en Python, con ayuda de la herramienta Qhull para el c´alculo del cierre convexo tridimensional. La implementaci´on se ha realizado para puntos aleatorios uniformemente distribuidos sobre la esfera unidad y sus resultados se muestran en las secciones correspondientes del trabajo. Para concluir, se muestran im´agenes del globo terr´aqueo aproximado como una esfera, aplicando los algoritmos implementados a puntos que representan capitales del mundo.

i

ABSTRACT This project studies the convex hull, Delaunay triangulation and Voronoi diagram of sets of points in general position located on the surface of a sphere. Moreover, it proposes efficient geometric algorithms to compute said structures, essential in the scope of Computational Geometry, on the unit sphere. For this study, the three-dimensional convex hull is used, which, as in the case of the plane, is closely related to the object of this work. Likewise, essential operations of Computational Geometry are used, such as the signed volume of four points or the normal vector of a surface. Additionally, the algorithms proposed have been implemented in SageMath, an open-source mathematical software system based on Python, with the help of the Qhull tool for the computation of a three-dimensional convex hull. The implementation was performed for uniformly distributed random points on the unit sphere, and its results are shown in the corresponding sections of the work. To conclude, images of planet Earth considered as a sphere are shown, applying the implemented algorithms to points that represent capitals of the world.

iii

´Indice ´ 1. INTRODUCCION 1.1. Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Herramientas utilizadas: Qhull y SageMath . . . . . . . . . . . . . . . .

1 1 2 2

´ EUCLIDEA 2. POSICION

3

3. CIERRE CONVEXO 3.1. Conceptos previos . . . 3.2. Cierre convexo sobre la 3.2.1. Caso l´ımite . . 3.3. Ejemplos . . . . . . . .

. . . .

7 7 7 11 12

´ DE DELAUNAY 4. TRIANGULACION 4.1. Conceptos previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Triangulaci´on de Delaunay sobre la esfera . . . . . . . . . . . . . . . . . 4.3. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 14 16

5. DIAGRAMA DE VORONOI 5.1. Conceptos previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Diagrama de Voronoi sobre la esfera . . . . . . . . . . . . . . . . . . . . 5.3. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 20 23

6. CONCLUSIONES 6.1. Resultados del globo terr´aqueo . 6.1.1. Europa . . . . . . . . . . ´ 6.1.2. Africa . . . . . . . . . . 6.1.3. Asia . . . . . . . . . . . 6.1.4. Ocean´ıa . . . . . . . . . 6.1.5. Am´erica . . . . . . . . .

25 26 29 30 31 32 33

. . . . esfera . . . . . . . .

. . . .

. . . .

. . . . . .

7. BIBLIOGRAF´IA

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . . . .

35

v

´Indice de figuras 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31.

Triangulaci´on de Delaunay de 3 puntos (circunferencia m´axima) . Diagrama de Voronoi de 3 puntos (circunferencia m´axima) . . . . Cierre convexo de 5 puntos en posici´on eucl´ıdea . . . . . . . . . . Cierre convexo de 5 puntos en posici´on no eucl´ıdea . . . . . . . . Cierre convexo de 25 puntos en posici´on eucl´ıdea . . . . . . . . . . Cierre convexo de 25 puntos en posici´on no eucl´ıdea . . . . . . . . Triangulaci´on de Delaunay de 5 puntos en posici´on eucl´ıdea . . . Triangulaci´on de Delaunay de 25 puntos en posici´on eucl´ıdea . . . Triangulaci´on de Delaunay de 25 puntos en posici´on no eucl´ıdea . Triangulaci´on de Delaunay de 100 puntos en posici´on no eucl´ıdea Diagrama de Voronoi de 5 puntos en posici´on eucl´ıdea . . . . . . . Diagrama de Voronoi de 25 puntos en posici´on no eucl´ıdea . . . . Diagrama de Voronoi de 25 puntos en posici´on eucl´ıdea . . . . . . Diagrama de Voronoi de 100 puntos en posici´on no eucl´ıdea . . . Triangulaci´on de Delaunay de capitales (posici´on no eucl´ıdea) . . Diagrama de Voronoi de capitales (posici´on no eucl´ıdea) . . . . . Cierre convexo de capitales de Europa (posici´on eucl´ıdea) . . . . . Triangulaci´on de Delaunay de capitales de Europa . . . . . . . . . Diagrama de Voronoi de capitales de Europa . . . . . . . . . . . . ´ Cierre convexo de capitales de Africa (posici´on eucl´ıdea) . . . . . ´ Triangulaci´on de Delaunay de capitales de Africa . . . . . . . . . ´ Diagrama de Voronoi de capitales de Africa . . . . . . . . . . . . Cierre convexo de capitales de Asia (posici´on eucl´ıdea) . . . . . . Triangulaci´on de Delaunay de capitales de Asia . . . . . . . . . . Diagrama de Voronoi de capitales de Asia . . . . . . . . . . . . . Cierre convexo de capitales de Ocean´ıa (posici´on eucl´ıdea) . . . . Triangulaci´on de Delaunay de capitales de Ocean´ıa . . . . . . . . Diagrama de Voronoi de capitales de Ocean´ıa . . . . . . . . . . . Cierre convexo de capitales de Am´erica (posici´on eucl´ıdea) . . . . Triangulaci´on de Delaunay de capitales de Am´erica . . . . . . . . Diagrama de Voronoi de capitales de Am´erica . . . . . . . . . . .

vi

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 11 12 12 12 12 16 16 17 17 23 23 24 24 26 27 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33

1. 1.1.

´ INTRODUCCION Motivaci´ on

En las u ´ltimas d´ecadas, la Geometr´ıa Computacional ha surgido como una nueva disciplina en el campo de dise˜ no, desarrollo y an´alisis de algoritmos geom´etricos. Esta disciplina estudia los problemas de la Geometr´ıa desde un punto de vista computacional, desarrollando herramientas y algoritmos computacionalmente eficientes que permitan analizar y resolver dichos problemas. Algunas aplicaciones importantes de la Geometr´ıa Computacional se encuentran en los campos de la rob´otica, los sistemas de informaci´on geogr´afica, el dise˜ no gr´afico por ordenador, la investigaci´on operativa, o la arquitectura. La mayor parte del estudio de la Geometr´ıa Computacional se sit´ ua en el campo de la Geometr´ıa Eucl´ıdea, concretamente en el plano y en el espacio tridimensional. En particular, tres de las estructuras geom´etricas m´as estudiadas son: el cierre convexo, la triangulaci´on de Delaunay y el diagrama de Voronoi de una nube de puntos en el plano o en el espacio. Sin embargo, el comportamiento de estas estructuras fuera del espacio eucl´ıdeo es poco conocido, aunque existen algunas l´ıneas de investigaci´on que estudian dichas estructuras y diversos problemas geom´etricos en superficies como pueden ser el cono, el cilindro, el toro, la esfera, o incluso superficies algebraicas m´as complejas, no necesariamente en el espacio eucl´ıdeo. Por ejemplo, en sistemas de informaci´on geogr´afica se pueden considerar cuestiones geom´etricas globales que se traducen en problemas geom´etricos sobre la esfera; o en fen´omenos que presentan una configuraci´on que se muestra de manera c´ıclica, resulta interesante el estudio del cilindro. En particular, en este trabajo se estudiar´an y obtendr´an las tres estructuras geom´etricas mencionadas anteriormente sobre la superficie esf´erica para puntos en posici´on general, dadas las posibles aplicaciones que pueden tener sobre el globo terr´aqueo (que puede aproximarse a una esfera).

1

1.2.

Objetivos

Los objetivos principales de este trabajo de fin de grado son los siguientes: Estudiar el cierre convexo, la triangulaci´on de Delaunay y el diagrama de Voronoi de nubes de puntos en posici´ on general1 situados sobre la superfice esf´erica. Dise˜ nar, implementar y validar nuevos algoritmos geom´etricos sencillos y eficientes que calculen las tres estructuras mencionadas anteriormente sobre la superficie de la esfera.

1.3.

Herramientas utilizadas: Qhull y SageMath

Para la realizaci´on del trabajo ha sido fundamental el uso de las herramientas Qhull y SageMath. Qhull 2 es una librer´ıa de c´odigo abierto que calcula cierres convexos, triangulaciones de Delaunay, diagramas de Voronoi e intersecciones de semiespacios en una dimensi´on gen´erica. En particular, ha resultado de inter´es el c´alculo del cierre convexo tridimensional de una nube de puntos mediante el algoritmo Quick Hull proporcionado por esta librer´ıa, que presenta un alto rendimiento en la pr´actica. Cabe destacar que esta herramienta evita, en general, utilizar puntos coplanarios (puntos que no se encuentran en posici´on general), dado que pueden generar errores num´ericos en los algoritmos geom´etricos. Adem´as, el cierre convexo tridimensional calculado por Qhull requiere de al menos 4 puntos, por lo que el trabajo se centrar´a en conjuntos de 4 puntos o m´as, situados en posici´on general. SageMath 3 es un sistema de software matem´atico libre que se construye sobre diversos paquetes de c´odigo abierto como NumPy, SciPy o matplotlib, y permite su uso mediante un lenguaje basado en Python. Este sistema ha sido el utilizado para implementar algoritmos que calculen el cierre convexo, la triangulaci´on de Delaunay y el diagrama de Voronoi de nubes de puntos situados sobre la superficie de una esfera.

1

Un conjunto de d + 1 puntos en un espacio af´ın d-dimensional se dice que est´an en posici´on general si ning´ un hiperplano contiene m´as de d puntos; es decir, los puntos no satisfacen m´as relaciones de dependencia lineales de las necesarias. 2 Disponible en http://www.qhull.org/ 3 Disponible en http://www.sagemath.org/

2

2.

´ EUCLIDEA POSICION

Sup´ongase que se quiere calcular el cierre convexo o una triangulaci´on de una nube de puntos muy cercanos en la superficie de una esfera, de manera que su disposici´on se asemeja a la de un plano. Para este prop´osito puede resultar ser de inter´es considerar si el uso de m´etodos planares es v´alido, dado que existen algoritmos o´ptimos para el c´alculo de estas estructuras. Por ello, es necesario definir el concepto de posici´on eucl´ıdea, de manera que si un conjunto de puntos est´a en posici´on eucl´ıdea, su comportamiento es similar al comportamiento del conjunto trasladado al plano, por lo que el uso de m´etodos planares es v´alido o de f´acil adaptaci´on. Sea P un conjunto de puntos sobre la superficie esf´erica. Se dice que P se encuentra en posici´on eucl´ıdea en la esfera si est´a contenido en un hemisferio (abierto) de la misma [1]. Es posible decidir si un conjunto de puntos se encuentra o no en posici´on eucl´ıdea en tiempo lineal, como indica el siguiente lema: LEMA [5] Un conjunto est´ a en posici´ on eucl´ıdea sobre la esfera si y solo si el conjunto es linealmente separable del centro de la esfera, y esto puede llevarse a cabo en tiempo lineal. Atendiendo al lema anterior, un conjunto de puntos sobre la superficie esf´erica que se encuentre en posici´on eucl´ıdea, se puede separar del centro de la esfera mediante un plano. Ahora bien, el m´etodo de complejidad te´orica O(n) es complejo, usando criterios de separabilidad y t´ecnicas de programaci´on lineal [6]. Adem´as, en este trabajo se hace uso del c´alculo del cierre convexo tridimensional de Qhull, el cual presenta un alto rendimiento en la pr´actica. Por estos dos motivos, en vez de utilizar el m´etodo lineal, se ha dise˜ nado e implementado un algoritmo de complejidad O(nlog(n)), que emplea el cierre convexo tridimensional y el volumen signado para decidir si un conjunto de puntos sobre la esfera se encuentra en posici´on eucl´ıdea. El volumen signado de 4 puntos determina la orientaci´on y el volumen del tetraedro con dichos v´ertices. Se puede calcular mediante la f´ormula:    a x ay a z 1    1 1  bx by bz 1 signedV olume(a, b, c, d) ≡ [a − d, b − d, c − d] ≡  6 6  cx cy cz 1  dx d y dz 1 El algoritmo propuesto para determinar la posici´on eucl´ıdea o no eucl´ıdea de puntos sobre la esfera es el siguiente:

3

ALGORITMO isEuclideanPosition(P) ENTRADA: P = {p1 , p2 , ..., pn } conjunto de puntos en posici´on general sobre la esfera. n ≥ 4 SALIDA: True si est´an en posici´on eucl´ıdea. False en caso contrario. PASO 1 Calcular el cierre convexo H de P en 3D.1 PASO 2 Evaluar si el centro de la esfera se puede separar de P por un plano: Para cada tri´angulo de H, calcular los vol´ umenes signados de los tetraedros formados por el tri´angulo con el centro de la esfera, y por el tri´angulo con otro punto de H. Si en alg´ un tri´angulo los vol´ umenes signados calculados tienen distinto signo, entonces P se encuentra en posici´on eucl´ıdea, y no lo estar´ a en otro caso. (END) A continuaci´on se analizar´a la complejidad del algoritmo isEuclideanPosition: PASO 1: C´alculo del cierre convexo tridimensional. Utilizando un algoritmo o´ptimo para este c´alculo, como por ejemplo el algoritmo Quick Hull, este paso presenta una complejidad de O(nlogn). PASO 2: C´alculo de vol´ umenes signado y evaluaci´on de signos. El volumen signado es una operaci´on de orden de complejidad constante (O(1)), al igual que la evaluaci´on de signos. Este c´alculo se realiza a lo sumo h veces, siendo h el n´ umero de caras (tri´angulos) del cierre convexo tridimensional, por lo que este paso tiene una complejidad de O(h). COMPLEJIDAD TOTAL: O(nlogn)

Existe otro m´etodo similar para realizar el paso 2 del algoritmo presentado anteriormente. Ese m´etodo hace uso del test explicado en el cap´ıtulo 4 del trabajo que determina si un tri´angulo es Delaunay o no. Consiste en estudiar si los s´ımplices del cierre convexo tridimensional son Delaunay o no: si alg´ un s´ımplice no es Delaunay, entonces ese s´ımplice determina un plano que separa el centro de la esfera del conjunto de puntos, por lo que se encuentran en posici´on eucl´ıdea; y si todos son Delaunay, entonces los puntos no se encuentran en posici´on eucl´ıdea. En el caso general, este segundo m´etodo presenta una complejidad de O(n), pero para casos degenerados puede llegar a tener una complejidad de O(n2 ). 1

Se obtiene usando el algoritmo Quick Hull proporcionado por Qhull.

4

En cuanto a la probabilidad de que un conjunto de N puntos sobre la superficie esf´erica se encuentre en posici´on eucl´ıdea, se tiene el siguiente resultado de Wendel: ´ PROPOSICION [7] Si se eligen N puntos aleatoriamente con una distribuci´on uniforme, se encontrar´ an en posici´on eucl´ıdea con una probabilidad P = (N 2 − N + 2)/2N Por tanto, la probabilidad de que un n´ umero elevado de puntos se encuentre en posici´on eucl´ıdea es muy baja: Caso particular: N ≤ 3 puntos → P = 1 N = 4 puntos → P = 0,875 N = 5 puntos → P = 0,6875 N = 6 puntos → P = 0,5 N = 10 puntos → P = 0,08984375 N = 14 puntos → P = 0,01123047 N = 25 puntos → P = 0,00017941 Se puede ver que para N > 14 puntos, la probabilidad de que se encuentren en posici´on eucl´ıdea es inferior al 1 %.

5

3. 3.1.

CIERRE CONVEXO Conceptos previos

Se dice que un conjunto X ⊂ Rn es convexo si para cada par de puntos x e y de X existe un punto z ∈ X\{x, y} tal que d(x, z) + d(y, z) = d(x, y); es decir, si x, y ∈ X, el segmento que une ambos puntos debe estar contenido en X. Se llama cierre convexo de un conjunto X ⊂ Rn al conjunto CH(X), donde CH(X) es el conjunto convexo minimal que contiene a X. Tambi´en puede definirse como el conjunto de todas las combinaciones convexas de puntos en X:  CH(X) = {x ∈ Rn |x = λ1 A1 + ... + λk Ak , Ai ∈ X, λi ≥ 0, ki=1 λi = 1, 1 ≤ i ≤ k} La definici´on de cierre convexo puede generalizarse a las superficies de manera que dada una superficie S y un conjunto P ⊆ S, entonces P es convexo si para cada par de puntos de P el segmento en S que los une est´a contenido en P . Adem´as, el cierre convexo de P en S, CH(P ) es el conjunto convexo minimal que contiene a P . En el caso de la esfera, el segmento que une dos puntos de su superficie es la geod´esica de longitud m´ınima que los conecta.

3.2.

Cierre convexo sobre la esfera

A continuaci´on, se caracteriza y se calcula el cierre convexo de un conjunto P de puntos sobre la esfera. Para ello, primero se debe determinar si P se encuentra en posici´on eucl´ıdea o no: cuando P est´a en posici´on eucl´ıdea, basta adaptar un algoritmo planar; en otro caso, el cierre convexo es toda la esfera. ´ [1] El cierre convexo de cuatro puntos en posici´on no eucl´ıdea sobre PROPOSICION la esfera es toda la superficie esf´erica. Demostraci´ on: Sea P = {v1 , v2 , v3 , v4 } un conjunto de cuatro puntos en posici´on no eucl´ıdea sobre la esfera. Sea Cij el c´ırculo m´aximo definido por vi y vj , y sea γij el segmento que une dichos puntos, luego γij ⊂ Cij . Si se considera, por ejemplo y sin p´erdida de generalidad, C12 , dado que P se encuentra en posici´on no eucl´ıdea, v3 y v4 yacen en los dos hemisferios definidos por C12 . El segmento γ12 no interseca a γ34 ; si esto ocurriera, se podr´ıa considerar el hemisferio cuyo polo es el punto de intersecci´on de ambos segmentos, y se tendr´ıa que P est´a en posici´ on eucl´ıdea. Los tri´ angulos {v1 , v2 , v3 } y {v1 , v2 , v4 } deben estar contenidos en el cierre convexo, y 7

en ellos est´a incluida la geod´esica C34 \γ34 . Lo mismo sucede con la geod´esica C12 \γ12 usando los tri´angulos {v1 , v3 , v4 } y {v2 , v3 , v4 }. Adem´as, los segmentos γ12 y γ34 pertenecen al cierre convexo por definici´on. Luego los c´ırculos m´ aximos C12 y C34 est´an contenidos en el cierre convexo. Basta unir los puntos de estos dos c´ırculos por parejas con segmentos para cubrir toda la superficie de la esfera, por lo que el cierre convexo es toda la superficie esf´erica. Para el caso de puntos en posici´on eucl´ıdea, no se puede aplicar directamente un algoritmo planar, dado que se tiene una representaci´on planar de la esfera. Sin embargo, Grima y M´arquez describen una adaptaci´on para la esfera del algoritmo de Graham, el cual calcula el cierre convexo en el plano: [1] Sea P = {v1 , v2 , ..., vN } el conjunto de puntos sobre la esfera. 1. Calcular el centroide p de tres puntos no colineales cualesquiera de P 1 . Transformar las coordenadas de los puntos de P para convertir p en el polo norte de la esfera, y ordenar lexicogr´ aficamente los puntos por ´angulo polar (y distancia a p en caso de igualdad de ´angulo polar). 2. Calcular uno de los puntos m´as alejados de p. Este punto pertenece al cierre convexo. Comenzar el scan desde ´el siguiendo el orden de los puntos. 3. Examinar todas las ternas de puntos consecutivos en el orden circular: para cada terna de puntos {v1 , v2 , v3 }, estudiar si el segmento pv2 interseca al segmento v1 v3 : si pv2 ∩ v1 v3 = ∅ continuar con la siguiente terna {v2 , v3 , v4 } si pv2 ∩ v1 v3 = ∅ eliminar v2 y probar la terna {v0 , v1 , v3 } El scan termina cuando pasa por todos los puntos para llegar de nuevo al punto inicial. De una forma similar, se pueden adaptar otros algoritmos planares para calcular el cierre convexo sobre la esfera de un conjunto de puntos en posici´on eucl´ıdea.

1

Tres puntos sobre la esfera son colineales si existe un c´ırculo m´aximo sobre el cual se sit´ uan todos. El centroide de un conjunto de N puntos p1 , p2 , ..., pN es su media aritm´etica:(p1 + p2 + ... + pN )/N

8

Para este trabajo se ha dise˜ nado e implementado un algoritmo que calcula el cierre convexo de un conjunto de puntos sobre la esfera, cuya descripci´on es la siguiente: ALGORITMO sphereConvexHull(P) ENTRADA: P = {p1 , p2 , ..., pn } conjunto de puntos en posici´on general sobre la esfera. n ≥ 4 SALIDA: El cierre convexo sobre la esfera de P PASO 1: Determinar si P est´ a o no en posici´ on eucl´ıdea. Si P est´a en posici´ on eucl´ıdea, ir al paso 3. PASO 2: El cierre convexo de P sobre la esfera es toda la superficie esf´erica. (END) PASO 3: Hallar un plano1 que pase por el centro de la esfera y que deje los puntos de P en uno de los semiespacios que determina. PASO 4: Transformar las coordenadas de los puntos de P mediante un giro tal que el plano obtenido en el paso 3 se transforme en el plano z = 0 y deje a los puntos en el semiespacio z > 0. PASO 5: Proyectar2 los puntos de P desde el centro de la esfera (el origen) sobre el plano z = 1. PASO 6 Calcular el cierre convexo de los puntos proyectados con alg´ un algoritmo planar3 . Este cierre convexo nos da el cierre convexo de P sobre la esfera. (END)

1

En la implementaci´ on se utiliza el plano determinado por el tri´ angulo que separa al centro de la esfera de P detectado en el paso 1. 2 Dividiendo por la tercera coordenada de cada punto: Si p = (px , py , pz ) ∈ P , su proyecci´ on sobre el plano z = 1 es: p = (px /pz , py /pz ) N´otese que pz = 0 s´olo en el caso degenerado en el que hay tres puntos en una circunferencia m´ axima, caso que en realidad se encuentra en posici´on no eucl´ıdea. 3 En la implementaci´ on se utiliza el algoritmo Quick Hull de Qhull, por simplicidad y rendimiento.

9

A continuaci´on se analizar´a la complejidad del algoritmo sphereConvexHull : PASO 1: Determinar posici´on eucl´ıdea. Usando el algoritmo isEuclideanPosition propuesto en el cap´ıtulo anterior, este paso tiene una complejidad de O(nlog(n)). Puede reducirse esta complejidad a O(n) si se usa un algoritmo de complejidad lineal. PASO 2: El cierre convexo es P . Complejidad de O(1). PASO 3: C´alculo del plano separador. Puede obtenerse en el paso 1. Aprovechando esto, se puede decir que tiene complejidad constante. PASO 4: Transformaci´on de coordenadas mediante un giro. Se aplican operaciones b´asicas a cada uno de los puntos de P , resultando una complejidad de O(n). PASO 5: Transformaci´on de coordenadas mediante una proyecci´on. Se aplican operaciones b´asicas a cada uno de los puntos de P , resultando una complejidad de O(n). PASO 6: C´alculo del cierre convexo en el plano. Usando un algoritmo planar o´ptimo como Quick Hull o el scan de Graham este paso presenta una complejidad de O(nlogn). COMPLEJIDAD TOTAL: O(nlogn)

10

3.2.1.

Caso l´ımite

Cabe destacar el caso l´ımite en el que existen tres puntos en una circunferencia m´axima C no dispuestos en una semicircunferencia. En este caso, los puntos se encuentran en posici´on no eucl´ıdea, como se demuestra a continuaci´on: Sea P un conjunto de puntos situados sobre un hemisferio, tal que en P existen al menos 3 puntos formando una circunferencia m´axima C. Los puntos de C pertenecen al cierre convexo, y cualquier punto del semiespacio que no contiene puntos est´a contenido en una semicircunferencia m´axima con sus extremos en C, por lo que pertenecen al cierre convexo. En consecuencia el cierre convexo de P es toda la esfera. N´otese que estos puntos no se encuentran en posici´on general. Sin embargo, si no se consideran puntos adicionales, su triangulaci´on de Delaunay y diagrama de Voronoi sobre la esfera son simples (una semiesfera, y tres sectores esf´ericos, respectivamente), que se muestran en las siguientes figuras:

Figura 1: Triangulaci´on de Delaunay de 3 puntos (circunferencia m´axima)

Figura 2: Diagrama de Voronoi de 3 puntos (circunferencia m´axima)

11

3.3.

Ejemplos

Figura 3: Cierre convexo de 5 puntos en posici´on eucl´ıdea

Figura 4: Cierre convexo de 5 puntos en posici´on no eucl´ıdea

Figura 5: Cierre convexo de 25 puntos en posici´on eucl´ıdea

Figura 6: Cierre convexo de 25 puntos en posici´on no eucl´ıdea

12

4. 4.1.

´ DE DELAUNAY TRIANGULACION Conceptos previos

Sea S = {v0 , v1 , ...vk } ⊂ Rn . Se llama k-s´ımplice con v´ertices S al politopo k-dimensional σ que es el cierre convexo de S. Por ejemplo, un 1-s´ımplice es un segmento,un 2-s´ımplice es un tri´angulo, y un 3-s´ımplice es un tetraedro. Si T ⊂ S, el s´ımplice τ con v´ertices T es una cara de σ. Un complejo simplicial K es un conjunto finito de s´ımplices tal que: a) Si σ ∈ K y τ ≤ σ → τ ∈ K (Si un s´ımplice est´a en K tambi´en lo est´an todas sus caras), b) Si σ, σ’∈ K → σ ∩ σ’≤ σ y σ ∩ σ’≤ σ’ (Si dos s´ımplices de K se intersecan lo hacen por una cara com´ un). Una triangulaci´on T ⊂ Rn es una subdivisi´on de Rn en s´ımplices n-dimensionales tal que es un complejo simplicial que cubre todo el espacio. Para un conjunto de puntos S ⊂ Rn , se llama triangulaci´on de Delaunay a la triangulaci´on DT (S) tal que ning´ un punto de S se encuentra en el interior de la hiperesfera circunscrita de cualquier s´ımplice en DT (S). En el caso de la superficie esf´erica, para poder generalizar la definici´on de triangulaci´on a la esfera, se considerar´an los segmentos que unen dos puntos como los segmentos geod´esicos asociados, como se mencion´o en la secci´on del Cierre Convexo. Adem´as, se considerar´a que un c´ırculo sobre la esfera es un casquete esf´erico.

13

4.2.

Triangulaci´ on de Delaunay sobre la esfera

Para poder calcular la triangulaci´on de Delaunay de un conjunto de puntos sobre la esfera se debe primero determinar si se encuentran en posici´on eucl´ıdea dichos puntos. Si los puntos no se encuentran en posici´on eucl´ıdea, basta calcular el cierre convexo tridimensional de los puntos, y proyectar sus caras (s´ımplices) sobre la superficie de la esfera. Esto no sucede cuando los puntos est´an en posici´on eucl´ıdea, dado que generar´ıa intersecciones de aristas no v´alidas al estar incluyendo tri´angulos que no son Delaunay, que se traducir´ıa en incluir aristas que conectan puntos no consecutivos del cierre convexo esf´erico. Por lo anterior, se debe determinar si un tri´angulo es Delaunay o no, para lo cual se ha dise˜ nado e implementado el siguiente algoritmo: ALGORITMO testDelaunay(s,C) ENTRADA: s: s´ımplice (tri´angulo) a estudiar; C: cierre convexo tridimensional de n ≥ 4 puntos en posici´on general situados sobre la esfera SALIDA: True si el tri´angulo s es de Delaunay. False en caso contrario. PASO 1: Calcular el vector normal exterior del s´ımplice s. PASO 2: Calcular el producto escalar del vector normal calculado en el paso 1 por el opuesto del vector posici´on de uno de los v´ertices del tri´ angulo. Si el producto escalar es negativo, entonces el tri´angulo es de Delaunay; en caso contrario, no lo es. (END) A continuaci´on se analizar´a la complejidad del algoritmo testDelaunay: PASO 1: C´alculo del vector normal. Usando el algoritmo usado en la implementaci´on1 , este paso tiene una complejidad de O(n) para casos degenerados (muchos puntos coplanarios), pero es de complejidad O(1) en el caso general. PASO 2: Producto escalar. Complejidad de O(1). COMPLEJIDAD TOTAL: O(1) para el caso general. O(n) para casos degenerados. 1

El vector normal se calcula en tiempo constante haciendo uso del paquete NumPy. Para verificar que es el exterior, se necesita otro punto no coplanario con el s´ımplice, con cuyo vector posici´on se calcula el producto escalar con el vector normal. Si este producto escalar es positivo, entonces se cambia el signo al vector normal calculado. La b´ usqueda del punto no coplanario es lo que da lugar a la complejidad lineal en casos degenerados.

14

El algoritmo propuesto es v´alido, como se demuestra a continuaci´on: dado un tri´angulo esf´erico, el c´ırculo circunscrito es la intersecci´on del plano que pasa por los tres v´ertices con la esfera. Si el tri´angulo es exterior1 , el plano que lo contiene deja todos los puntos del mismo lado que el centro de la esfera, luego el c´ırculo circunscrito es vac´ıo, pues en el casquete esf´erico que determina no hay puntos, por lo que se trata de un tri´angulo Delaunay. Por el contrario, si es un tri´angulo interior, el plano que determina separa el centro de la esfera de los puntos y en consecuencia el c´ırculo circunscrito no es vac´ıo porque contiene a todos los puntos; luego no es un tri´angulo Delaunay.

Entonces, el c´alculo de la triangulaci´on de Delaunay sobre la esfera se realiza mediante el siguiente algoritmo: ALGORITMO sphereDelaunay(P) ENTRADA: P = {p1 , p2 , ..., pn } conjunto de puntos en posici´on general sobre la esfera. n ≥ 4 SALIDA: Triangulaci´on de Delaunay de P sobre la esfera. PASO 1: Calcular el cierre convexo tridimensional de P . PASO 2: Determinar si P est´a o no en posici´ on eucl´ıdea. Si P est´ a en posici´ on eucl´ıdea, ir al paso 4. PASO 3: Proyectar sobre tridimensional.2 (END)

la

esfera

cada

s´ımplice

del

cierre

convexo

PASO 4: Proyectar sobre la esfera los s´ımplices del cierre convexo tridimensional que sean de Delaunay. (END) N´otese que el paso 3 del algoritmo es id´entico al paso 4, ya que, en posici´on no eucl´ıdea, todos los tri´angulos son de Delaunay, por lo que no hace falta realizar esa comprobaci´on.

1

Se dice que un tri´angulo esf´erico es exterior si su vector normal exterior apunta hacia el exterior de la esfera; si apunta hacia el interior de la esfera, se dice que es interior. 2 Cada arista del tri´angulo se divide por su m´ odulo y se multiplica por el radio de la esfera.

15

A continuaci´on se analizar´a la complejidad del algoritmo sphereDelaunay: PASO 1: C´alculo del cierre convexo 3D. Usando un algoritmo o´ptimo, como lo es Quick Hull, este paso tiene una complejidad de O(nlog(n)), PASO 2: Determinar posici´on eucl´ıdea. Usando el algoritmo isEuclideanPosition, este paso tiene una complejidad de O(nlog(n)). Puede reducirse esta complejidad si se usa un algoritmo de complejidad lineal o se aprovechan los c´alculos del paso 1. PASO 3: Proyecci´on sobre la esfera. Cuesta O(1) para cada s´ımplice, resultando en una complejidad de O(h), siendo h el n´ umero de caras del cierre convexo tridimensional. PASO 4: testDelaunay y proyecci´on sobre la esfera. Para cada tri´angulo se comprueba si es Delaunay. En casos degenerados esto supondr´ıa una complejidad de O(hn), siendo h el n´ umero de caras del cierre convexo tridimensional, aunque en el caso general presentar´ıa una complejidad de O(h). La proyecci´on de todos los s´ımplices tiene una complejidad de O(h), como se vi´o en el paso 3. Por tanto, se tiene una complejidad de O(h) en el caso general para este paso. COMPLEJIDAD TOTAL: O(nlog(n)) para el caso general; O(hn), siendo h el n´ umero de caras del cierre convexo tridimensional, para casos degenerados en posici´on eucl´ıdea.

4.3.

Ejemplos

Figura 7: Triangulaci´on de Delaunay de 5 puntos en posici´on eucl´ıdea

Figura 8: Triangulaci´on de Delaunay de 25 puntos en posici´on eucl´ıdea 16

Figura 9: Triangulaci´on de Delaunay de 25 puntos en posici´on no eucl´ıdea

Figura 10: Triangulaci´on de Delaunay de 100 puntos en posici´on no eucl´ıdea

17

5. 5.1.

DIAGRAMA DE VORONOI Conceptos previos

Sea X un espacio m´etrico y sea S = {p1 , p2 , ..., pN } un conjunto de puntos de X. Se llama regi´on de Voronoi de pk al lugar geom´etrico de los puntos que distan menos o igual de pk que de cualquier otro punto de S: V or(pk ) = {q ∈ X|d(q, pk ) ≤ d(q, pj ), 1 ≤ k ≤ N, j = k} El conjunto formado por las regiones de Voronoi de todos los puntos de S, V or(S) = {V or(p1 ), ..., V or(pN )}, se denomina diagrama de Voronoi generado por S, y constituye una teselaci´on de X. Cabe destacar que el diagrama de Voronoi es la estructura dual a la triangulaci´on de Delaunay en el plano, y tambi´en lo es en el caso de la esfera: cada circuncentro de los tri´angulos de la triangulaci´on de Delaunay constituyen un v´ertice de Voronoi, y sus aristas se traducen en aristas del diagrama perpendiculares a los lados de los tri´angulos. Adem´as, aunque en el caso general los diagramas de Voronoi pueden no estar acotados, en el caso de la esfera no existen regiones de Voronoi infinitas dado que la esfera es un conjunto acotado.

19

5.2.

Diagrama de Voronoi sobre la esfera

Es posible calcular el diagrama de Voronoi esf´erico en O(nlog(n)) a partir de dos diagramas de Voronoi planares de puntos transformados por inversi´on. [9] Este m´etodo fue propuesto por Hyeon-Suk Na, Chung-Nim Lee y Otfried Cheong, y su descripci´on es la siguiente: [9] Sea P = {v1 , v2 , ..., vN } un conjunto de N puntos sobre la esfera S. 1. Elegir un punto cualquiera σ que no pertenezca a P . 2. Calcular la imagen inversa de P , W := ζσ (P ), siendo ζσ (P ) la funci´ on de inversi´on v−σ con centro σ de los puntos de P : ζσ (v) = |v−σ|2 + σ. 3. Aplicar un algoritmo planar que calcule el diagrama de Voronoi de W , V or(W ). 4. Elegir un punto q del interior del cierre convexo de W distinto de los v´ertices de W . Sea η := ζσ (q) su imagen inversa, y sea ζη la funci´ on inversi´ on con centro η.  Calcular la imagen inversa de P , W := ζη (P ), siendo ζη la funci´ on de inversi´on. 5. Aplicar un algoritmo planar que calcule el diagrama de Voronoi de W  , V or(W  ). 6. Identificar la parte de V (W  ) que yace en la regi´on del diagrama de Voronoi plano (en el plano T  , inverso de la esfera mediante ζη ) de σ que se obtendr´ıa si se a˜ nadiera el inverso de σ a W  , denotando a esta regi´on de Voronoi como ZT  (ζη (σ), W  ). Este paso puede realizarse recorriendo el diagrama y estudiando la distancia de cada v´ertice o arista a ζη (σ). 7. Corresponder V (W ) con la parte de V (W  ) calculada en el paso anterior, a trav´es −1 de las funciones φ−1 σ y φη , donde: T es el plano resultante de invertir la esfera S mediante φσ D(x) denota el disco vac´ıo m´as grande en T con centro x SD(x) denota el disco esf´erico vac´ıo m´ as grande en S con centro x + Rσ := {x ∈ S|σ ∈ extSD(x)} φσ := R+ σ → T + φη := Rη → T 

φσ (x) := y ∈ T tal que D(y) = ζσ (SD(x)) φη (x) := y ∈ T  tal que D(y) = ζη (SD(x))

¯ σ , siendo R ¯ σ := {x ∈ S|σ ∈ δSD(x)}. 8. Identificar los O(n) puntos extremos en R Estos son los ”puntos extremos en el infinito” de V (W ), y los puntos de V (W  ) que ¯ σ , agrupando los que yacen en la frontera de ZT  (ζη (σ), W  ). Ordenarlos a lo largo de R sean id´enticos, siendo el resultado el diagrama de Voronoi de P sobre la esfera. 20

Ahora bien, se puede utilizar un algoritmo m´as sencillo para obtener el diagrama de Voronoi esf´erico, teniendo en cuenta los resultados de Brown para el caso planar: calcular el diagrama de Voronoi en el plano es inmediato una vez se tiene calculada la triangulaci´on de Delaunay , dado que puede obtenerse, por dualidad, en tiempo lineal; adem´as, se puede calcular el diagrama de Voronoi planar en (O(nlogn)) usando el cierre convexo tridimensional [8]. Sobre la esfera, se presenta una situaci´on similar, con la diferencia de que en el plano existen regiones de Voronoi no acotadas mientras que en la esfera esto no es posible. Dichas regiones proceden de tri´angulos con aristas del cierre convexo, es decir, aristas que no forman parte de ning´ un otro tri´angulo de Delaunay. Esta situaci´on del plano debe ser tratada tambi´en en la esfera. Para ello, se emplea el cierre convexo tridimensional, y se estudia si sus s´ımplices son Delaunay o no. Se propone el siguiente algoritmo para calcular el diagrama de Voronoi sobre la esfera: ALGORITMO sphereVoronoi(P) ENTRADA: P = {p1 , p2 , ..., pn } conjunto de puntos en posici´on general sobre la esfera. n ≥ 4 SALIDA: Diagrama de Voronoi de P sobre la esfera. PASO 1: Calcular el cierre convexo tridimensional de P . PASO 2: Calcular el v´ertice de Voronoi asociado a cada s´ımplice del cierre convexo tridimensional: si el s´ımplice es Delaunay, el v´ertice de Voronoi es la proyecci´on sobre la esfera del circuncentro del tri´angulo; en otro caso, el v´ertice de Voronoi es la proyecci´on sobre la esfera del opuesto del circuncentro del tri´angulo. PASO 3: Calcular los segmentos (geod´esicos) que unen los v´ertices de Voronoi asociados a cada s´ımplice con los v´ertices de Voronoi asociados a sus s´ımplices vecinos. (END) N´otese que no se ha tenido que determinar si los puntos se encuentran en posici´on eucl´ıdea o no para calcular el diagrama. Sin embargo, esta comprobaci´on se podr´ıa hacer para evitar realizar el test en el caso de encontrarse en posici´on no eucl´ıdea dado que todos los tri´angulos ser´ıan de Delaunay.

21

A continuaci´on se analizar´a la complejidad del algoritmo sphereVoronoi : PASO 1: C´alculo del cierre convexo 3D. Usando un algoritmo o´ptimo, como Quick Hull, este paso tiene una complejidad de O(nlog(n)), PASO 2: C´omputo de v´ertices de Voronoi. Calcular el v´ertice de Voronoi asociado a cada s´ımplice implica estudiar si son de Delaunay o no (O(1) en el caso general, O(n) en casos degenerados) y calcular su circuncentro O(1). Esto supone una complejidad de O(h) en general, siendo h el n´ umero de s´ımplices del cierre convexo tridimensional. PASO 3: C´omputo de segmentos (aristas) de Voronoi. Calcular los segmentos geod´esicos que conectan un v´ertice de Voronoi con sus vecinos cuesta O(1), gracias a la estructura del cierre convexo tridimensional proporcionada por Qhull. Luego este paso tiene una complejidad de O(h), siendo h el n´ umero de s´ımplices del cierre convexo tridimensional. COMPLEJIDAD TOTAL: O(nlog(n)) para el caso general; O(hn) para casos degenerados, siendo h el n´ umero de s´ımplices del cierre convexo tridimensional

22

5.3.

Ejemplos

Figura 11: Diagrama de Voronoi de 5 puntos en posici´on eucl´ıdea

Figura 12: Diagrama de Voronoi de 25 puntos en posici´on no eucl´ıdea

23

Figura 13: Diagrama de Voronoi de 25 puntos en posici´on eucl´ıdea

Figura 14: Diagrama de Voronoi de 100 puntos en posici´on no eucl´ıdea

24

6.

CONCLUSIONES

En este trabajo de fin de grado se ha contribuido al estudio de las tres estructuras fundamentales de la Geometr´ıa Computacional (cierre convexo, triangulaci´on de Delaunay y diagrama de Voronoi), en el ´ambito de la superficie esf´erica. Se han mencionado m´etodos que permiten calcular dichas estructuras, y propuesto nuevos algoritmos geom´etricos basados en el cierre convexo tridimensional para realizar dichos c´alculos sobre puntos en posici´on general situados en la esfera. Adem´as, los algoritmos propuestos presentan una alta eficiencia dado que su complejidad en general es O(nlogn), inducida por el c´alculo del cierre convexo tridimensional mediante algoritmos ´optimos. Cabe destacar que los algoritmos presentados est´an limitados por precisi´on num´erica en el contexto de esta ciencia, dado que los c´alculos que se usan (vectores normales exteriores y vol´ umenes signados) pueden dar lugar a resultados que un computador puede f´acilmente manejar incorrectamente por errores num´ericos. Es por esto por lo que el trabajo se ha centrado en la posici´on general de los puntos y no ha entrado en detalle en los casos degenerados que acent´ uan dichos errores num´ericos. En la implementaci´on se han incluido modificaciones para evitar dichos errores num´ericos y aumentar su robustez algor´ıtmica, que consisten en no utilizar puntos que sean aproximadamente coplanarios a la hora de realizar los c´alculos. Este trabajo puede servir de gu´ıa para futuros estudios de dichas estructuras y sus aplicaciones sobre la esfera y, por tanto, sobre el globo terr´aqueo, como pueden ser: geolocalizaci´on, reconstrucci´on 3D, generaci´on de mallas o planificaci´on de rutas, entre otras. Para concluir, se presentan im´agenes de las estructuras de cierre convexo, triangulaci´on de Delaunay y diagrama de Voronoi sobre el globo terr´aqueo.

25

6.1.

Resultados del globo terr´ aqueo

A continuaci´on se muestran los resultados de aplicar los algoritmos geom´etricos propuestos a lo largo del trabajo a un conjunto de puntos que representan capitales del mundo, aproximando la Tierra a una esfera.1 . En verde: Londres y meridiano de Greenwich. En rojo: Madrid. En morado: ecuador. Figura 15: Triangulaci´on de Delaunay de capitales (posici´on no eucl´ıdea)

(a)

(b)

(c)

(d)

1

Los datos han sido extra´ıdos de un fichero atribuido a www.geognos.com, y cuya informaci´ on puede ser consultada en http://www.geognos.com/geo/en/countries-list/ world-capital-cities-coordinates-and-time-diffirence.html

26

(e) Polo Norte

(f) Polo Sur

Figura 16: Diagrama de Voronoi de capitales (posici´on no eucl´ıdea)

(a) Polo Norte

(b) Polo Sur

27

(c)

(d)

(e)

(f)

28

6.1.1.

Europa

En verde: Londres y meridiano de Greenwich. Punto azul en figura 17: Madrid. Punto rojo en el resto: Madrid. En morado: ecuador.

Figura 17: Cierre convexo de capitales de Europa (posici´on eucl´ıdea)

Figura 18: Triangulaci´on de Delaunay de capitales de Europa

Cierre convexo: Malta,La Valeta; Guernsey,Saint Peter Port; Azerbaiy´ an,Bak´ u; Kazajist´an,Astan´a; Svalbard,Longyearbyen; Islandia,Reikiavik; Portugal,Lisboa; Gibraltar,Gibraltar

Figura 19: Diagrama de Voronoi de capitales de Europa

29

6.1.2.

´ Africa

En verde: N´ıger y meridiano de Greenwich. Punto azul: Marruecos. En morado: ecuador.

Figura 20: Cierre convexo de capitales ´ de Africa (posici´on eucl´ıdea)

Figura 21: Triangulaci´on de Delaunay ´ de capitales de Africa

Cierre convexo: Cabo Verde,Praia; Santa Elena,Jamestown; Lesoto,Maseru; Mauricio,Puerto Louis; Seychelles,Victoria; Jordania,Am´ an; Angola,Luanda

´ Figura 22: Diagrama de Voronoi de capitales de Africa

30

6.1.3.

Asia

En verde: Jap´on y meridiano de Greenwich. Punto azul: China. En morado: ecuador.

Figura 23: Cierre convexo de capitales de Asia (posici´on eucl´ıdea)

Figura 24: Triangulaci´on de Delaunay de capitales de Asia

Cierre convexo: Timor Oriental,Dili; Jap´ on,Tokio; Rusia,Mosc´ u; Turqu´ıa,Ankara; Egipto,El Cairo; Yemen,San´a; Maldivas,Mal´e; Indonesia,Yakarta

Figura 25: Diagrama de Voronoi de capitales de Asia

31

6.1.4.

Ocean´ıa

En verde: Nueva Zelanda y meridiano de Greenwich. Punto azul: Australia. En morado: ecuador.

Figura 26: Cierre convexo de capitales de Ocean´ıa (posici´on eucl´ıdea)

Figura 27: Triangulaci´on de Delaunay de capitales de Ocean´ıa

Cierre convexo: Islas Cocos,West Island; Nueva Zelanda,Wellington; Islas Pitcairn,Adamstown; Islas Marshall, Majuro; Islas Marianas del Norte,Saip´an

Figura 28: Diagrama de Voronoi de capitales de Ocean´ıa

32

6.1.5.

Am´ erica

En verde: Canad´a y meridiano de Greenwich. Punto amarillo: Chile. Punto azul: Estados Unidos. En morado: Ecuador.

Figura 29: Cierre convexo de capitales de Am´erica (posici´on eucl´ıdea)

Figura 30: Triangulaci´on de Delaunay de capitales de Am´erica

Cierre convexo: Groenlandia,Nuuk; Brazil,Brasilia; Islas Malvinas,Stanley; M´exico,Ciudad de M´exico

Figura 31: Diagrama de Voronoi de capitales de Am´erica

33

7.

BIBLIOGRAF´IA

Referencias [1] C. Grima, A. M´arquez: “Computational Geometry on Surfaces”. Kluwer Academic Publishers, 2001. [2] M. de Berg et al.: “Computational Geometry, Algorithms and Applications”(Third Edition). Springer, 2008. [3] H. Edelsbrunner: “Algorithms in Combinatorial Geometry”. Springer, 1987. [4] F. Preparata, M. I. Shamos: “Computational Geometry: An Introduction”. Springer, 1985. [5] V. Sacrist´an: “Optimizaci´on Geom´etrica y Aplicaciones en Visibilidad”. Tesis doctoral, Universidad Polit´ecnica de Catalu˜ na, 1997. [6] N. Megiddo: “Linear-time algorithms for linear programming in R3 and related problems”. SIAM J. Comput., 12:759-776, 1983. [7] J. Wendel: “A problem in geometric probability”. Math. Scand., 2:109-111. [8] K. Brown: “Geometric transformations for fast geometric algorithms”. PhD thesis, Dept. of Computer Science, Carnegie Mellon Univ. [9] H-S. Na et al.: “Voronoi diagrams on the sphere”. Computational Geometry 23 (2002) 183–194

35

Este documento esta firmado por Firmante Fecha/Hora Emisor del Certificado Numero de Serie Metodo

CN=tfgm.fi.upm.es, OU=CCFI, O=Facultad de Informatica - UPM, C=ES Sat Jun 11 16:03:50 CEST 2016 [email protected], CN=CA Facultad de Informatica, O=Facultad de Informatica - UPM, C=ES 630 urn:adobe.com:Adobe.PPKLite:adbe.pkcs7.sha1 (Adobe Signature)