Mithesisgc-intro2.pdf

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/304782087

algoritmos geométricos sobre conjuntos finitos de puntos Thesis · May 2015 DOI: 10.13140/RG.2.1.3358.3609

CITATIONS

READS

0

446

1 author: Osmer Montilla Simon Bolívar University 1 PUBLICATION   0 CITATIONS    SEE PROFILE

Some of the authors of this publication are also working on these related projects:

construir una guia para Algebra 1 View project

desarrollo de algoritmos geometricos View project

All content following this page was uploaded by Osmer Montilla on 04 July 2016. The user has requested enhancement of the downloaded file.

República Bolivariana de Venezuela Universidad Nacional Abierta Vicerrectorado Académico Área de Matemática

Algoritmos Geométricos sobre Conjuntos Finitos de Puntos

Autor: Osmer A. Montilla Rangel Prof. Tutor: Alfredo Espejo Mayo 2015 Caracas, Venezuela

República Bolivariana de Venezuela Universidad Nacional Abierta Vicerrectorado Académico Área de Matemática

Algoritmos Geométricos sobre Conjuntos Finitos de Puntos Informe Final de Pasantía presentado por Osmer A. Montilla Rangel ante la Ilustre Universidad Nacional Abierta para obtener el Título de Licenciado en Matemática Mayo 2015 Caracas, Venezuela

A mis Padres y Amigos, en especial al Prof. Francisco Rivero

AGRADECIMIENTOS Considero que lo primero a lo que debo agradecer es a lo que representa la Totalidad, la Unidad Universal, la Energía sin límite ni medida que es la Infinita Inteligencia, Amor, Voluntad. En seguida figuran mis padres, quienes me dieron la vida. Luego están mis familiares y amigos. Agradezco a los profesores y todo el personal del Centro Local Metropolitano con quienes he convivido y que considero muy valiosos para mí: Eddy Abreu, Luis Cappellucci, Oscar Neira, Giusseppe Lanza, Efraín Salas, Yulimar, W. Sánchez, Cassandra y otros más. En el área de Biblioteca: César P., Jonathan V. En Administración: Danny Rodríguez. Además, profesores y personal del Nivel Central: Carla, Gilberto, Alfredo, Alvaro, José Gascón. Mis compañeros de carrera: Henry Peñalver, Ernesto Ruiz, Alexander Bravo, Alfredo Duarte, Javier Ovalles (primer egresado del nuevo pensum de la carrera de Matemática). Y a todos aquellos que no he nombrado pero que sin duda me han prestado su apoyo, su colaboración, en especial, la familia Angarita. Les agradezco desde lo más profundo de mi corazón.

vii

RESUMEN

Esta investigación se ubica en los Fundamentos de la GEOMETRÍA COMPUTACIONAL (GC), que une las áreas de Geometría Euclidiana, Algoritmos, Programación Estructurada, la Teoría de Grafos. Se utiliza el software de cálculo numérico SCILAB y sus módulos (SIVP y METANET), además del software GEOGEBRA para implementar prácticas y ejecutar algoritmos. La GEOMETRÍA COMPUTACIONAL es el estudio de problemas geométricos desde un punto de vista computacional. Aplicaciones importantes de la GC incluyen la Robótica, Sistemas de Información Geográfica (GIS), Diseño de Circuitos Integrados, Ingeniería Civil y Urbanismo, Visión Computacional y muchos otros. Se tratarán principalmente los conjuntos finitos de puntos, que pueden representar cualquier conjunto de objetos distribuidos en el espacio en la vida real. Sobre ellos se encontrará su ENVOLTURA o CÁPSULA CONVEXA (CC), la TRIANGULACIÓN de DELAUNAY (TD) y el DIAGRAMA de VORONOI (DV), “tres estructuras muy relacionadas entre sí y con muchas aplicaciones”. PALABRAS CLAVE: Geometría Computacional (GC), Cápsula Convexa (CC), Triangulación de Delaunay (TD), Diagrama de Voronoi (DV), Polígonos, Conjuntos Finitos de Puntos.

ABSTRACT This investigation is about the foundations of COMPUTATIONAL GEOMETRY (CG), joining Euclidean Geometry, Algorithms, Structured Programming, Graph Theory. It uses the SCILAB numeric calculation software’s basic commands and its modules SIVP and METANET. Besides, it uses GEOGEBRA software to implement practices and to run algorithms. The COMPUTATIONAL GEOMETRY is the study of geometric problems from computational point of view. GC’s significant applications includes Robotics, Geographic Information Systems (GIS), Integrated Circuit Design, Civil Engineering and Town Planning, Computational Vision, and much more. It mainly deals with finite set of points, that can perform any objects’ set distributed in space in real life. About this set it will display the algorithms that find its ENVELOPE or CONVEX CAPSULA (CC), the DELAUNAY’S TRIANGULATION (DT) and VORONOI’S DIAGRAM (VD), “three structures very related among their and with a lot of applications”. KEY WORDS: Computational Geometry (CG), Convex Capsule (CC), Delaunay’s Triangulation (DT), Voronoi’s Diagram (VD), Polygons, Finite Sets of Points.

Índice general Introducción

1

1. UBICACIÓN DEL TRABAJO

5

1.1. PROPUESTA DEL TRABAJO DE GRADO . . . . . . . . . . . .

5

1.2. MOTIVACIÓN . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3. ANTECEDENTES . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.4. PLANTEAMIENTO DEL PROBLEMA . . . . . . . . . . . . . .

10

1.4.1. Limitaciones del estudio . . . . . . . . . . . . . . . . . . .

11

1.5. OBJETIVOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.5.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . . .

11

1.5.2. Objetivos específicos . . . . . . . . . . . . . . . . . . . . .

12

1.6. METODOLOGÍA . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.6.1. MAPS (Metodología) . . . . . . . . . . . . . . . . . . . . .

13

2. PRELIMINARES

15

2.1. GEOMETRÍA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2. PUNTO Y MÉTRICA . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3. POSTULADOS DE CONEXIÓN DE LA GEOMETRÍA EUCLIDIANA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 xv

Índice general

Índice general

2.4. COMBINACION CONVEXA Y MEDIATRIZ . . . . . . . . . . .

18

2.5. POLÍGONOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.5.1. Teorema de la Curva de Jordan . . . . . . . . . . . . . . .

21

2.5.2. Diagonales y Triangulación de Polígonos . . . . . . . . . .

22

2.5.3. Polígono Convexo . . . . . . . . . . . . . . . . . . . . . . .

23

2.6. MÁQUINAS DE TURING, COMPUTABILIDAD Y ALGORITMOS 25 2.7. ANÁLISIS DE ALGORITMOS Y EFICIENCIA . . . . . . . . . .

27

2.8. EL PROCESO DE LA GEOMETRÍA COMPUTACIONAL . . .

29

2.9. PROGRAMAS, RECURSIVIDAD Y ESTRUCTURAS DE DATOS 31 2.9.1. La técnica Divide y Vencerás

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

32

2.9.2. Recursividad . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.9.3. Estructuras de Datos . . . . . . . . . . . . . . . . . . . . .

33

2.9.4. Primitivas Geométricas . . . . . . . . . . . . . . . . . . . .

33

2.10. GRAFOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3. CONVEX-HULL O CÁPSULA CONVEXA (CC)

41

3.1. NOTAS PREVIAS . . . . . . . . . . . . . . . . . . . . . . . . . .

41

3.2. EL ALGORITMO INCREMENTABLE (INCREMENTAL) . . . .

44

3.3. EL ALGORITMO DE GRAHAM . . . . . . . . . . . . . . . . . .

48

3.4. ALGORITMO (DIVIDIR Y VENCER) . . . . . . . . . . . . . . .

50

3.4.1. Parte Recursiva . . . . . . . . . . . . . . . . . . . . . . . .

52

3.5. APLICACIONES DE LA CC . . . . . . . . . . . . . . . . . . . .

53

4. TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

55

4.1. DOS ALGORITMOS DE TRIANGULACIÓN . . . . . . . . . . .

56

4.1.1. Algoritmo de División Triangular . . . . . . . . . . . . . .

56 xvi

Índice general 4.1.2. Algoritmo Incremental . . . . . . . . . . . . . . . . . . . . 4.2. TRIANGULACIONES Y FÓRMULA DE EULER

57

. . . . . . . .

58

4.3. EL GRAFO DE INTERCAMBIOS (FLIPS) . . . . . . . . . . . .

59

4.4. LA TRIANGULACIÓN DE DELAUNAY (DELONÉ) . . . . . . .

62

4.5. ALGORITMO DE INTERCAMBIO DE ARISTAS (AT3) . . . .

64

4.6. ALGORITMO AT4 (DIVIDE Y VENCE) . . . . . . . . . . . . .

67

4.7. APLICACIONES DE LA TD . . . . . . . . . . . . . . . . . . . .

68

5. DIAGRAMA DE VORONOI (DV)

73

5.1. BASES GEOMÉTRICAS . . . . . . . . . . . . . . . . . . . . . .

73

5.2. ALGORITMOS PARA CONSTRUIR EL DV . . . . . . . . . . .

82

5.3. DUALIDAD Y TD . . . . . . . . . . . . . . . . . . . . . . . . . .

83

5.4. ÍNDICE DE PROXIMIDAD . . . . . . . . . . . . . . . . . . . . .

87

5.5. TEOREMA DE LAS TEJAS . . . . . . . . . . . . . . . . . . . .

89

5.6. CÁLCULO DE PROMEDIOS EN DV . . . . . . . . . . . . . . .

89

5.7. APLICACIONES DEL DV . . . . . . . . . . . . . . . . . . . . . .

90

6. IMPLEMENTACIÓN EN SCILAB

95

6.1. INTRODUCCIÓN DE DATOS . . . . . . . . . . . . . . . . . . .

96

6.1.1. Funciones de librería Scilab . . . . . . . . . . . . . . . . .

97

6.1.2. Menú Principal [sls, sp, coo2] = crm2(ptref, coord) . . . . 103 6.1.3. Puntos aleatorios [puntr, coord] = rmt() . . . . . . . . . . 104 6.1.4. Función localizar [X, coord] = localiz() . . . . . . . . . . . 104 6.1.5. Puntos sobre imagen [X, coord] = pvori2() . . . . . . . . . 104 6.1.6. Seudocódigos y códigos fuente . . . . . . . . . . . . . . . . 105 xvii

Índice general

Índice general

6.2. LA CÁPSULA CONVEXA (CC) . . . . . . . . . . . . . . . . . . 109 6.2.1. Funciones de librería Scilab . . . . . . . . . . . . . . . . . 109 6.2.2. Función CC [nhull, ind, graf ] = capsula(coord, puntr) . . 112 6.2.3. Función dibujo dibuc(ptref, li, coord) . . . . . . . . . . . . 112 6.2.4. Seudocódigos y códigos fuente . . . . . . . . . . . . . . . . 113 6.3. PUENTES (TANGENTES) DE INTERCONEXIÓN . . . . . . . 113 6.3.1. Funciones de librería Scilab . . . . . . . . . . . . . . . . . 115 6.3.2. Función T I[ccf, ch1 , ch2 , g] = divi(ptref, coord) . . . . . . 117 6.3.3. Seudocódigos y códigos fuente . . . . . . . . . . . . . . . . 120 6.4. LA TRIANGULACIÓN DELONÉ

. . . . . . . . . . . . . . . . . 120

6.4.1. Funciones de librería Scilab . . . . . . . . . . . . . . . . . 128 6.4.2. Triangulizador [T r, ing] = trit(coord, ptref ) . . . . . . . . 130 6.4.3. Puntos-índices vecinos [ig2 , ig3 ] = sdel(ing) . . . . . . . . . 130 6.4.4. TD en Metanet graf = delon(ptref, ing) . . . . . . . . . . 131 6.4.5. Seudocódigos y códigos fuente . . . . . . . . . . . . . . . . 131 6.5. EL DIAGRAMA DE VORONOI . . . . . . . . . . . . . . . . . . 135 6.5.1. Funciones de librería Scilab . . . . . . . . . . . . . . . . . 135 6.5.2. Función dual DV [vv, ino, gdv] = dvtri(coord, ptref ) . . . . 137 6.5.3. Seudocódigos y códigos fuente . . . . . . . . . . . . . . . . 141 6.6. PRUEBA Y VERIFICACIÓN: ENTRADAS Y SALIDAS DE DATOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 6.6.1. Datos técnicos de la computadora usada . . . . . . . . . . 152 6.6.2. Menú principal . . . . . . . . . . . . . . . . . . . . . . . . 152 6.6.3. Generación de datos de entrada . . . . . . . . . . . . . . . 152 6.6.4. Entradas y Salidas de CC . . . . . . . . . . . . . . . . . . 153 xviii

Índice general 6.6.5. Entradas y Salidas de puentes (TI) . . . . . . . . . . . . . 153 6.6.6. Entradas y Salidas de Triangulación Deloné (TD) . . . . . 153 6.6.7. Entradas y Salidas de Diagrama Voronoi (DV) . . . . . . . 157 6.7. PRUEBAS SOBRE LA EFICIENCIA

. . . . . . . . . . . . . . . 157

6.7.1. Temporizador timer(); f unci´ on(); timer() . . . . . . . . . 158 6.7.2. Comparador de funciones timu(xe, ye) . . . . . . . . . . . 158 6.7.3. Comparación entre capsula, divi, trit, delon, vorg . . . . . 158 6.7.4. Función dvtri . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.8. NOTAS ACERCA DE LA IMPLEMENTACIÓN . . . . . . . . . 159 7. CONCLUSIONES Y RECOMENDACIONES

165

7.1. CONCLUSIONES . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 7.2. RECOMENDACIONES . . . . . . . . . . . . . . . . . . . . . . . 169 8. APÉNDICE

171

8.1. MODO DE ENCONTRAR LA MEDIATRIZ DE UN SEGMENTO 171 8.2. ALGORITMO QUICKSORT . . . . . . . . . . . . . . . . . . . . 171 8.3. ÁREA DE UN POLÍGONO . . . . . . . . . . . . . . . . . . . . . 173 8.4. TEOREMA DE LA COMBINACIÓN CONVEXA

. . . . . . . . 175

8.5. COMPLEJIDAD DE LA TÉCNICA “DIVIDE Y VENCE” . . . . 177 8.6. LA FÓRMULA DE EULER . . . . . . . . . . . . . . . . . . . . . 179 8.6.1. REFERENTE A LA TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS . . . . . . . . . . . . . . . . . . . . 179 8.6.2. DERIVACIÓN DE RELACIONES AFINES . . . . . . . . 180 8.6.3. EL CASO DE UN DIAGRAMA DE VORONOI (DV)

. . 181 xix

Índice general

Índice general

8.7. DEMOSTRACIÓN DE TEOREMAS EN TD . . . . . . . . . . . 182 8.7.1. LA PROPOSICIÓN 4.5.2 . . . . . . . . . . . . . . . . . . 182 8.7.2. DEMOSTRACIÓN DEL TEOREMA DEL CIRCULO VACÍO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 8.8. DEMOSTRACIÓN DE TEOREMAS DE DV . . . . . . . . . . . 184 8.8.1. TEOREMA 5.1.8

. . . . . . . . . . . . . . . . . . . . . . 184

8.8.2. LEMA 5.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 185 8.9. DESCUBRIENDO PUNTOS GENERADORES . . . . . . . . . . 186 8.10. PROBLEMAS ABIERTOS . . . . . . . . . . . . . . . . . . . . . . 189 Bibliografía

193

Nomenclatura

203

xx

Índice de algoritmos 1.

CC por Fuerza bruta . . . . . . . . . . . . . . . . . . . . . . . . . .

42

2.

Marcha de Jarvis . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.

CC Incrementable . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.

Puentes (Dividir y vencer) . . . . . . . . . . . . . . . . . . . . . . .

51

5.

Concatenación puentes . . . . . . . . . . . . . . . . . . . . . . . . .

51

6.

Puente inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

7.

División triangular (AT1) . . . . . . . . . . . . . . . . . . . . . . .

57

8.

Incremental AT2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

9.

Intercambio de aristas AT3 . . . . . . . . . . . . . . . . . . . . . .

65

10.

AT4 (Divide y vence) . . . . . . . . . . . . . . . . . . . . . . . . .

68

11.

Voronoi (Divide y vence) . . . . . . . . . . . . . . . . . . . . . . .

83

12.

Algoritmo dual DV . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

13.

función rmt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

14.

capsula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

15.

divi(TI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 xxi

ÍNDICE DE ALGORITMOS

ÍNDICE DE ALGORITMOS

16.

TD seudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

17.

DV -seudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

18.

La función principal Quicksort . . . . . . . . . . . . . . . . . . . . 173

xxii

Listados de código 6.1. rmt-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.2. pvori2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.3. capsula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.4. divi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.5. dvdut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.6. medcc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.7. dvgraf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.8. ceuler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

xxiii

Índice de figuras 2.1. Recta o línea . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2. Mediatriz de A y B . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.3. Polígonos y figuras . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.4. Teorema de Jordan para polígonos

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

22

2.5. polígono triangulado . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.6. Primitiva CCW . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.7. Primitiva Ccírculo

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

35

3.1. CC en diferentes etapas hasta k + 1 . . . . . . . . . . . . . . . . .

45

3.2. línea L tangente a P . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.3. Tangentes a Hk . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

3.4. Aristas visibles e invisibles . . . . . . . . . . . . . . . . . . . . . .

47

3.5. Ordenación según ángulos . . . . . . . . . . . . . . . . . . . . . .

49

3.6. Descarte de giros a derecha

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

49

3.7. Efecto del algoritmo Puentes . . . . . . . . . . . . . . . . . . . . .

50

4.1. Triangulación maximal . . . . . . . . . . . . . . . . . . . . . . . .

56

4.2. Grafo Flips (GF (S)) para 6 puntos . . . . . . . . . . . . . . . . .

60

4.3. Estrella de pn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61 xxv

Índice de figuras

Índice de figuras

4.4. Interpolación de alturas . . . . . . . . . . . . . . . . . . . . . . .

63

4.5. Teorema de Thales . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.6. 3 posiciones de D . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.7. Triangulación de terreno . . . . . . . . . . . . . . . . . . . . . . .

69

4.8. Escultura de Gego . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.1. Vórtices de Descartes . . . . . . . . . . . . . . . . . . . . . . . . .

74

5.2. Discos alrededor de pi

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

75

5.3. Salida gráfica de DV . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.4. Hiperplanos de p y q . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.5. Bisectores entre p, q, r

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

78

5.6. Intersección de bisectores . . . . . . . . . . . . . . . . . . . . . . .

79

5.7. Teorema de la Arista . . . . . . . . . . . . . . . . . . . . . . . . .

80

5.8. Vértice al infinito . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

5.9. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

5.10. Dual del DV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.11. Puntos repartidos en una región . . . . . . . . . . . . . . . . . . .

88

5.12. Puntos relocalizados . . . . . . . . . . . . . . . . . . . . . . . . .

88

5.13. DV en 3D con 4 sitios . . . . . . . . . . . . . . . . . . . . . . . .

90

5.14. Fractal de Shirriff, Anisóptera, Gaudí y ventana . . . . . . . . . .

93

6.1. Funciones para la entrada . . . . . . . . . . . . . . . . . . . . . .

96

6.2. Símbolos en Scilab . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.3. menú principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.4. localiz1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.5. localiz2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 xxvi

Índice de figuras 6.6. funciones CC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.8. divi-funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.7. dibuc código fuente . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.9. conver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.10. puen2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.11. inic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.12. desci1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.13. prueb2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.14. TD funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.15. códigos trit, sdel . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.16. delon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6.17. DV- funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.18. DV dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.19. tresp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.20. vervo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.21. voroc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.22. vorg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.23. crm2-menu principal . . . . . . . . . . . . . . . . . . . . . . . . . 150 6.24. crm2-final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.25. menú . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 6.26. 20 puntos con rmt, localiz, pvori2 . . . . . . . . . . . . . . . . . 154 6.27. CC Salidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.28. TI-salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.29. TD Scilab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.30. TD- consola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 xxvii

Índice de figuras

Índice de figuras

6.31. DV- salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 6.32. DV- consola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6.33. comparación de 5 funciones . . . . . . . . . . . . . . . . . . . . . 164 6.34. tiempo versus N° puntos en dvtri . . . . . . . . . . . . . . . . . . 164 7.1. Diagonales en un cuadrilátero . . . . . . . . . . . . . . . . . . . . 168 7.2. TD y DV en un disco de Poincaré . . . . . . . . . . . . . . . . . . 170 8.1. Triangulo con sus vértices . . . . . . . . . . . . . . . . . . . . . . 174 8.2. Paso inductivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 8.3. Verificación de aristas legales . . . . . . . . . . . . . . . . . . . . . 182 8.4. Otro Criterio de legalidad . . . . . . . . . . . . . . . . . . . . . . 183 8.5. Propiedad del circulo vacío . . . . . . . . . . . . . . . . . . . . . . 184 8.6. Demostración aristas . . . . . . . . . . . . . . . . . . . . . . . . . 185 8.7. Cuerdas1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 8.8. cuerdas cruzándose . . . . . . . . . . . . . . . . . . . . . . . . . . 186 8.9. DV sin puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

xxviii

INTRODUCCIÓN “Escuchad en vuestro interior y fijaos en lo infinito del espacio y del tiempo. Allí resuena el canto de los astros, la voz de los números, la armonía de las esferas” luque alvarez, j. La Geometría Computacional (GC) es un campo que ofrece muchas soluciones a diferentes problemas de la vida real. Es interesante debido a la combinación de dos factores: el primero son las conexiones fuertes con la matemática clásica y la ciencia computacional y el segundo son las muchas aplicaciones que tiene en varias áreas. Abordar el estudio de la Geometría implica ejercitar la facultad de razonar, visualizar y con ello resolver problemas de diseño e ingeniería. Luego con la era actual de la computación e internet, nos viene la inquietud de representar esta Geometría con estructuras de datos útiles. De allí surge el término “Algoritmos Geométricos”, que significa el uso de la Geometría para realizar algoritmos y resolver problemas. Existen paquetes de libre descarga como Geogebra y el Scilab, que son herramientas poderosas para el aprendizaje individual. Lo que nos motiva es el estudio de los conjuntos finitos de puntos en tres aspectos a saber: encontrar una estructura poligonal convexa que los encierre a ellos (capítulo III), encontrar la mejor manera 1

de modelar una superficie (capítulo IV) y encontrar la estructura que nos indique el sitio más cercano para un punto de prueba dado ubicado en el plano (capítulo V). Comenzamos definiendo en el primer capítulo lo que se quiere lograr con este primer trabajo, en el que todavía hay mucho por recorrer. Se hace la propuesta, se describe la motivación, antecedentes del trabajo, planteamiento del problema, objetivos y metodología. El capítulo II es un pequeño compendio de algunos de los conocimientos previos a tomar en cuenta para la GC. Recordaremos aquellas definiciones y teoremas de la Geometría Euclidiana y poco a poco nos adentraremos en los conceptos de computabilidad, análisis de algoritmos y grafos. Sin embargo se requieren conocimientos previos de programación para realizar por sí mismo las implementaciones. Ya mencionamos que en el capítulo III hablamos sobre la primera de las estructuras. Se darán tres algoritmos (Incrementable, de Graham y Divide&vence) y se explicará con detalles. Hay una construcción interesante llamada Puentes de Interconexión, que es un paso recursivo de un algoritmo que se tratará allí. Finalmente algunas aplicaciones de la CC. El capítulo IV da cuatro algoritmos, se explican las triangulaciones, junto a la Fórmula de Euler y el Grafo de Flips. Finalmente la definición de la Triangulación de Deloné (TD) y algunas aplicaciones. El capítulo V propone un algoritmo para el Diagrama de Voronoi (DV), se presentan conceptos geométricos, la noción de dualidad, el índice de proximidad, el teorema de las tejas, cálculo de promedios y algunas aplicaciones. La parte práctica del trabajo está en un CD con los archivos del Scilab (Capítulo 2

VI). En este capítulo se explican muchos comandos básicos del Scilab y los códigos fuente implementados allí. Se comienza con algoritmos de introducción de datos. Se usan funciones de librería y el módulo Metanet para realizar la CC, los Puentes de Interconexión y TD. Para el DV se realizan funciones para encontrar el dual del TD. Se verifican las entradas y salidas en la consola y las ventanas gráficas. Se verifica la eficiencia con la función timer(). El capítulo VII es una reflexión sobre lo desarrollado hasta ahora. Se dan las conclusiones y recomendaciones. Luego el Apéndice trata algunas demostraciones esenciales del texto. Se incluyen cálculos relacionados con la búsqueda de la mediatriz, el algoritmo Quicksort, área de un polígono convexo, una demostración de la CC, un cálculo de complejidad en el tiempo, la Fórmula de Euler, demostraciones de teoremas del capítulo IV y V y un esbozo de una solución a un problema abierto. Hay allí problemas abiertos de interesante resolución. La transcripción se hizo en Lyx, que considero es una buena plataforma para redactar documentos con calidad Latex (ver [27, 72]). Como guía para no confundirse entre tantas referencias, las que aparecen en formato ].].].] se buscan a partir del número de capítulo en el primer numeral, luego la sección y así sucesivamente. Las que aparecen entre corchetes []] son referencias a material bibliográfico. Las que aparecen entre paréntesis (].]) son ecuaciones. Las demás referencias están precedidas por abreviaturas (Fig., sec.) por lo que se sabe qué significan. Se espera que este trabajo sirva de introducción a muchos temas relacionados, y que se siga expandiendo el gusto de hacer muchas matemáticas computacionales de gran valor. ¡Es la tendencia de estos tiempos!

3

1 UBICACIÓN DEL TRABAJO 1.1.

PROPUESTA DEL TRABAJO DE GRADO

Esta investigación se ubica en los fundamentos de la partición de una región por medio de un conjunto dado de puntos. Este tema es desarrollado por la Geometría Computacional (GC), la cual estudia la complejidad de los algoritmos que son usados para resolver problemas geométricos. La GC une las áreas de la Geometría Euclidiana principalmente, la teoría de Grafos y la teoría de Algoritmos. Se incluye información acerca de comandos y estructuras básicas del software Scilab y sus módulos SIVP y Metanet. Se utiliza Scilab, Geogebra y Maple® a la hora de implementar prácticas y ejecutar algoritmos. La GC tiene diversas aplicaciones y grupos que se reúnen en Simposios y Eventos en varios países del mundo1 . En particular se estudiarán los algoritmos que hallan la Envoltura o Cápsula Convexa (CC), la Triangulación de Delaunay (Deloné, TD) y el Diagrama de Voronoi (DV), “tres estructuras muy relacionadas entre sí y con muchas aplicaciones”.

1

Ver por ejemplo los eventos http://www.dais.is.tohoku.ac.jp/~socg2014/ y http:// www.win.tue.nl/SoCG2015/.

5

UBICACIÓN DEL TRABAJO

1.2.

MOTIVACIÓN

La computación ya forma parte de la vida del ciudadano común. Existen grandes oportunidades de aprendizaje en la red de Internet y hay grandes ventajas para la comunicación e intercambio de ideas y oportunidades de desarrollo científico y tecnológico. De manera que la Geometría con regla y compás sube un mayor nivel. Se suma una nueva herramienta que potencia el estudio de la resolución de problemas geométricos, esta herramienta es la computadora. Ahora hablamos de Geometría Computacional. La esencia de la GC es un conjunto de técnicas para el diseño y análisis de algoritmos geométricos eficientes. Estos algoritmos frecuentemente operan y son guiados por un conjunto de Estructuras de Datos que poseen todos los sistemas actualmente. Aplicaciones importantes de la GC incluyen la robótica (planificación del movimiento y problemas de visibilidad), sistemas de información geográfica (GIS) (localización y búsqueda, planificación de rutas), diseño de circuitos integrados, ingeniería civil y urbanismo, diseño asistido por computadora (generación de mallas), visión computacional (reconstrucción 3D). No sólo estas áreas han sido fuente de problemas e inspiración para la GC sino, inversamente, varias técnicas que provienen de la GC han sido útiles en la práctica. La complejidad computacional es central para la GC, con gran significado práctico si los algoritmos son usados para muy grandes conjuntos de datos que contienen decenas o cientos de millones de puntos. Para tales conjuntos, la diferencia entre O(n2 ) y O(nlog(n)) puede ser la diferencia entre días y segundos de computación (ver Preliminares 2.7.1). 6

1.3 ANTECEDENTES Se tratarán los conjuntos finitos de puntos, que pueden representar cualquier conjunto de objetos distribuidos en el espacio en la vida real. Sobre ellos se realizarán los algoritmos para encontrar su Envoltura o Cápsula Convexa (CC), la Triangulación de Deloné (TD) y el Diagrama de Voronoi (DV), tres estructuras muy relacionadas entre sí y con muchas aplicaciones, como bien dice Abellanas en su artículo [4]. La profundización del estudio de la GC podrá ser de mucho provecho a la hora de crear o mejorar la productividad y la eficiencia tanto en el sector público como privado que requiera el auxilio de la Geometría en sus operaciones.

1.3.

ANTECEDENTES

Mientras los algoritmos formales han existido por milenios (el algoritmo de Euclides2 para determinar el máximo común divisor de dos números es aun usado en computación), después de Euclides, el análisis de algoritmos enfrentó casi 2000 años de decadencia. En 1900, en el 2° Congreso Internacional de Matemáticas, el décimo problema de los 23 que enunció Hilbert era prácticamente encontrar un algoritmo que nos indique para cualquier ecuación diofántica, si tiene o no al menos una solución entera. Lo que se necesitaba era una definición formal de algoritmo. En el siglo XVII Leibniz imaginó un lenguaje universal que permitiría a una persona reducir pruebas matemáticas a simples cálculos. Entonces, durante el siglo XIX lógicos como Babbage, Boole, Frege y Peano intentaron formalizar el razonamiento matemáti2

Ver Elementos [30], libros 7,8,9. Según parece, estos libros son atribuidos a la escuela Pitagórica.

7

UBICACIÓN DEL TRABAJO co. Finalmente, entre 1931 y 1936 Gödel, Church, y Stephen Kleene introdujeron la noción de funciones “recursivas3 ”. Una vez que la noción de funciones “recursivas” habían sido formuladas, Church afirmó que la clase de funciones recursivas era exactamente la misma que la clase de funciones “efectivamente calculables”. Esto no pudo ser demostrado y se llamó la “Tesis de Church”. Una de las más fuertes piezas de evidencia para la Tesis de Church es que en 1936 Turing4 encontró una manera diferente de formalizar la noción de algoritmo, el cual demostró que era equivalente, es decir, toda función computable en su nuevo sentido también es recursiva y viceversa. Casi todos los matemáticos se pondrían de acuerdo de que existe una diferencia notable entre demostraciones constructivas y demostraciones indirectas de existencia, una diferencia que ha llegado a ser más clara con el surgimiento de la ciencia de la computación. En cuanto a la Geometría, el crecimiento del análisis real en el siglo XIX tuvo un profundo efecto en la primera, resultando en la formal abstracción de conceptos que habían sido previamente intuitivos. Dos de tales desarrollos, Geometría Métrica y la Teoría de la Convexidad, proveen herramientas matemáticas principales que ayudan en el diseño de algoritmos rápidos. La frase “Computational Geometry” había sido usada antes: 1. Como modelaje geométrico por medio de curvas spline y superficies, un tópico que está más cerca en espíritu al análisis numérico que a la geometría, Esta palabra tiene un significado diferente al de hoy en día. Significaba aquellas funciones que pueden ser calculadas por medio de un algoritmo. Sobre recursividad se hablará en (sec. 2.9.2) 4 Se recomienda ampliamente la película Código Enigma (The Imitation Game) (2014), sobre la vida de Turing, basada en el libro de Andrew Hodges. 3

8

1.3 ANTECEDENTES ha sido tratada por expertos como Bézier, Forrest y Riesenfeld. 2. En un libro elegante y fascinante titulado “Perceptrons”, Minsky y Papert (1969) tratan con la complejidad de predicados que reconocen ciertas propiedades geométricas, tales como la convexidad. 3. Software gráfico, editores geométricos, software de control numérico para soporte de maquinarias, programas para trazadores (plotters) gráficos, sistemas que dibujan mapas y software para diseño arquitectónico e ingeniería civil (ver [61]).

La “Geometría Computacional” como la disciplina que conocemos aparece en un documento hecho por M.I. Shamos: Problemas en Geometría Computacional, no publicado, en 1975. Ahora existen conferencias anuales, revistas5 , libros y una vigorosa comunidad de investigadores con intereses comunes. Hay buenas lecturas sobre la GC en [33, 45, 66, 1]. La investigación en GC ha fomentado el cálculo correcto y robusto de primitivas geométricas basado en fundamentos matemáticos sólidos (ver sec. 2.9.4). Como actores principales de los conceptos básicos que veremos tenemos a Ronald Graham (1972), Boris Delone (1924) y Georgy Voronoi (1908), quienes dieron los primeros resultados de sus investigaciones en la geometría relativa al análisis de conjuntos finitos de puntos. Vemos una ligera descripción biográfica según O’Connor y Robertson en [57, 56, 55], respectivamente, además de otras vidas que contribuyeron al desarrollo actual. 5

Revistas como www.journals.elsevier.com/computational-geometry/, www. worldscientific.com/worldscinet/ijcga y www.link.springer.com/journal/454. Además, está www.jocg.org

9

UBICACIÓN DEL TRABAJO Actores de los que se ha recopilado información están los españoles Manuel Abellanas, Clara Grima, David Orden, Belén Palop, Vera Sacristán, Pedro Reyes, J. Priego, M. Porres, R. Guerequeta, A. Vallecillo, de México Eduardo Rodríguez, de Chile Pablo Barceló, Pedro Valenzuela, de USA y otros países Franco Preparata, Jianer Chen, Joseph O’rourke, Satyan Devadoss, Mark de Berg, M. Van Kreveld, Otfried Cheong, P. Cignoni, Christopher Gold, Leonidas Guibas, Craig Kaplan, Nandy Subhas, A. Kumar, M. Sharir, Ken Shirriff, Herbert Wilf, M. Bern, D. Eppstein, Timothy Chan, A. Dumitrescu, O. Goldreich, A. Wigderson, C. Lawson, I. Pinelis, A. Sheffer, R. Seidel, y otros. En Venezuela F. Rivero, F. Tovar, J. Lockiby, J. Ruiz, L. León, M. Rosas. Actualmente se estudian redes geométricas, topología computacional, geometría estocástica y algoritmos de generación aleatoria entre muchos otros aspectos de la GC.

1.4.

PLANTEAMIENTO DEL PROBLEMA

Es necesario hacer una revisión del desarrollo y evaluación de algoritmos que realizan la Cápsula o Cierre Convexo (CC), la Triangulación de Deloné (TD) y el Diagrama de Voronoi (DV), todos sobre un conjunto finito de puntos determinado, sobre el plano, el espacio 3D y con los entornos matemáticos Scilab y Geogebra, para ofrecer soluciones a la sociedad. Los conjuntos finitos de puntos pueden representar servicios públicos (drenajes y surtidores de aguas, casetas telefónicas, transformadores de corriente alterna, abastos, oficinas administrativas, bombas de gasolina, etc.) o privados, cadenas de establecimientos, personas, lugares de interés turístico, emisoras de radio o 10

1.5 OBJETIVOS radio-bases de telecomunicaciones, etc. De allí la utilidad del tema. Para la realización de este proyecto se hará una investigación documental, buscando artículos que traten el tema de la Geometría Computacional, en particular las tres estructuras antes mencionadas. Luego, revisar algoritmos en seudocódigo que puedan dar como salida estas construcciones anteriores en el plano discreto. En seguida, realizar una implementación en lenguaje Scilab. Luego verificar la corrección comparando resultados con Geogebra, que ya tiene instalados estos algoritmos. Se usa Scilab, por ser un software numérico muy eficiente, es de fuente abierta, puede implementarse de una manera sencilla y puede proporcionar resultados que no aparecen en Geogebra.

1.4.1.

Limitaciones del estudio

Nos restringimos a la representación de los diagramas en Geometría Euclidiana y bajo la plataforma Scilab, con auxilio de Geogebra para ejemplificar.

1.5.

OBJETIVOS

1.5.1.

Objetivo general

Estudiar los conceptos teóricos y algorítmicos que generan la Cápsula Convexa, la Triangulación de Deloné y el Diagrama de Voronoi, a partir de conjuntos finitos de puntos mediante el software Scilab.

11

UBICACIÓN DEL TRABAJO

1.5.2.

Objetivos específicos

1. Describir los fundamentos de la Geometría Computacional en general. 2. Describir estructuras de datos usados en la situación de estudio (estructuras centradas en el software Scilab). 3. Analizar algoritmos asociados a la Cápsula Convexa. 4. Analizar algoritmos asociados a la Triangulación de Deloné. 5. Analizar algoritmos asociados al Diagrama de Voronoi. 6. Implementar estos algoritmos geométricos con el software Scilab.

1.6.

METODOLOGÍA

La investigación es Mixta, ya que se realizará en dos grandes fases:

Diseño de investigación documental, dado que se basa en la búsqueda, recuperación, análisis, crítica e interpretación de datos obtenidos y registrados por otros investigadores en fuentes documentales impresas, audiovisuales o electrónicas (Fidias [6]). Se hizo una recopilación para seleccionar 81 fuentes (escritas en un archivo .bib), la mayoría localizada en Internet6 y de libre descarga. Se verificó en lo posible la seriedad de cada documento. La Bibliografía fue generada automáticamente usando el archivo de estilo IEEEtranS. 6

12

Si no aparece en Internet, puede enviarme un email a osmer montilla

1.6 METODOLOGÍA Diseño experimental, dado que se somete a un conjunto de puntos ubicados en un plano que simula la realidad (variables independientes) y mediante el proceso algorítmico (tratamiento utilizado), se observan los efectos (los tres diagramas o estructuras) que se producen en el plano o pantalla de la computadora (variables dependientes). En este diseño, la hipótesis de trabajo es precisamente el algoritmo usado para representar la estructura que se espera. La población la constituye el tamaño de la imagen en píxeles, la muestra son los distintos conjuntos de puntos de estudio, los instrumentos de medición son las salidas numéricas y en ventanas de gráfico, funciones internas del Scilab y el software Geogebra y Maple para verificación. Para realizar algoritmos sirvió como guía la metodología MAPS.

1.6.1.

MAPS (Metodología)

Son siglas inglesas que significan METODOLOGÍA PARA SOLVENTAR PROBLEMAS ALGORÍTMICOS, en español, y es la sucesión de las siguientes etapas: diálogo, especificaciones, subdivisión, definición de abstracciones, codificación, prueba y verificación, presentación. Ver Tucker[77] para más detalles.

13

2 PRELIMINARES 2.1.

GEOMETRÍA

Geometría1 (del griego ge¯o, “tierra”; metrein, “medir”), rama de las matemáticas que se ocupa de las propiedades del espacio que nos rodea. El matemático griego Euclides (300 a.C.) fue el autor de Los Elementos, un cuerpo deductivo de conocimientos altamente organizado, vigente hasta nuestros días. El filósofo y matemático francés René Descartes, cuyo tratado “La Geometría”2 , publicado en 1637, hizo época. Este trabajo fraguó una conexión entre la Geometría y el Álgebra al demostrar cómo aplicar los métodos de una disciplina en la otra. Éste es el fundamento de la geometría analítica, en la que las figuras se representan mediante expresiones algebraicas, sujeto subyacente en la mayor parte de la Geometría moderna. La Geometría analítica fue desarrollada en el siglo XVIII especialmente por Euler. Hacia el fin de éste siglo, el análisis fue otra vez aplicado a la Geometría. Por ejemplo, la contribución de Monge puede ser reconocida como un precursor de la geometría diferencial. El Axioma de las Paralelas de Euclides ha sido un objeto de critica desde los Recordando lo visto en Geometría (754) en la carrera Matemática de la UNA, curso diseñado por el Prof. Gascón. 2 La Géométrie, Editor: A. Hermann (2008), disponible en www.gutenberg.org 1

15

2.2 PUNTO Y MÉTRICA tiempos antiguos. En el siglo XIX, negando la validez a priori de la Geometría Euclidiana, Bolyai y Lobachevskii formularon la geometría no-euclidiana, cuya consistencia lógica fue demostrada mediante modelos construidos en la misma Geometría Euclidiana. En la Geometría Analítica, espacios físicos y planos como los conocemos, son representados como espacios euclidianos bidimensionales o tridimensionales (E 2 , E 3 respectivamente). Es fácil generalizar estos espacios al espacio euclidiano n-dimensional E n . Riemann inició otra dirección de la investigación geométrica cuando descubre las variedades n-dimensionales, abriendo el campo de la Geometría Diferencial moderna. La reexaminación del sistema de axiomas de los Elementos de Euclides condujo a los fundamentos de la Geometría de Hilbert. Otra rama de la Geometría es la topología, la cual se ha desarrollado desde el fin del siglo XIX hasta ahora. La geometría métrica es el cuerpo de aquellas proposiciones que tratan de las magnitudes de las figuras, invariantes sólo bajo la clase de los movimientos rígidos. La geometría discreta y la geometría combinatoria tratan las propiedades combinatorias de colecciones discretas de objetos geométricos.

2.2.

PUNTO Y MÉTRICA

Un punto es aquel que no tiene partes, es un concepto indefinido. Es interpretado aquí como un vector de 2-componentes aplicados al origen de E 2 . Por E 2 denotamos el espacio euclidiano 2-dimensional, esto es, el espacio de las duplas 16

PRELIMINARES (x11 , x12 ), (x21 , x22 ), ...(xn1 , xn2 ) de números de punto flotante3 en Q × Q con una métrica dada por d, la cual es una función binaria, simétrica, no-negativa (siempre d ≥ 0), definida por d(x, y) = (y1 − x1 )2 + (y2 − x2 ) 2 h

i1/2

(2.1)

Para dos puntos (x1 , x2 ) y (y1 , y2 ), que satisfacen la Desigualdad del Triángulo d(x, y) + d(y, z) ≥ d(x, z)

(2.2)

Además, se extiende naturalmente el concepto al espacio euclidiano 3-dimensional E 3 . Decimos números de punto flotante (sin ser densos) ya que estamos sobre una plataforma computacional, y en ella sólo podemos concebir números de esta forma. Los objetos considerados en este proyecto son conjuntos finitos de puntos en un espacio euclidiano E 2 , a veces exploraremos puntos en E 3 . La topología que se puede usar en estos conjuntos es la Topología Digital o Computacional, que está siendo desarrollada aún.

2.3.

POSTULADOS DE CONEXIÓN DE LA GEOMETRÍA EUCLIDIANA

Recordaremos un poco aspectos de este tema (los daremos como “Proposiciones”): Proposición 2.3.1. Una recta es un conjunto de puntos que contiene al menos 2 puntos distintos. 3

Es un conjunto finito y es un subconjunto de Q.

17

2.4 COMBINACION CONVEXA Y MEDIATRIZ

Figura 2.1: Recta o línea Proposición 2.3.2. Si p y q son puntos hay una y sólo una recta que los contiene a ambos (Fig. 2.1). Definición 2.3.3. Se dice que los puntos de un conjunto están alineados si y sólo si hay una recta que los contiene a todos. Proposición 2.3.4. Plano es un conjunto de puntos que contiene, por lo menos, 3 puntos no-alineados. Proposición 2.3.5. Si p, q, r son tres puntos no-alineados, hay un solo plano que los contiene a todos ellos. Proposición 2.3.6. Si dos puntos de una recta están en un plano, todos los puntos de esta recta están en él. Definición 2.3.7. Se dice que los puntos de un conjunto son coplanares si y sólo si hay un plano que los contiene a todos ellos.

2.4.

COMBINACION CONVEXA Y MEDIATRIZ

Definición 2.4.1. Dados dos puntos distintos q y r en E 2 , la combinación convexa de estos puntos es: αq + (1 − α)r 18

(2.3)

PRELIMINARES

Figura 2.2: Mediatriz de A y B con α ∈ Q, 0 ≤ α ≤ 1.

Esta combinación convexa describe el segmento de línea recta uniendo los dos puntos q y r. Normalmente se denota como qr. Esto se extiende naturalmente a E 3. Definición 2.4.2 (Convexo). Un conjunto A del plano se llama convexo, si para todo par de puntos a, b en A, el segmento ab está contenido en A, según la combinación convexa (2.3). También se puede decir que un conjunto es convexo si y solo si cualquiera dos puntos de la región son visibles uno de otro. Un punto x en A es visible a un punto y si el segmento de línea xy yace en A. Ejemplo. El Semiplano es un conjunto convexo de puntos que tiene como borde una recta. Esto permite que los objetos tengan propiedades de separabilidad. Definición 2.4.3 (Mediatriz de un segmento). Es la recta perpendicular al segmento en su punto medio. En otras palabras, es el lugar geométrico de los puntos del plano que equidistan de los extremos del segmento (Fig. 2.2). Ver apéndice sec. 8.1 para más detalles.

19

2.5 POLÍGONOS

2.5.

POLÍGONOS

Los polígonos son a la geometría plana como los enteros son a la matemática numérica: un subconjunto discreto del gran universo de posibilidades que se prestan a sí mismos a cálculos eficientes. El polígono del cual partimos es el triángulo. Definición 2.5.1. La unión de los tres segmentos determinados por tres puntos no alineados se llama triángulo4 .

Un polígono P es la región cerrada del plano acotada por una colección finita de segmentos de línea que forman una curva cerrada que no se interseca a sí misma. Los segmentos de línea se llaman aristas y los puntos donde las aristas adyacentes se encuentran se llaman vértices, de manera que cada vértice contiene exactamente los extremos de dos aristas. El conjunto de vértices y aristas de P se llama la frontera del polígono, denotado ∂P . En la Fig. 2.3, polígono es el de la izquierda5 .

Figura 2.3: Polígonos y figuras

Veremos en capítulo III Capítulo 4 que la estructura TD es la unión de triángulos con características especiales. 5 En capítulo III Capítulo 3 veremos que siendo la CC un polígono, entonces su frontera son las aristas con sus vértices que ella forma. Además ∂(T D) = ∂(CC) y ∂(DV ) = Ø 4

20

PRELIMINARES

2.5.1.

Teorema de la Curva de Jordan

Este teorema topológico, formulado y demostrado por Camille Jordan en 1882, es notorio por ser obvio pero difícil de demostrar en su completa generalidad. Una aplicación de este teorema está ligada al teorema de los 4 colores. El Teorema de la Curva de Jordan Poligonal es: Teorema 2.5.2. La frontera ∂P de un polígono P parte el plano en dos componentes. En particular, las dos componentes de E 2 \ ∂P son el interior acotado y el exterior no acotado6 . Demostración. Supóngase P un polígono en el plano. Primero elegimos una dirección fija en el plano que no es paralela a alguna arista de P . Esto es siempre posible porque P tiene un número finito de aristas. Respecto a las semirrectas (rayos) que se intersecan con P en vértices, no contaremos una intersección en un vértice en el que las dos aristas de P que concurren en el vértice estén del mismo lado de la semirrecta, pero sí contaremos una intersección en un vértice donde las dos aristas estén en lados opuestos del rayo. Entonces cualquier punto x en el plano excepto la frontera ∂P , cae en uno de dos conjuntos: 1. El rayo a partir de x en la dirección fija cruza ∂P un número par de veces: x es exterior. 2. El rayo a través de x en la dirección fija cruza ∂P un número impar de veces: x es interior. Note que todos los puntos sobre un segmento de línea (o más generalmente, un segmento de línea poligonal) que no intersecan ∂P deben 6

Entendemos por cota un número que es más grande (o más pequeño) que todos los números dentro de un conjunto dado de números. ∂P acota en todas las direcciones el interior de un polígono, si consideramos que el plano tiene coordenadas (x, y).

21

2.5 POLÍGONOS yacer en el mismo conjunto. Así, los conjuntos pares (definidos por los cruces del rayo) y los conjuntos impares están conectados entre sí. Además, si existe un camino entre puntos en conjuntos diferentes, entonces este camino debe intersecar ∂P , de otra manera, pertenecerían al mismo conjunto (Fig. 2.4).

Figura 2.4: Teorema de Jordan para polígonos

2.5.2.

Diagonales y Triangulación de Polígonos

Los algoritmos frecuentemente “cortan” polígonos en piezas para procesarlas. Una natural descomposición de un polígono P en piezas más simples es alcanzado por el dibujo de diagonales. Una diagonal de un polígono es un segmento de línea conectando dos vértices de P y permanece en el interior de P , no tocando a ∂P excepto en sus extremos. Dos diagonales no se cruzan si ellas no comparten puntos interiores. Definición 2.5.3. Una triangulación de un polígono P es una descomposición de P en triángulos por medio de un conjunto maximal de diagonales que no se cruzan. Aquí maximal significa que no más diagonales pueden ser añadidas al conjunto sin cruzarse entre sí. 22

PRELIMINARES Las triangulaciones son las factorizaciones primas de los polígonos, pero sin el beneficio del Teorema Fundamental de la Aritmética, que garantiza una factorización única. Las afirmaciones siguientes se dan sin demostración (ver [65, 21]): Lema 2.5.4. Todo polígono con más de tres vértices tiene una diagonal. Teorema 2.5.5. Todo polígono tiene una triangulación. Teorema 2.5.6. Toda triangulación de un polígono P con n vértices tiene n − 2 triángulos y n − 3 diagonales (Fig. 2.5).

Figura 2.5: polígono triangulado

2.5.3.

Polígono Convexo

Tenemos P un polígono simple con n vértices xi para i = 1, ..., n y definimos los vectores-arista vi = xi+1 − xi donde hacemos xn+1 = x1 al definir vn . Entonces el polígono es convexo si y solo si todos los giros desde un vector-arista cualquiera al próximo tienen el mismo sentido. Sin embargo, una prueba más eficiente se puede ver en [60]. Sobre polígonos convexos7 tenemos los siguientes: 7

En el capítulo III, IV, V, veremos que la CC es un polígono convexo, la TD consta de polígonos convexos y el DV puede contener muchos de ellos.

23

2.5 POLÍGONOS

Lema 2.5.7. Una diagonal existe entre cualesquiera 2 vértices no adyacentes de un polígono P si y solo si P es un polígono convexo. Teorema 2.5.8. El número de triangulaciones de un polígono convexo con n + 2 vértices es el número de Catalán8 cn =

2n 1 n+1 n

 

, (ver una demostración en [69]).

Demostración. Imaginemos un polígono convexo Pn+2 con sus vértices etiquetados de 1 a n + 1 en sentido antihorario, el conjunto τn+2 de las triangulaciones de Pn+2 donde τn+2 tiene tn+2 elementos. Formemos a la función φ : τn+2 → τn+1 dada por la contracción de la arista {1, n + 2} de Pn+2 . Elijamos a un elemento T de τn+1 . Es interesante darse cuenta que el número de triangulaciones de τn+2 que tienen como imagen a T (el número de elementos de φ−1 (T )) es igual al grado del vértice 1 en T . Así que τn+2 = P

T ∈τn+1

grado de vertice 1 de T . Dado que el polígono es convexo, esto es verdad

para todos los vértices de T . Por lo tanto, sumaremos para todos los vértices de T , obteniendo (n + 1) · tn+2 = =

P

T ∈τn+1

Pn+1 i=1

Pn+1 P i=1

T ∈τn+1

grado de vertice i de T

grado de vertice i de T

= 2(2n − 1)tn+1 La ultima ecuación se sigue del hecho que la suma de los grados de todos los vértices de T es el doble del número de aristas de T y el número de diagonales de T (ver 2.10.3). Debido a que T está en τn+1 , éste tiene n + 1 aristas, y por el 2.5.6, tiene n − 2 diagonales, lo que da 2n − 1. Resolviendo para tn+2 , obtenemos (2n − 1) (2n − 3) 3 1 (2n)! 1 2n 2(2n − 1) tn+1 = 2n ... = = tn+2 = n+1 n+1 n 32 (n + 1)!n! n+1 n que es el número de Catalán buscado 8

Sabemos que

24

a b




=

a! b!(a−b)!

!

PRELIMINARES Definición 2.5.9. La unión de una circunferencia y sus puntos interiores es un círculo.

2.6.

MÁQUINAS DE TURING, COMPUTABILIDAD Y ALGORITMOS

En muchos ambientes, una computación es lo que modifica favorablemente un medio ambiente por medio de repetidas aplicaciones de una regla fija. La regla es usualmente referida como un algoritmo. Una Máquina (de) Turing es una simplificación extraordinaria de una computadora, por más avanzada que ésta sea. De hecho, fue uno de los esquemas pioneros que dieron lugar al desarrollo de las computadoras. Para nuestros propósitos, una Máquina Turing convierte una secuencia en lenguaje binario de ceros y unos en otra secuencia de ceros y unos, siempre y cuando la máquina se detenga adecuadamente para toda entrada después de procesarla y dar la salida requerida. Para ser precisos, consideramos el conjunto de todas las secuencias finitas de ceros y unos y lo llamamos I. Es decir I = {a1 a2 . . . an |ai ∈ {0, 1} ∧ i ∈ [1, n]}. Si M es la Máquina de Turing y fM es la función correspondiente, entonces decimos que M computa fM . Así, toda función f : I → I da lugar a una tarea computacional, una computación de f . Decimos que f es computable si esto es posible, es decir, si existe una Máquina Turing M tal que la correspondiente función fM es igual a f . A pesar de que algunas funciones no son computables, la teoría de complejidad trata sólo con funciones computables y estudia cuáles de ellas pueden ser compu25

2.6 MÁQUINAS DE TURING, COMPUTABILIDAD Y ALGORITMOS tables eficientemente.

Definición 2.6.1. Un algoritmo puede ser pensado como una Máquina de Turing cualquiera que se detiene (halt) para toda entrada posible. Su complejidad es definida por el número de pasos que la máquina realiza antes de detenerse.

En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín dixit algorithmus y éste a su vez del matemático persa Al-Juarismi (c. 780-c. 835)) es un conjunto ordenado de pasos o instrucciones ejecutables y no ambiguas para resolver un determinado problema. Propiedades: 1. Especificación precisa de la entrada. 2. Especificación precisa de cada instrucción. 3. Exactitud, corrección: se debe calcular la función deseada, convirtiendo cada entrada a la salida correcta. 4. Etapas bien definidas y concretas (subprogramas). 5. Número finito de pasos. 6. Un algoritmo debe terminar: no puede entrar en un bucle infinito. 7. Descripción clara del resultado o efecto. Esta amplia definición abarca tanto a algoritmos prácticos como aquellos que solo funcionan en teoría, por ejemplo el método de Newton y la eliminación de GaussJordan funcionan, al menos en principio, con números de precisión infinita; sin embargo no es posible programar la precisión infinita en una computadora, y no por ello dejan de ser algoritmos. 26

PRELIMINARES

2.7.

ANÁLISIS DE ALGORITMOS Y EFICIENCIA

Continuando con la sección anterior, el tiempo tomado por una Máquina Turing depende de la entrada, así que dada una máquina M y una cadena de caracteres o string x, podemos definir TM (x) como el número de pasos que M realiza antes de detenerse cuando x es la entrada. La función TM : I → N es la función de complejidad de la máquina M . Estamos interesados casi siempre en la complejidad en el peor caso de la máquina M . Esta es una función TM : N→ N definida como sigue: Dado un entero positivo n, TM (n) es el máximo valor de TM (x) en todas las cadenas de entrada x de longitud n. En otras palabras, queremos conocer el tiempo más largo posible que nuestra máquina puede gastar cuando se enfrenta a una entrada de longitud n9 . Se utiliza más sencillamente T (n) en lugar de TM (n) (donde M es un algoritmo), para representar el número de unidades de tiempo tomadas por un programa o algoritmo M para cualquier entrada de tamaño n. La alta velocidad de las computadoras actuales hace que la medida exacta de la eficiencia de un algoritmo no sea una preocupación vital en el diseño pero sí el orden general de magnitud de la misma. La función “O grande” representa “está en el orden de” y se expresa como O(n), es decir, “en el orden de n”. La notación O indica la cota superior del tiempo de ejecución de un algoritmo o programa. Así, en lugar de decir que un algoritmo emplea un tiempo de 4n − 1 en procesar un vector de longitud n, se dirá que emplea un tiempo O(n) que informalmente significa “algunos tiempos constantes 9

Como un ejemplo de la importancia de este este tema, ver Miraikan Channel [52]. Para mayor profundización en algoritmos, ver [41, 34, 49].

27

2.7 ANÁLISIS DE ALGORITMOS Y EFICIENCIA n”. Con la notación O se expresa una aproximación de la relación entre el tamaño de un problema y la cantidad de proceso necesario para hacerlo. Por ejemplo si: T (n) = n2 − 2n + 3 entonces T (n) ∼ = O(n2 ). Definición 2.7.1. Se dice que T (n) es O(g(n)) si g(n) acota superiormente a T (n). De modo más riguroso, T (n) es O(g(n)) si existe un entero n0 y una constante c > 0 tal que para todos los enteros n ≥ n0 se tiene que T (n) ≤ cg(n). De menor a mayor tenemos log2 n < n < nlog2 n < n2 < n3 . . . nk < 2n < n!

(2.4)

Propiedades de la notación O: 1. Siendo c una constante, c ∗ O(f (n)) = O(f (n)) 2. O(f (n)) + O(g(n)) = O(f (n) + g(n)) 3. m´ aximo[O(f (n)), O(g(n))] = O(m´ aximo[f (n), g(n)]) 4. O(f (n)) ∗ O(g(n)) = O(f (n) ∗ g(n)) 5. O(loga (n)) = O(logb (n))para a, b > 1. En adelante, no colocaremos explícitamente la base del logaritmo, que casi siempre es 2. 6. O(log(n!)) = O(n ∗ log(n)) 7. Para k > 1, O(Σni=1 ik ) = O(nk+1 ) 8. O(Σni=2 log(i)) = O(n ∗ log(n)) Complejidad de sentencias básicas: 1. Las sentencias de asignación, son de orden constante O(1) 2. La complejidad de una sentencia de selección (condicional if o elseif ) es el máximo de las complejidades del bloque then y else. Para una sentencia 28

PRELIMINARES de selección múltiple (select − case), es el máximo de las complejidades de cada uno de los bloques case. Para un bucle condicional while o automático (f or), se ha de estimar el número máximo de iteraciones para el peor caso: entonces la complejidad del bucle es producto del número de iteraciones por la complejidad de las sentencias que forman el cuerpo del bucle10 . Obtener una cota mínima de un problema requiere establecer una cota mínima para todos los algoritmos concebibles dentro de un cierto modelo de computación. Cuando la cota superior de un algoritmo particular iguala la cota mínima del problema, decimos que el algoritmo es asintóticamente óptimo.

2.8.

EL PROCESO DE LA GEOMETRÍA COMPUTACIONAL

El camino desde la formulación del problema a soluciones eficientes y elegantes ha sido frecuentemente largo, con muchas dificultades y resultados intermedios subóptimos. Hoy existe una rica colección de algoritmos geométricos que son eficientes y relativamente fáciles de implementar y entender. Las buenas soluciones a problemas algorítmicos de naturaleza geométrica se basan generalmente en dos ingredientes: uno es un minucioso entendimiento de las propiedades geométricas del problema, el otro es una aplicación apropiada de técnicas algorítmicas y estructuras de datos. Si no se entiende la geometría del problema, todos los algoritmos del mundo no nos ayudarán a resolverlo eficientemente. Por otro lado, si se entiende perfectamente la geometría del problema, es duro resolver10

Estas estructuras existen en Scilab y se verán en el capítulo VI

29

2.8 EL PROCESO DE LA GEOMETRÍA COMPUTACIONAL lo efectivamente si no se conoce las técnicas algorítmicas correctas. Si los puntos de entrada son dados en coordenadas de punto flotante y los cómputos son hechos usando aritmética de punto flotante (APF), entonces habrá errores de redondeo que pueden distorsionar la salida de las pruebas11 . Debido a los errores de redondeo puede repentinamente haber dos o ninguna arista comenzando en un vértice p. Esto puede causar que el programa que implementa un algoritmo sencillo se bloquee. El desarrollo de un algoritmo geométrico frecuentemente pasa por tres fases: en la primera fase, ignoramos todo lo que pueda obstaculizar nuestro entendimiento de los conceptos geométricos con los que estamos tratando. En la segunda fase, tenemos que ajustar el algoritmo diseñado en la primera fase a su corrección en la presencia de casos que no admiten posición general: Definición 2.8.1 (Posición general). Un conjunto de puntos u objetos más generales se dice que están en posición general si ellos evitan las configuraciones problemáticas, conocidas como situaciones degeneradas, que pueden ser: 2 o más puntos sobre una línea vertical, 3 o más puntos sobre una línea cualquiera o 4 puntos sobre una circunferencia. Considerando la geometría del problema nuevamente, uno puede frecuentemente integrar casos especiales con el caso general. Los casos especiales definitivamente incrementan la complejidad de las implementaciones. La mayoría de investigadores en GC de hoy en día están conscientes de que sus supuestos de “posición general” no son satisfechas en aplicaciones prácticas y que un tratamiento integrado de los casos especiales es normalmente la mejor manera de manejarlos. 11

El software Scilab usa APF

30

PRELIMINARES La tercera fase es la implementación. Ahora se necesita pensar acerca de las operaciones primitivas, como probar si un punto yace a la izquierda, a la derecha o sobre una línea dirigida. Para ello se dispone de una librería de software geométrico (CGAL[15], LEDA12 , CGLAB13 , SIVP, METANET) disponible que contiene las operaciones que se necesitan, de otra manera se deben implementar14 .

2.9.

PROGRAMAS, RECURSIVIDAD Y ESTRUCTURAS DE DATOS

Un programa es una ejecución (instanciación) de un algoritmo en un lenguaje de programación de computadora. En otras palabras, un programa es una secuencia de instrucciones que indican al hardware de un ordenador qué operaciones debe realizar con los datos. Los programas pueden estar incorporados al propio hardware, o bien pueden existir de manera independiente en forma de software. Los compiladores traducen un programa íntegro a lenguaje máquina antes de su ejecución, por lo cual se ejecutan con tanta rapidez como si hubiesen sido escritos directamente en lenguaje máquina. En este paradigma, los programas se descomponen en unidades más pequeñas que adoptan el nombre de funciones (procedimientos, subprogramas o subrutinas en otros lenguajes de programación). De este modo, un programa orientado a procedimientos se divide en funciones, de modo que cada función tiene un propósito bien definido y resuelve una tarea concreta, se diseña una interfaz claramente 12

http://algorithmic-solutions.com/leda/ledak/index.htm Hay actualmente un proyecto en Scilab denominado CGLAB. Se espera que este proyecto utilice una gran cantidad de librerías en C++ para la Geometría Computacional (GC). 14 Las implementaciones aquí se hicieron en base a las librerías SIVP y METANET

13

31

2.9 PROGRAMAS, RECURSIVIDAD Y ESTRUCTURAS DE DATOS definida para su comunicación con otras funciones15 . Un problema importante de la programación estructurada reside en el hecho de que la disposición separada de datos y funciones no se corresponde con los modelos de las cosas del mundo real. Los objetos del mundo real tienen atributos y comportamiento. Aquí nace el paradigma de la Programación Orientada a Objetos (en inglés OOP)16 .

2.9.1.

La técnica Divide y Vencerás

En su acepción más amplia es algo más que una técnica de diseño de algoritmos. De hecho, suele ser considerada una filosofía general para resolver problemas. En nuestro contexto, esta técnica consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de menor tamaño. Si éstos subproblemas son todavía relativamente grandes, se aplicará de nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente. Por último, se combinan las soluciones obtenidas anteriormente para construir la solución del problema original. Esta técnica sugiere naturalmente el uso de la recursión, sec. 2.9.2 en las implementaciones de estos algoritmos.

En Scilab, el programa puede ser una función (function) o un grupo de ellas relacionadas entre sí. Para la interacción con el usuario, se diseña una ventana con un menú de lo que desee realizar (ver capítulo VI). 16 Implementaciones según este paradigma están en Ruiz [70], Expósito [28] y por supuesto Geogebra[43]. 15

32

PRELIMINARES

2.9.2.

Recursividad

La recursividad (recursión) es aquella propiedad que posee una función o procedimiento por la cual puede llamarse a sí misma. Una función (o procedimiento) que tiene sentencias entre las que se encuentra al menos una que llama al propia función (procedimiento) se dice que es recursiva. En matemáticas, la definición de una función en términos de sí misma se denomina definición inductiva y conduce naturalmente a una implementación recursiva. El caso base es esencial dado que se detiene, potencialmente, una cadena de llamadas (a la propia función). Este caso base o condición de salida debe fijarse en cada solución recursiva.

2.9.3.

Estructuras de Datos

Las estructuras de datos son maneras de organizar información, los cuales, en conjunción con los algoritmos, permiten la solución eficiente y elegante de problemas computacionales. Tenemos como estructuras las pilas, colas, bicolas, árboles binarios y de búsqueda, arrays dinámicos, listas, grafos, etc.

2.9.4.

Primitivas Geométricas

Las primitivas geométricas son las bases para muchos algoritmos de la Geometría Computacional (GC). Son usadas para extraer información combinatoria a partir de los puntos de entrada. Lo agradable acerca del uso de estas primitivas es que su complejidad es constante, es decir O(1). Esto es así porque el modelo de computación utilizado aquí (árbol de decisión lineal) lo especifica. Más precisamente, estas primitivas geométricas dependerán de los signos de ciertos determinantes. 33

2.9 PROGRAMAS, RECURSIVIDAD Y ESTRUCTURAS DE DATOS Así, las primitivas realmente tendrán 3 valores: {+, −, 0}. Estos corresponden a verdadero, falso, degenerado (es una convención).

2.9.4.1.

La primitiva CCW

Dados tres puntos A, B, C, CCW nos dice si estos 3 puntos están en orden contrarreloj alrededor de su círculo común por medio del cálculo del signo del determinante     det    



xA y A 1  

(2.5)

xB y B 1   

xC y C 1

 

Si el signo es positivo, entonces A, B, C están en orden contrarreloj; si el signo es negativo, entonces A, B, C están en orden reloj; si éste es cero, entonces A, B, C son colineales (Fig. 2.6). Note que determinar el signo de un determinante es tan caro como calcular su valor17 . La implementación del CCW está en la sec. 6.3.2.8.

Figura 2.6: Primitiva CCW

17

La CCW es útil para el cálculo de CC, pero no es suficiente
para calcular el DV o la TD. Esto sucede así porque en algunos arreglos cada uno de los n3 triángulos tienen el mismo valor de CCW pero los n puntos pueden tener estructuras diferentes.

34

PRELIMINARES

Figura 2.7: Primitiva Ccírculo

2.9.4.2.

La primitiva Ccírculo

Dados 4 puntos A, B, C, D, la primitiva Ccírculo es verdadera si y sólo si D está en la cara izquierda de la circunferencia orientada a través de A, B, C. La cara izquierda es el interior de la circunferencia si CCW (A, B, C) > 0, de otra manera, la cara izquierda es el exterior del círculo. Así, si tomamos A, B, C en orden contrarreloj, Ccírculo nos dice si D está dentro de su circunferencia (ver Fig. 2.7). Note que existe una situación degenerada si D está sobre la circunferencia (4 puntos cocirculares) o si todos los cuatro puntos son colineales. Curiosamente, la situación no es degenerada si A, B, C son colineales pero D está fuera de la línea, ya que aún existe una cara definible izquierda.

Proposición 2.9.1. El valor del Ccírculo(A, B, C, D) es dado por el signo del 35

2.10 GRAFOS

determinante18       det      

2.10.

xA y A

x2A

xB yB

x2B

+

yA2

+

yB2



1  1

xC yC x2C + yC2 1 2 xD yD x2D + yD 1

         

(2.6)

GRAFOS

Tienen aplicaciones en sociología, química, geografía, ingeniería eléctrica e industrial, etc. Existen numerosos problemas que se pueden modelar en términos de grafos. Ejemplo de ello es la planificación de las tareas que completan un proyecto, encontrar las rutas de menor longitud entre dos puntos geográficos, calcular el camino más rápido en un transporte, determinar el flujo máximo que puede llegar desde una fuente de agua potable a, por ejemplo, una urbanización.

19

Definición 2.10.1. Un grafo es un par G = (V, E) en el que V es un conjunto finito y E es un conjunto de subconjuntos de dos elementos de V ; u es adyacente a v siempre y cuando {u, v} ∈ E (u, v ∈ V )20 . Vecindad de v: N (v) = {u ∈ V : u ≺ v}

(2.7)

(la relación ≺ significa “comparte arista con”). El grado de v es JN (v)K, es decir, la cantidad de elementos vecinos a v.

En el capitulo VI está definida la función asociada a CCW y Ccírculo Como información introductoria están las diapositivas de Barceló (ver [8, 9]). 20 Cuando queramos describir una gráfica que tenga bucles y aristas paralelas usaremos la palabra multigráfica, que no se usará aquí 18 19

36

PRELIMINARES Si todos los vértices en G tienen el mismo grado, se dice que G es regular. Definición 2.10.2. El orden de G es la cantidad de vértices V allí, esto es, kV k. El tamaño de G es la cantidad de aristas E, esto es kEk. Teorema 2.10.3 (de los saludos). La suma de los grados de los vértices en G es el doble de la cantidad de aristas, esto es,

X v∈V

JG(v)K = 2kEk

(2.8)

Esta identidad se usa para hallar la Característica de Euler en Grafos Planos: 3kV k < 2kEk

(2.9)

Ver apéndice sec. 8.6 sobre la Fórmula de Euler. Definición 2.10.4. Se dice que G es subgráfica de H siempre y cuando los conjuntos de vértices y aristas de G están contenidos en H: V (G) ⊆ V (H) y E(G) ⊆ E(H). Se dice que G es subgráfica incorporada de H siempre y cuando G es subgráfica de H y V (G) = V (H). Tenemos H una gráfica y A ⊆ V (H). La subgráfica de H inducida en A es la gráfica HA definida por V (HA ) = A y E(HA ) = {(x, y) ∈ E(H) : x, y ∈ A}. Las aristas de HA son las aristas de H legalmente posibles, es decir, que tienen ambos extremos en A. Definición 2.10.5. Una caminata en G es una sucesión (o una lista) de vértices, 37

2.10 GRAFOS donde cada vértice es adyacente al siguiente; esto es, W = (v0 , v1 , ..., vl ) con v0 ≺ v1 ≺ ... ≺ vl

(2.10)

La longitud de esta caminata es l. Hay l + 1 vértices (a lo sumo). Está permitido visitar más de una vez los vértices en una caminata. Definición 2.10.6. Camino (cam) es una caminata en la que no se repiten vértices. Dada una sucesión de vértices en G que forme un camino, también se considera que esa sucesión es una subgráfica de G, los vértices y las aristas de esta subgráfica son los vértices y aristas que recorre el camino. Pm representa un camino con m vértices. Se dice que u ∈ V (G) está conectado con v ∈ V (G) siempre y cuando haya un camino (u, v) en G. Teorema 2.10.7. La relación a“está conectado con” es una relación de equivalencia en V (G). Sabemos que la relación de equivalencia es reflexiva, simétrica y transitiva. Demostración. Supongamos los vértices v1 , v2 , v3 en V (G). Es natural y permitido que v1 a v1 y por tanto a es reflexiva. Si v1 a v2 existe una arista que conecta los dos vértices v1 , v2 . Por definición esta arista es no orientada, por tanto también es válido decir v2 a v1 . Así, a es simétrica. Si v1 a v2 y v2 a v3 entonces existe una arista que conecta v1 , v2 y una arista que conecta v2 , v3 . Se puede decir que v1 a v3 si asumimos que puede haber más de una arista en el camino de v1 a v3 . En fin, a es transitiva. Definición 2.10.8. Se dice que una gráfica está conectada (conexa) siempre y cuando cada par de vértices en la gráfica estén conectados por un camino. Es decir 38

PRELIMINARES

∀x, y ∈ V (G) ∃ cam(x, y)

(2.11)

Si G está conectada, un vértice v cortado es aquel tal que G−v está desconectada. De igual manera, e es una arista cortada si G − e está desconectada. Definición 2.10.9. Un ciclo es una caminata de longitud mínima 3, en la que el primero y el último vértice son el mismo, pero no se repiten otros vértices. Un ciclo de n vértices se representa por Cn . Definición 2.10.10. Tenemos a G una gráfica y k entero positivo. Una iluminación k de G es una función f : V (G) → {1, 2, ..., k}. Es propia siempre y cuando

∀(x, y) ∈ E(G), f (x) 6= f (y)

(2.12)

A G se le llama k−iluminable. El entero mínimo posible k para el que G es k−iluminable se llama número cromático de G. Si el grado máximo de G es ∆, entonces χ(G) ≤ ∆ + 1

(2.13)

Para los ciclos Cn :

χ(Cn ) =

   

2

  

  3 si n es impar 

si n es par

   

(2.14)

39

2.10 GRAFOS Definición 2.10.11. Tenemos (x, y) vértices de G. La distancia de x a y en G es la longitud del camino (x, y) más corto. Si no hay camino, la distancia es ∞. La abstracción matemática de un dibujo se llama incrustación. Definición 2.10.12. Una gráfica plana es una gráfica que tiene una incrustación sin cruces en el plano21 (donde se cumple el Teorema de Jordan 2.5.2). Una caracterización muy importante es el Teorema de Kuratowski (ver [71, 22]). El problema del mapa de 4 colores lo propuso Francis Guthrie por primera vez en 1852, y permaneció sin resolver durante más de un siglo hasta que, a mediados de 1970, Appel y Haken demostraron que todo mapa se puede iluminar usando cuando mucho 4 colores22 . Definición 2.10.13. Tenemos G = (V, E) y (V ? , E ? ) dos grafos planos cualquiera, y el conjunto de las caras de G es F = {c|c ∈ R2 \ G}, y de (V ? , E ? ) es F ? . Llamamos a (V ? , E ? ) un grafo dual de G y escribimos (V ? , E ? ) := G? si existen biyecciones f, g, h en donde f : F → V ? , g : E → E ? , h : V → F ? que satisfacen las condiciones siguientes: 1. f (c) ∈ F para todo c ∈ F 2. e ∩ G y e? ∩ G? consiste en un punto, para e ∈ E y e? ∈ E ? 3. v ∈ F ? para todo c ∈ F ? Todo grafo plano conexo tiene un grafo dual plano. Además, este dual es único, topológicamente hablando, y G es él mismo el dual de G? . Todo esto es fácil de demostrar. La CC, TD y DV son gráficas planas. En general, no es fácil verificar con un algoritmo si una gráfica es plana, a pesar de tener una complejidad de O(n). 22 Ver más en [37], en que se hizo una demostración usando el software COQ de INRIA. Descargable desde https://coq.inria.fr

21

40

3 CONVEX-HULL O CÁPSULA CONVEXA (CC)

3.1.

NOTAS PREVIAS

La cápsula o envoltura es un polígono simple que referimos a un conjunto finito de puntos. Ya hemos visto en Preliminares sec. 2.5.3 el concepto de polígono convexo. El primer método que se utilizó para calcular la envolvente era por fuerza bruta, dicho proceso tenía una función de complejidad en el tiempo del orden de O(n3 ). Primero se numeran los puntos tal como estén almacenados en la matriz, pila, lista, etc. Luego, se toman dos puntos a la vez y se prueba si todos los demás puntos quedan en un solo lado de la línea formada por ellos. Si esto es cierto, entonces estos dos puntos son parte de la CC, si esto no ocurre, probamos con el siguiente punto y así sucesivamente hasta agotar todas las posibilidades (ver algoritmo 1). Luego se presenta el algoritmo incremental, con T (n) ∼ = O(n2 ), que explicamos más adelante y el algoritmo de envoltura de regalo, por Donald Chand y Sham Kapur en 1970 (primero para CC en dimensiones más altas, ver [17]), con T (n) ∼ = 41

CONVEX-HULL O CÁPSULA CONVEXA (CC)

input : Un conjunto S de puntos en el plano output: La cápsula convexa CC de S inicio Se numeran los puntos de entrada en la lista; for i = 1..n do para cada punto i for j = 2..n do para cada punto j for k = 3..n do para cada punto k Aplicar CCW (pi , pj , pk ); if CCW > 0 then almacenar en tr1 ; else almacenar en tr2 ;si CCW < 0 // si CCW == 0 ignorar el punto y avanzar (se supone posición general) if tamaño de tr1 o tr2 es vacío then almacenar pi , pj en convx; hacer i == j; avanzar con j = 2...n; end end end end fin Algoritmo 1: CC por Fuerza bruta O(nh). El algoritmo para dos dimensiones, conocido como la marcha de Jarvis (ver [46]), funciona de la manera siguiente: Se busca el punto p0 que esté con la coordenada-y mínima, luego se selecciona el punto pi+1 tal que todos los demás puntos estén a la → derecha de la línea ← pi− p− i+1 . Repitiendo hasta que se alcance pn = p0 , se obtiene la CC en h pasos, donde h es la cantidad de vértices que forman la CC. El valor de h no es conocido de antemano, y esto puede variar dependiendo de la situación desde un pequeño valor hasta n. La complejidad en tiempo de O(nh) hace favorable el algoritmo cuando se espera que h sea muy pequeño en comparación con n (ver algoritmo 2). 42

3.1 NOTAS PREVIAS

input : Un conjunto S de puntos en el plano output: La cápsula convexa CC de S inicio Se escoge el punto p0 que está más a la izquierda; Se selecciona pi+1 tal que todos los puntos están a la derecha de la linea pi pi+1 ; // esto puede ser encontrado en O(n) comparando ángulos polares Haciendo i = i + 1 y repitiendo hasta que un punto alcance a p0 ; // se obtiene la CC en h pasos fin Algoritmo 2: Marcha de Jarvis En los laboratorios Bell de finales de los 60, Ron Graham (ver [57]) desarrolló un algoritmo para calcular la CC de cerca de 10 mil puntos en el plano. En su documento de 1972 Graham [38] presentó el primer algoritmo de T (n) ∼ = O(nlog(n)): el Scan de Graham. En 1977, Preparata y Se June Hong fueron los primeros en aplicar el método divide y vencerás, sec. 2.9.1 al problema del CC. En el espacio de 2 y 3 dimensiones, el algoritmo de Timothy Chan es el de salida sensitiva óptimo hasta ahora para calcular el CC de un conjunto S de n puntos. El algoritmo toma una complejidad en tiempo de O(nlog(h)), con h definido anteriormente. El algoritmo combina el de Graham con el de la marcha de Jarvis (ver [16, 54])1 . El primer paso para organizar un conjunto de puntos es encontrar su cápsula convexa (CC). el concepto de región o conjunto convexo se ha visto en la definición 2.4.2. La envolvente convexa de una nube de puntos es siempre un polígono convexo. Es fácil demostrar esto, ver [18]. 1

Kirkpatrick y Seidel dieron un algoritmo con O(nlog(h)) pero de difícil implementación, con h el número de vértices que forman el CC.

43

CONVEX-HULL O CÁPSULA CONVEXA (CC) Definición 3.1.1. La envolvente convexa (CC) de un conjunto finito de puntos S, es la intersección de todas las regiones convexas que contienen a S. Aunque esta definición y otras del mismo estilo son naturales, no son computables, es decir, no son computacionalmente útiles. Veamos otra manera de construir una CC. Recordemos que una combinación convexa de puntos S = {p1 , . . . , pn } es de la forma λ1 p1 + . . . + λn pn , donde λi ≥ 0 y Σλi = 1. Una combinación particular de estos puntos es otro punto dentro del polígono formado por ellos. Tenemos el siguiente: Teorema 3.1.2. Para un conjunto de puntos S, la CC de S es el conjunto de todas las combinaciones convexas de S. La demostración se encuentra en el apéndice sec. 8.4. Veremos a continuación el algoritmo incrementable, seguidamente el de Graham, el de Divide y vencerás, la CC en 3D y por último algunas aplicaciones.

3.2.

EL ALGORITMO INCREMENTABLE (INCREMENTAL)

Calcular la CC significa identificar los vértices de la frontera del polígono que cubre el conjunto. Es fácil hacerlo visualmente con un pequeño conjunto de puntos, pero si se nos dan cientos o miles de puntos dados en su forma cartesiana, entonces calcular la CC se torna duro. Es necesario enseñar a la computadora a hacerlo. Comenzamos con el algoritmo más parecido a la prueba matemática por inducción. En un alto nivel, asumimos que la cápsula de k puntos ha sido construida y usamos 44

3.2 EL ALGORITMO INCREMENTABLE (INCREMENTAL) esto para construir la cápsula con k + 1 puntos. Esto se llama el algoritmo 3 incrementable2 (ver Fig. 3.1). input : Un conjunto S de puntos en el plano output: La cápsula convexa CC de S inicio Se ordenan los puntos según la coordenada x-horizontal; Obtener H3 , los primeros tres puntos en S ; // ordenados tales que ellos circundan en sentido contrarreloj Asumamos que hemos construido Hk ; consideramos ahora el próximo punto p de nuestra lista S ordenada; // Ya que esta lista está ordenada,p pertenece a Hk+1 porque ella está en el extremo de la dirección x Añadir p a nuestra cápsula; // aunque varios de los previos puntos de Hk pueden ser ahora interiores al polígono Eliminar estos puntos interiores; fin Algoritmo 3: CC Incrementable

Figura 3.1: CC en diferentes etapas hasta k + 1 Así que ahora necesitamos una manera de sumar p a nuestra lista Hk en la posición apropiada mientras se eliminan posibles puntos extraños. 2

La palabra incremental no aparece en RAE, más adecuado es “incrementable”, pero lo usaremos indistintamente.

45

CONVEX-HULL O CÁPSULA CONVEXA (CC) Definición 3.2.1 (Tangente a P en x). Supóngase P un polígono convexo y x un punto en la frontera de P . Entonces una línea L que contiene a x sostiene a P en x si todo P se encuentra a un lado de L. La línea L se llama entonces “tangente a P en x” (Fig. 3.2). Observamos allí que la tangente puede pasar por un punto o por un lado (arista) del polígono3 .

Figura 3.2: línea L tangente a P Nuestra tarea es encontrar dos puntos en Hk que tengan líneas tangentes al CC(Hk ) pasando a través de p. La observación clave es ver las cosas no desde la perspectiva de los vértices de la CC, sino de sus aristas. Como la Fig. 3.3 muestra, cada arista de CC(Hk ) es o visible a p, invisible a p, o yace en la misma línea pasando por p (pero esta opción es excluida dada la suposición de posición general, ver definición 2.8.1). Así que habrá dos vértices del CC donde sus aristas correspondientes pasan de ser visibles a ser invisibles desde p. Éstos son los vértices de tangencia. Considere cualquier arista del polígono CC y supóngase L la línea sobre la cual esta arista yace. Entonces observemos que esta arista es visible a p si p y CC(Hk ) están en 3

Resulta interesante si suponemos un polígono de un número muy grande de lados, nos acercaríamos al concepto de tangente de una curva visto en cálculo vectorial en la UNA.

46

3.2 EL ALGORITMO INCREMENTABLE (INCREMENTAL)

Figura 3.3: Tangentes a Hk lados opuestos de L. Similarmente, la arista es invisible si ellos están en el mismo lado de L (ver Fig. 3.4).

Figura 3.4: Aristas visibles e invisibles Así que los puntos que buscamos son aquellos con líneas tangentes que agrupan y separan al mismo tiempo CC(Hk ) y p. Una vez que los dos puntos de tangencia se encuentran, simplemente los ubicamos en la posición apropiada en el CC(Hk ), eliminando los nuevos puntos interiores (y reemplazándolos por p). Así, si pi y pj son los vértices especiales de tangencia, donde pi aparece antes de pj en el orden contrarreloj de Hk , entonces Hk+1 = {. . . pi−1 , pi , p, pj , pj+1 , . . .}. Vamos a calcular la complejidad en tiempo del algoritmo incrementable. Da47

CONVEX-HULL O CÁPSULA CONVEXA (CC) dos n puntos en S, primero los ordenamos. Esto puede ser alcanzado en tiempo O(nlogn), con el algoritmo quicksort, en el apéndice sec. 8.2. Para cada punto de S (después de los primeros 3) necesitamos probar cada arista de la cápsula existente para ver si ésta es visible hacia el punto. En el peor caso, pudimos necesitar considerar k − 1 aristas cuando se suma el punto k. ya que esta prueba se necesita ejecutar por cada nuevo punto, podríamos ejecutarlo como: 3 + 4 + . . . + (n − 1) =

n2 n n(n − 1) − (1 + 2) = − −3 2 2 2

(3.1)

cálculos en tiempo constante. Dado que el término más significante de esta suma es n2 , la complejidad en tiempo computacional es O(n2 ). Observación. En casos determinados es más conveniente utilizar este algoritmo, dado que existen situaciones en donde puede haber variaciones locales, en donde no sea necesario recalcular una estructura global cada vez.

3.3.

EL ALGORITMO DE GRAHAM

Notamos que su complejidad es del orden O(nlogn), es una mejora al algoritmo anterior (algoritmo 3). Para iniciar el algoritmo elegimos el primer punto de S, denotado por P0 , como el punto de más baja altura. En caso de empate, se toma el extremo derecho de los puntos. Luego ordenamos todos los puntos de S en el sentido contrario a las agujas del reloj de acuerdo al ángulo que forma desde la horizontal hasta el rayo que parte de P0 y termina en el punto4 (Fig. 3.5). Se verifica si Pm Pm+1 Pi es un giro a la izquierda (CCW > 0, ver sec. 2.9.4.1). 4

Ver el vídeo de Clara Grima, en [40]

48

3.3 EL ALGORITMO DE GRAHAM

Figura 3.5: Ordenación según ángulos Si eso es así, Pm+1 y Pi son puntos de la envolvente. Los giros a la derecha se descartan y se elimina de la lista el vértice que lo origina (Fig. 3.6).

Figura 3.6: Descarte de giros a derecha Se continúa hasta llegar al punto de inicio P0 . Como antes se mencionó, ordenar los puntos tiene complejidad O(nlogn). Recorriendo el algoritmo, vemos que cada punto es considerado a lo más dos veces: una vez cuando se agregan y una vez si forman un giro ilegal a la derecha. Por tanto, la búsqueda de los puntos de la cápsula ejecuta O(n) iteraciones. Ahora, usando las propiedades de O sección 2.7: T (n) ∼ = O(nlogn) + O(n) = O(nlogn+n)= O(nlogn), ya que n < nlogn (ver ecuación (2.4)). La complejidad total se mantiene en O(nlogn). 49

CONVEX-HULL O CÁPSULA CONVEXA (CC)

3.4.

ALGORITMO (DIVIDIR Y VENCER)

Seguimos con otra forma de hallar la CC de un conjunto S de n puntos. La idea del algoritmo es dividir en dos partes el conjunto de puntos, calcular la CC de cada parte y unirlas con dos puentes o tangentes, allí está lo esencial de esta construcción. Proporcionamos el algoritmo 4: Para concatenar, lo haremos con el puente superior y puente inferior. Al determinar las líneas del puente, podemos empalmar ambos conjuntos realizando lo siguiente (algoritmo 5). ¿Cómo se calculan los vértices extremos a y b? Comenzamos con una primera aproximación del puente considerando la línea que une a xmax1 (el punto más a la derecha de S1 ) con xmin2 (el punto más a la izquierda de S2 ). La idea es seguir bajando hasta llegar a la línea “tangente”(definición 3.2.1) a ambos polígonos. Este algoritmo tiene orden de complejidad O(n). El seudocódigo del algoritmo del Puente Inferior es algoritmo 6 (ver [65] y la Fig. 3.7):

Figura 3.7: Efecto del algoritmo Puentes El algoritmo de Puente Superior es análogo. 50

3.4 ALGORITMO (DIVIDIR Y VENCER)

input : Un conjunto S de puntos en el plano output: La cápsula convexa CC de S inicio Halle la mediana de las coordenadas-x de los puntos de S; Divida S en dos subconjuntos disjuntos S1 , S2 ; Hallar recursivamente CC(S1 ), CC(S2 ); Concatenar las dos CC; fin Algoritmo 4: Puentes (Dividir y vencer)

input : CC(S1 ) y CC(S2 ) output: Cápsula Convexa de S = S1 ∪ S2 inicio Eliminar aquellos lados de S1 que se encuentran entre los vértices de contacto; // limpiar parte derecha Eliminar aquellos lados de S2 que se encuentran entre los vértices de contacto; // limpiar parte izquierda Colocar los puentes; fin Algoritmo 5: Concatenación puentes

input : CC(S1 ) y CC(S2 ) output: Puente Inferior de S = S1 ∪ S2 inicio Calcular xmax1 , el punto más a la derecha de S1 ; Calcular xmin2 , el punto más a la izquierda de S2 ; while L = xmax1 xmin2 no sea tangente simultánea para S1 y S2 do while L no sea tangente para S1 do xmax1 ← xi−1 ; while L no sea tangente para S2 do xmin2 ← xj+1 ; end fin Algoritmo 6: Puente inferior

51

CONVEX-HULL O CÁPSULA CONVEXA (CC)

3.4.1.

Parte Recursiva

Se comienza con los casos-base: 1. Dos puntos: su CC es una arista que los une. Primero se ordena, para que la orientación esté desde abajo hacia arriba. 2. Un punto: su CC es ese punto. Procediendo de una manera recursiva se puede obtener la CC de un conjunto de puntos S, usando el algoritmo del puente superior e inferior. La CC total es la suma de 4 componentes (ver [18]): CC = CCizq [p3 → p1 ] + {p1 , p2 } + CCder [p2 → p4 ] + {p4 , p3 }. Se trabajan con listas de cada conjunto y los puntos obtenidos después de realizar los algoritmos Puente superior y Puente inferior5 . El punto de inicio de la lista CC izquierda o CC derecha puede estar dentro de la “zona interior” (aristas que deben desaparecer del CC total) o fuera de ella. Considerando esto, el algoritmo realiza la envoltura convexa que resulta de unir dos conjuntos mediante sus puentes correspondientes. El algoritmo en Scilab (sec. 6.3) consta de un ciclo for para desplegar cada punto de la envoltura y con ayuda de las condicionales if y banderas booleanas convenientes, se logran los objetivos propuestos en el algoritmo. Se asumió en todo el algoritmo que el recorrido de los vértices se hace a favor de las agujas del reloj (que origina una pequeña corrección en la práctica). El orden de complejidad en tiempo para encontrar las líneas tangentes o puentes es lineal, recorriendo a la vez el CC izquierdo y derecho. La complejidad en tiempo total del algoritmo Divide y Vence (O(nlogn)) está calculada en el apéndice sec. 8.5. 5

Esta es la implementación del TI en Scilab

52

3.5 APLICACIONES DE LA CC

3.5.

APLICACIONES DE LA CC

Hemos visto una breve revisión de los algoritmos más interesantes para la CC, ahora veremos algunas aplicaciones: 1. Cálculo del diámetro y la anchura de un conjunto (Diseño Industrial). El diámetro de una nube de puntos S es la mayor distancia posible entre todos los puntos de S. La anchura es la menor longitud, de entre todas las posibles, entre dos rectas paralelas que contengan en su interior todos los puntos pertenecientes a S (ver [28, 64]). Se aplica para el cálculo de envolturas. 2. Planificación de Movimientos (Robótica): debido a que el cálculo de caminos que evitan colisiones es más sencillo con robots poligonales convexos que con no-convexos (ver [51]). 3. En Seguridad e Inteligencia Artificial, con respecto al Análisis de Formas (o Reconocimiento de Patrones): las formas pueden ser clasificadas con el objetivo de compararlas por su “convex-deficiency-tree”, estructuras que dependen para su cálculo del cierre convexo (CC). 4. En Química y Meteorología: Las CC y capas convexas son herramientas usadas para realizar “capas de cebolla” y para calcular elementos centrales de un conjunto. Las llamadas capas de cebolla (Onion peelings) son secuencias de CC anidados. Son importantes en la propagación de eventos químicos y en el estudio de las capas de la atmósfera6 . 5. Para la Estadística en lo referente a la estimación robusta (insensible a desviaciones de la distribución poblacional asumida) y en la regresión isotónica (elección de la curva de regresión de comportamiento monótono creciente o 6

Ver http://www.montefiore.ulg.ac.be/~briquet/algo3-chull-20070206.pdf

53

CONVEX-HULL O CÁPSULA CONVEXA (CC) decreciente), ver [61].

54

4 TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS Tocaremos el tema general de triangulación, el cual es necesario comprender antes de pasar a la TD. Ya se ha visto la triangulación de polígonos en Preliminares (sec. 2.5.2) Veremos el primer algoritmo de triangulación de un conjunto de puntos, el algoritmo incremental, el maravilloso aporte de la formula de Euler (las demostraciones en apéndice), el grafo de intercambios GF (S), la Triangulación TD y algunas propiedades particulares, dos algoritmos más y algunas aplicaciones. Primero definimos qué es una triangulación: Definición 4.0.1. Una triangulación de un conjunto de puntos S en el plano es una subdivisión del plano determinada por un conjunto maximal de aristas (que no se cruzan entre ellas) cuyo conjunto de vértices es S. La palabra maximal tiene el mismo sentido establecido en Preliminares (ver Fig. 4.1). Observación. Las aristas del CC de un conjunto de puntos S siempre aparece en toda triangulación de S. Observación. Todas las regiones de la subdivisión son siempre triángulos. 55

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

Figura 4.1: Triangulación maximal Observación. En relación al teorema de Jordan, tenemos que la frontera del polígono formado son las aristas de la CC, el interior de este polígono y el exterior no acotado están separados por esta frontera.

4.1.

DOS ALGORITMOS DE TRIANGULACIÓN

4.1.1.

Algoritmo de División Triangular

Presentamos este algoritmo 7 en el que vamos a utilizar el resultado obtenido en Preliminares sec. 2.5.2 y en el capítulo anterior sobre triangulación de un polígono convexo y la construcción de la CC. Asumimos por simplicidad que nuestros puntos están en posición general (definición 2.8.1), sin tres puntos colineales. Lo interesante de esto es que una triangulación de un conjunto de puntos pasa por una triangulación de un polígono convexo. La complejidad de este algoritmo no pasa de O(nlog(n)), ya que calcular la CC lleva más dificultad que verificar los puntos dentro de cada triangulo, que es del orden de O(n). Teorema 4.1.1. Tenemos a S un conjunto de k puntos en el interior y h puntos en la cápsula (CC). Si no todos los puntos son colineales, cualquier triangulación 56

4.1 DOS ALGORITMOS DE TRIANGULACIÓN

input : Un conjunto S de puntos en el plano output: La Triangulación de S inicio Encontrar la CC del conjunto de puntos; Triangular esta cápsula como un polígono; // ignorando los puntos interiores // Note que cada punto interior está estrictamente dentro de algún triángulo (y no sobre una diagonal) repeat Elija un punto interior; Dibuje aristas a los tres vértices del triángulo que lo contiene; until todos los puntos interiores se hayan acabado; fin Algoritmo 7: División triangular (AT1) de S que resulte del algoritmo 7 tiene exactamente 2k + h − 2 triángulos. Demostración. Por el teorema anterior 2.5.6 la triangulación del CC de S tiene h−2 triángulos. Si un punto interior está dentro de un triángulo, lo reemplaza por tres triángulos, incrementando la cuenta de triángulos en +2. Pero si un punto interior yace sobre una arista, el algoritmo extendido conecta este punto a los dos vértices de los triángulos en ambos lados de esta arista. Así, este punto interior divide los triángulos sobre ambos lados en dos triángulos, de nuevo incrementando la cuenta en +2. Ya que existen k puntos interiores en S, el número de triángulos resultantes del algoritmo 7 debe ser 2k + h − 2.

4.1.2.

Algoritmo Incremental

Presentamos este algoritmo 8 incrementable, similar al de la CC, en el que utilizamos el concepto de visibilidad: La complejidad en tiempo no pasa de O(n2 ), debido a la verificación de la visibi57

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

input : Un conjunto S de puntos en el plano output: La Triangulación de S inicio Ordene los puntos de S acorde a las coordenadas de x; Los primeros tres puntos determinan un triángulo; repeat Considere el próximo punto en el conjunto ordenado (similar a Hk ); conecte éste con todos los puntos previamente considerados {p1 , . . . , pk } que son visibles a p; until hasta que todo haya sido procesado; fin Algoritmo 8: Incremental AT2 lidad en cada punto insertado.

4.2.

TRIANGULACIONES Y FÓRMULA DE EULER

El número de triángulos en cualquier triangulación depende sólo del número de vértices del polígono. ¿Cuál sería la situación para un conjunto de puntos? El teorema anterior 4.1.1 muestra que cualquier triangulación de un conjunto de puntos que deriva del algoritmo 7 tiene un número fijo de triángulos, dependiente de los puntos interiores y de los puntos frontera de la CC. Mostramos ahora que este resultado es verdad para TODA triangulación de un conjunto de puntos. La demostración está en la gran relación que descubrió Euler para todo poliedro, pero que se generalizó para todo grafo plano; ya vimos algunos conceptos de grafos en Preliminares, sec. 2.10. Teorema 4.2.1. Supóngase que G un grafo plano conectado con V vértices, E 58

4.3 EL GRAFO DE INTERCAMBIOS (FLIPS) aristas y F caras (donde la cara externa es no acotada). Entonces V − E + F = 2. Esto se demuestra en el apéndice sec. 8.6. Observación. El Scan de Graham se puede alterar convenientemente para producir triangulaciones. Observación. La cota inferior para el número de triangulaciones distintas de un conjunto de n puntos es de Ω(8,65n) (ver [23, 74]) y la cota superior hasta ahora es de 30n .

4.3.

EL GRAFO DE INTERCAMBIOS (FLIPS)

Comenzamos definiendo lo que significa un Grafo de Flips, luego veremos para qué lo necesitamos. Definición 4.3.1. Para un conjunto de puntos S, el Grafo de Flips de S, es decir, GF (S), es un grafo cuyos nodos son el conjunto de triangulaciones de S. Dos nodos T1 y T2 del GF (S) están conectados por un arco si una diagonal de T1 puede ser cambiada para obtener T2 (ver Fig. 4.2). El GF (S) revela un espacio discreto de triangulaciones de un conjunto de puntos fijo, en los que se pueden visualizar las más convenientes. Existen varias cuestiones acerca de triangulaciones que pueden ser interpretados en el lenguaje del GF (S). La más básica de todas es: Si una triangulación de S puede ser transformada en otra por medio de una secuencia de intercambios o flips. En otras palabras, ¿es el GF (S) conexo? El teorema siguiente fue formulado y demostrado por Charles Lawson en 1971 (ver [48]). 59

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

Figura 4.2: Grafo Flips (GF (S)) para 6 puntos Teorema 4.3.2. El GF (S) de cualquier conjunto de puntos S en el plano es conexo. Demostración. Supongamos S un conjunto de puntos del plano con n puntos. Se ordenan los puntos de S acorde a las coordenadas x (horizontales). Si dos o más puntos comparten la misma coordenada-x, podemos siempre rotar el plano ligeramente tal que todos los puntos tengan distintas coordenadas-x. Etiquetar el orden resultante de S como {p1 , . . . , pn }. Nombramos T ∗ la triangulación obtenida desde S usando el algoritmo incremental. Nuestra meta es mostrar que cualquier triangulación T de S puede ser convertida en T ∗ usando flips. Esto demostrará la conectividad de GF (S) porque cualquier par de triangulaciones estarán conectadas por caminos al nodo T ∗ del GF (S), y así uno está conectado al otro invirtiendo los flips en uno de los caminos. Probamos esto por inducción sobre n. Cuando n = 3, el conjunto S tiene una 60

4.3 EL GRAFO DE INTERCAMBIOS (FLIPS)

Figura 4.3: Estrella de pn triangulación única, su GF (S) es un nodo único, y eso es todo. Asumamos para cualquier conjunto S con menos de n puntos, que cualquier triangulación de S puede ser hecha dentro del algoritmo incremental a otra triangulación de S mediante flips. Ahora consideremos S con n puntos ordenados {p1 , . . . , pn } y decimos que T es una triangulación de S. Decimos la “estrella” de un vértice v de una triangulación la unión de los triángulos incidentes a v. Mostraremos que por una secuencia de flips, la estrella de pn en nuestra triangulación T puede ser convertida en la estrella de pn en T ∗ (ver Fig. 4.3) Una vez que esto se realiza, lo que queda es una triangulación del conjunto de puntos S \ pn , la cual por nuestra hipótesis de inducción es convexa. Debido a que el algoritmo incremental produce un polígono convexo en cada paso del proceso, la estrella de pn en T ∗ tiene exactamente tres vértices convexos: pn y los dos vértices adyacentes a pn sobre la cápsula, llamémoslas a y b. En T ∗, los vértices entre a y b en la estrella, forman una cadena reflex (que contiene ángulos mayores a π con respecto a la estrella). Ahora, elijamos un vértice convexo v de la estrella de pn en nuestra triangulación T distinto de {pn , a, b}. Si no existe tal vértice convexo, entonces la estrella de pn en T es exactamente la estrella de pn en T ∗, y finalizamos. Debido a que v es convexo, la arista entre v y pn es una diagonal de un cuadrilátero convexo 61

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS que puede ser intercambiado. Así, un vértice menos es ahora visible para pn y el grado de pn disminuye en 1. Repita este proceso eligiendo vértices convexos. Este proceso debe terminar ya que el grado de pn disminuye en cada paso.

4.4.

LA TRIANGULACIÓN DE DELAUNAY (DELONÉ)

Esta triangulación debe su nombre a Boris Delone, un matemático ruso (ver [56]). Boris Delone sugiere una triangulación apropiada a las configuraciones cristalinas de átomos con los que trabajaba. Posteriormente se identifica esta triangulación con su nombre y esto es por las propiedades que posee frente a otro tipo de triangulación. Aquí veremos estas propiedades. Comenzamos con un problema surgido de un modelo de terreno que se ha triangulado en base a sus puntos muestrales. En la Fig. 4.4, dos conjuntos de puntos idénticos con alturas se muestran, cada uno con una triangulación diferente. Intercambiando una diagonal, cambia un estimado de elevación a otra, haciendo una gran diferencia en el mapa del terreno resultante. En la reconstrucción de terrenos, las triangulaciones elegidas son aquellas que evitan triángulos delgados mediante la maximización del ángulo más pequeño en cualquier triángulo sobre todas las triangulaciones posibles. Ahora en adelante la posición general significa que 4 puntos no son cocirculares (ver sec. 2.9.4.2). Suponemos T una triangulación de nuestro conjunto de puntos S, y supongamos que T tiene n triángulos. La secuencia de ángulos (α1 , . . . , α3n ) 62

4.4 LA TRIANGULACIÓN DE DELAUNAY (DELONÉ)

Figura 4.4: Interpolación de alturas de T es la lista de todos los 3n-ángulos de T ordenados desde el más pequeño al más grande. Usando la secuencia angular, estamos ahora en una posición para comparar dos triangulaciones diferentes de S. Recordando que por el teorema anterior 4.2.1, el número de triángulos de cualquier triangulación de S es una constante; así que todas las triangulaciones tienen secuencias angulares de la misma longitud. Definición 4.4.1. Para dos triangulaciones T1 y T2 de S, decimos que T1 es más gruesa que T2 (y escribimos T1  T2 ) si la secuencia angular de T1 es lexicográficamente más grande que T2 . En otras palabras, si (α1 , . . . , α3n ) es la secuencia angular para T1 y (β1 , . . . , β3n ) para T2 , entonces existe algún 1 ≤ k ≤ 3n donde αi = βi para todo i < k y αk > βk . Ejemplo. (20◦ , 30◦ , 45◦ , 65◦ , 70◦ , 130◦ ) es más grueso que (20◦ , 30◦ , 45◦ , 60◦ , 75◦ , 130◦ ) porque 65° > 60° en la primera posición en que ellas difieren, sin importar las entradas subsiguientes. Definición 4.4.2. Supóngase e una arista de una triangulación T , y tenemos a Q el cuadrilátero en T1 formado por los dos triángulos teniendo a e como su arista 63

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS común. Si Q es convexa, tenemos a T2 la triangulación después del intercambio de aristas en T1 . Decimos que “e” es una arista legal si T1  T2 y e es ilegal si T1  T2 . Note que intercambiar una arista e altera 6 ángulos en la secuencia angular T1 , reemplazándolas por 6 ángulos diferentes (en general) en la secuencia T2 . Así que el efecto de un flip (intercambio) es en general complejo. Pero la definición justamente depende del orden lexicográfico de las dos triangulaciones, ignorando los detalles de cómo este orden es logrado. Esto ayuda a completar esta definición afirmando que todas las aristas de la CC de una triangulación son legales. Como nuestra meta es encontrar la triangulación más gruesa, estamos intentando evitar aristas ilegales. Definición 4.4.3. Para un conjunto de puntos S, una Triangulación Deloné de S, denotada T D(S) es una triangulación que sólo tiene aristas legales. El algoritmo siguiente construye el T D(S) en una manera extraordinariamente simple.

4.5.

ALGORITMO DE INTERCAMBIO DE ARISTAS (AT3)

Dada una triangulación cualquiera, el algoritmo abre un ciclo para verificar si los triángulos generados tienen sus aristas legales (ver algoritmo 9). Debido a que las aristas ilegales están siendo intercambiadas, las secuencias angulares de las nuevas triangulaciones se incrementan estrictamente, y así la misma 64

4.5 ALGORITMO DE INTERCAMBIO DE ARISTAS (AT3)

input : Un conjunto S de puntos en el plano, en posición general output: La Triangulación Deloné de S inicio Hacer cualquier triangulación T en S; repeat if T tiene una arista ilegal then haga f lip a la arista; moverse a través del GF (S) en cualquier orden; until no queden más aristas ilegales en S; fin Algoritmo 9: Intercambio de aristas AT3 triangulación nunca puede reaparecer en este proceso. Y ya que existe sólo un número finito de nodos en el GF (S), este algoritmo debe terminar. Por construcción, la triangulación TD será más gruesa que cualquiera de sus vecinos en su GF (S). En otras palabras, será un máximo de grosor local. Pero esto no necesariamente implica que la TD será la más gruesa sobre todos los nodos del GF (S)1 . Observación. Para toda n, existe una triangulación de n puntos que requiere Ω(n2 ) flips para transformarse en la TD. Intercambiando una diagonal involucra 12 ángulos, todos ellos necesitan ser comparados en las secuencias de ángulos. Existe una prueba (y por tanto un algoritmo) más simple usando circunferencias basados en una extensión de un teorema clásico (atribuido a Thales) de la geometría plana: Teorema 4.5.1 (de Thales). Para 3 puntos P, Q, B sobre una circunferencia, A dentro y C fuera de él (ver Fig. 4.5). El ángulo ∠P AQ es más grande que ∠P BQ y a su vez es más grande que ∠P CQ.

Demostración. Decimos que O el centro del círculo, los tres segmentos OP , OQ y OB son radios y por tanto son iguales en longitud. De manera que los triángulos 1

La demostración de esto es más elaborada.

65

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

Figura 4.5: Teorema de Thales

Figura 4.6: 3 posiciones de D P OB y QOB son isósceles. Desde aquí no es difícil demostrar que sin importar la posición de B sobre el arco circular, el ángulo ∠P OQ es dos veces el ángulo ∠P BQ. Ciertamente, este es un teorema de Euclides2 . Esto puede ser usado para llegar a la misma conclusión del teorema. Consideremos ahora el circuncírculo3 de un triángulo ABC con un punto adicional fuera, sobre o dentro del circuncírculo, respectivamente, en Fig. 4.6. “Un ángulo inscrito en un círculo es la mitad del ángulo central que subtiende el mismo arco”, libro III, proposición 20 en [30]. 3 el circuncírculo es un círculo que circunscribe un polígono dado (donde éste sea posible) pasando a través de todos sus vértices. El centro del circuncírculo de un triángulo es el circuncentro (Ayuda de Maple [50]). 2

66

4.6 ALGORITMO AT4 (DIVIDE Y VENCE)

Proposición 4.5.2. Decimos que e es una arista de una triangulación, donde e = BC pertenece a los dos triángulos ABC y BCD. Entonces e es una arista legal si D está fuera del circuncírculo de ABC (a) y una arista ilegal si D está dentro del circuncírculo (c). Se excluye, por la condición de posición general si D está sobre el circuncírculo (b). Demostración. Ver Apéndice sec. 8.7.1. Basado en esta proposición, el siguiente teorema clasifica a la TD en una nueva y poderosa manera. Teorema 4.5.3 (Propiedad del círculo vacío). Tenemos a S un conjunto de puntos en posición general, donde 4 puntos son siempre extra-circulares. Una triangulación T es Deloné (TD) si y sólo si ningún punto de S está en el interior de cualquier circuncírculo de un triángulo de T . Demostración. Ver Apéndice sec. 8.7.2. Observación. Para cuatro o más puntos en el mismo circuncírculo (ej. Los vértices de un cuadrilátero o polígono) la TD no es única: cada una de las dos o más triangulaciones posibles es válida. Con todo esto, el algoritmo AT3 originado de este último teorema (en base a la primitiva Ccírculo, sec. 2.9.4.2), tendrá una complejidad en tiempo de O(n).

4.6.

ALGORITMO AT4 (DIVIDE Y VENCE)

La formulación es sencilla (en algoritmo 10). 67

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

input : Un conjunto S de puntos en el plano output: La Triangulación Deloné de S inicio Se divide recursivamente el conjunto de puntos S en dos partes de casi igual tamaño; Se calcula la TD para cada parte individualmente; Se reúnen las dos triangulaciones en un proceso de fusión corrigiendo los errores; fin Algoritmo 10: AT4 (Divide y vence) Esta idea fue revisada en 1980 para comprobar la TD y mejorada por Guibas y Stolfi en 1985. Después en 1986 Dwyer presentó una modificación y Leach presentó otra en 1992. En 1997 Cignoni, Montani, Scopigno presentaron el algoritmo Dewall (ver [19]), que hace posible el cálculo de TD para cualquier número de dimensiones. A este método, la cota superior asintótica es O(nlogn). Una buena lectura sobre TD se encuentra en [68, 20, 7, 58].

4.7.

APLICACIONES DE LA TD

1. En Topografía y afines: Un modelo digital de terreno MDT es una representación numérica de las características topográficas del terreno, a partir de las coordenadas tridimensionales de los puntos que le definen (ver [62, 36]). La superficie topográfica real se puede aproximar a una superficie matemática discreta formada por superficies elementales planas triangulares, y que se definen a partir de una muestra de los puntos de coordenadas tridimensionales. El método primero considera los puntos S sobre el plano, construye una triangulación de S y entonces eleva cada uno de los puntos de muestra 68

4.7 APLICACIONES DE LA TD

Figura 4.7: Triangulación de terreno a su correcta altura (ver Fig. 4.7). 2. Este proceso eleva cada triángulo en el plano a uno (generalmente inclinado) en 3D, suministrando un terreno lineal-a-trozos de la Tierra. 3. En Diseño e Ingeniería, los gráficos 3D de ordenador usan redes de polígonos para modelar objetos tridimensionales4 , realizar construcciones juntando polígonos para imitar la superficie del objeto. Hay dos formas de modelar un objeto: modelarlo a mano o escanearlo con un range scanner. Al escanearlo se produce un relieve de la superficie formado por puntos discretos. Para usar ese relieve hay que transformarlo en una red de triángulos. Al usar la triangulación TD como modelo tridimensional los errores de redondeo son mínimos. 4. En Seguridad Informática: el mallado de los puntos obtenidos a partir de una imagen se ejecuta a través del algoritmo de TD, el mismo que provee la reconstrucción tridimensional del rostro humano (ver Altamirano [5]) . Hay 4

Discretizar es modelar objetos geométricos continuos en base a una cantidad finita y adecuada de información (ver la Revista Bits de Ciencia de la Universidad de Chile (2013), número 9 en http://www.dcc.uchile.cl/revista ).

69

TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS muchas consideraciones sobre la geometría 3D y la captación de imágenes, ver Carlsson [14]. 5. Un algoritmo muy utilizado para la generación de mallas no estructuradas es el algoritmo de TD. En muchos casos se necesita insertar nuevos puntos y elementos para mejorar la calidad de la malla, a través de un proceso denominado refinamiento (ver Valenzuela [78] para más detalles). Sobre TD restringida ver el artículo de Bern y Eppstein [11]. 6. Encontrando todos los vecinos más cercanos es más fácil de conseguir comenzando con la TD, porque todas las aristas que conectan un sitio y su más cercano vecino debe ser una arista Deloné. 7. Consideremos el cálculo del árbol de expansión mínima euclidiana (EMST en inglés). El EMST debe ser un subconjunto de la TD (considerado como un grafo), y puede ser obtenido desde allí por aplicación de un algoritmo de grafo de un árbol de expansión mínima (MST). De hecho, todos los algoritmos conocidos EMST con buena complejidad calculan la TD primero (ver [42]). 8. Para construir grafos de Gabriel y grafos de vecindad relativa derivados de la TD, que pueden modelar redes inalámbricas dinámicas (MANets), (ver [12, 3]). 9. En el campo Artístico hemos disfrutado de las obras de Gego5 , (Fig. 4.8)

5

Se puede averiguar en http://www.fundaciongego.com/index02.html

70

4.7 APLICACIONES DE LA TD

Figura 4.8: Escultura de Gego

71

5 DIAGRAMA DE VORONOI (DV)

5.1.

BASES GEOMÉTRICAS

Ahora nos interesamos en estudiar los puntos del plano que no están en el conjunto de puntos S dado. En particular, estudiamos cuál punto de S es más próximo a un punto arbitrario que no está en S. Esto es diferente de una triangulación, en el que los puntos próximos entre sí son puntos de la misma naturaleza, de las mismas características, digamos así, mientras que aquí dos puntos son próximos pero uno de ellos puede ser una fuente, sumidero, control; la relación entre ellos es diferente1 . Veremos unos fundamentos geométricos y topológicos del DV, pasaremos al concepto de dualidad, índice de proximidad, teorema de las tejas, cálculo de promedios, y por último algunas aplicaciones. Todos los problemas de proximidad pueden ser resueltos usando una herramienta que contiene toda la información sobre la proximidad de los puntos. El diagrama es llamado así en honor a Georgy Voronoi, quien definió y estudió el caso general n-dimensional en 1908 (ver [80, 55]). Es también llamado Teselación, Descomposición, Partición Voronoi. 1

Para introducirnos al tema, podemos ver los vídeos: el “extracto” de la serie Numb3rs [29], y el fascinante “Nature_by_Numbers” de Cristóbal Vila [79].

73

DIAGRAMA DE VORONOI (DV)

Figura 5.1: Vórtices de Descartes Hay autores que señalan el uso de los DV en trabajos de Descartes de 1644 sobre el cielo, cuando afirmaba que el Universo estaba plagado de éter y materia y formado por vórtices, en esta impresionante Fig. 5.1. Seguimos aquí la exposición de Devadoss y O’rourke2 . Tenemos a S una colección de puntos en el plano, es decir S =

i=1 qi .

Sn

La idea es asignar a cada punto la

región donde ella ejerce su influencia. Definición 5.1.1. La región Voronoi abierta V or(p) de un punto p en S es V or(p) = {x ∈ R2 : kx − pk < kx − qi k} 2

En su libro ([21]). Hay buenas introducciones al tema en [39, 67]

74

(5.1)

5.1 BASES GEOMÉTRICAS para todos los puntos p = qj , qi ∈ S donde i, j = 1..n ∧ i 6= j y ||.|| es la distancia euclidiana en el plano. En palabras, V or(p) es el conjunto de todos los puntos x que son al menos más cerca de p que a cualquier otro punto qi en S. Además, V or(p) no puede estar vacío, ya que todos los puntos en un disco suficientemente pequeño centrado en el punto p debe estar en V or(p) (ver Fig. 5.2).

Figura 5.2: Discos alrededor de pi En un lenguaje topológico3 , podemos decir que esta definición de región Voronoi corresponde a la definición de conjunto abierto, y que si incluimos la frontera tenemos una región Voronoi cerrada V or(p). Definición 5.1.2. El conjunto de regiones Voronoi Reg(S) es la reunión de todos los V or(p): Reg(S) =

n [

V or(pi )

i=1

Los puntos que están sobre la frontera (o aristas Voronoi) entre las regiones V or(pi ) tienen más de un punto único más cercano. El Diagrama de Voronoi 3

En Topología de espacios métricos de la UNA, ver [26].

75

DIAGRAMA DE VORONOI (DV) (DV (S)) es la colección de estas fronteras: el conjunto de todos los puntos en el plano que tienen más de un vecino más cercano. En la Fig. 5.3, el DV corresponde a las aristas y los vértices Voronoi que parten el plano en regiones alrededor de los puntos anteriores.

Figura 5.3: Salida gráfica de DV El conjunto Reg(S) es disconexo en general y denso (Reg(S) = E 2 ). Además, como Reg(S) es numerable, implica que E 2 es separable. Si V or(p) es acotado, es decir, existe k > 0 tal que para toda x, y ∈ V or(p) la distancia d(x, y) < k, entonces la región es un polígono. Veremos si este polígono es en efecto convexo. Miremos la situación desde la perspectiva de un solo punto p en S. Si existe no más que otro punto q en S, entonces el DV simplemente será el bisector perpendicular (Fig. 5.4) del segmento pq, ver definición 2.4.3.

Figura 5.4: Hiperplanos de p y q 76

5.1 BASES GEOMÉTRICAS Este bisector corta el plano en dos regiones donde V or(p) es el semiplano de puntos que contiene a p: H(p, q) = V or(p) de (5.1). Si S tiene numerosos puntos, entonces tenemos el siguiente resultado: Teorema 5.1.3. La región Voronoi V or(p) es la intersección de todos los semiplanos H(p, q) donde q es cualquier otro punto en S. Es decir:

V or(p) =

\

H(p, q)

(5.2)

q6=p

Demostración. Se hace por inducción. Entre dos puntos p, q de S se obtiene dos regiones V or mediante un bisector y listo. Asumimos que tenemos un conjunto n de puntos con sus regiones V or(pi ). Cuando aparece otro punto digamos pn+1 , se debe cumplir lo establecido en la ecuación (5.1), por lo que se deben trazar bisectores entre pn+1 y los puntos vecinos de S que se intersecarán y formarán la región V or(pn+1 ). Se modifican también las regiones V or de estos puntos vecinos.

Para añadir a lo antes dicho, uno de los resultados fundamentales de la geometría discreta es el que sigue: Teorema 5.1.4. La intersección de cualquier conjunto (no necesariamente finito) de objetos convexos es convexa. Demostración. Supongamos {Xi | i ∈ I} una colección arbitraria de conjuntos convexos, y decimos que X su intersección. Considere puntos arbitrarios p y q en X. Por la definición de intersección, estos puntos están en todo conjunto Xi . Debido a que todo Xi es convexo, el segmento entero pq está en todo conjunto Xi y por lo tanto en su intersección X. Se desprende que X es convexo. 77

DIAGRAMA DE VORONOI (DV)

Corolario 5.1.5. Todas las regiones V or(p) son convexas. Esto implica que todas las propiedades de los polígonos convexos se aplican en V or(p). Ahora volcamos nuestra atención hacia los vértices Voronoi. Cuando existen precisamente tres puntos p, q, r en el conjunto de puntos S, el DV está formado por 3 bisectores perpendiculares de los segmentos pq, pr, qr. ¿Es posible que estos bisectores no necesariamente se encuentren en un punto, como en la Fig. 5.5?

Figura 5.5: Bisectores entre p, q, r La respuesta que es NO, se sigue de un teorema de Euclides4 . Él demostró que los bisectores perpendiculares de los lados de un triángulo-pqr en nuestro caso- deben todos pasar a través de un punto. De hecho, este punto, un vértice Voronoi, es el centro del único circuncírculo que pasa a través de los vértices de los triángulos, como en la Fig. 5.6. ¿Qué sucede con 4 o más puntos? (caso degenerado) Como se ha visto, las intersecciones de bisectores crean vértices Voronoi5 . Sin embargo, ciertamente no todas las intersecciones llegan a ser vértices Voronoi. ¿Existe una manera fácil pa4 5

Elementos, libro IV, proposición 5, en [30] En el caso de 3 o más puntos sobre una circunferencia, resulta que los bisectores de las cuerdas pasan por el centro del círculo según la proposición 1 del libro III de los Elementos de Euclides [30].

78

5.1 BASES GEOMÉTRICAS

Figura 5.6: Intersección de bisectores ra encontrar cuáles puntos del plano llegarán a ser vértices Voronoi? El siguiente teorema responde esta pregunta. Teorema 5.1.6 (Vértice). Supongamos S un conjunto de puntos con su DV (S). Un punto v es un vértice Voronoi de DV (S) si y sólo si existe un círculo centrado en v con tres o más puntos sobre su frontera y ninguno en su interior. Demostración. Si v es un vértice Voronoi, entonces éste debe ser incidente a por lo menos 3 regiones Voronoi, digamos V or(p), V or(q), V or(r). Esto implica que v debe ser equidistante desde los tres puntos p, q, r y por tanto, existe un círculo centrado en v con estos puntos en su frontera. Si otro punto está dentro de este círculo, entonces éste estaría más cerca a v, implicando que las regiones V or(p), V or(q), V or(r) no se encontrarían en v. Esto demuestra una parte del teorema. Ahora asumimos que tal círculo centrado en v existe, con al menos tres puntos p, q, r sobre su frontera. Ya que el interior del círculo es vacío, v debe estar sobre la frontera de cada una de las regiones V or(p), V or(q), V or(r). Por tanto, v es un vértice Voronoi. Ahora volvamos a entender las aristas Voronoi. Sabemos que todas las aristas 79

DIAGRAMA DE VORONOI (DV) Voronoi son partes de bisectores perpendiculares entre puntos, pero no todos estos bisectores llegan a ser aristas Voronoi. Ahora presentamos una característica geométrica que caracteriza las aristas Voronoi, análogas al teorema anterior. Teorema 5.1.7 (Arista). Supongamos S un conjunto de puntos con DV (S) y tenemos a e un subconjunto conexo del bisector entre puntos p y q de S. Entonces e es una arista Voronoi de DV (S) si y sólo si por cada punto x en e, el círculo centrado en x a través de p y q no contiene otros puntos de S en su interior o frontera (ver Fig. 5.7).

Figura 5.7: Teorema de la Arista

Demostración. Suponga que x es un punto sobre la arista Voronoi entre puntos p y q. Si el círculo centrado en x con p y q sobre su frontera contiene otro punto r, entonces x estaría en V or(r) también. Ya que esto es una contradicción de lo que significa una arista Voronoi, este círculo está libre de otros puntos. Ahora asumimos que existe un círculo vacío a través de p y q (y no a través de cualquier otro punto) con x como su centro. Entonces sabemos que kx − pk = kx − qk y kx − pk ≤ kx − rk para cualquier otro punto r de S. Por tanto, x debe yacer sobre el DV (S) como una arista o un vértice. Por el teorema del vértice 5.1.6 x no puede ser un vértice Voronoi, y así x yace sobre una arista Voronoi. 80

5.1 BASES GEOMÉTRICAS Teorema 5.1.8. Un DV (S) para un conjunto de puntos S tiene aristas de líneas infinitas si y sólo si todos los puntos de S son colineales. Demostración. Ver Apéndice sec. 8.8.1. Corolario 5.1.9. Para un conjunto de puntos S, el DV (S) es disconexo si y sólo si todos los puntos de S son colineales. Demostración. Si el DV (S) es disconexo, entonces debe existir una región Voronoi V or(p) de S que separa el plano en dos regiones disjuntas. Ya que V or(p) debe ser una región convexa por el corolario anterior, la frontera de V or(p) debe ser dos líneas paralelas. Por el teorema anterior, los puntos de S deben ser colineales. Cerramos esta parte con un resultado numérico, acotando el número total de vértices y aristas Voronoi, y mostrando que la complejidad combinatoria del diagrama es O(n). Teorema 5.1.10. Tenemos a S un conjunto de puntos con n ≥ 3. Entonces DV (S) tiene a lo más 2n − 5 vértices y 3n − 6 aristas, (ver Fig. 5.8 y el apéndice sec. 8.6). Este resultado implica que el número de vértices y aristas es lineal en el número de puntos n. Simplemente, debido a que existen

  n 2

bisectores punto-punto, la

relación podría haber sido cuadrática. La dependencia lineal sobre n significa que muchos algoritmos basados en el DV pueden correr rápidamente. Observación. Se puede describir la estructura del DV para los vértices de un polígono regular (o irregular6 ). 6

Con la condición de que sus vértices estén sobre su circuncírculo. Esto se sale de la posición general, pero se puede realizar.

81

DIAGRAMA DE VORONOI (DV)

Figura 5.8: Vértice al infinito Observación. Para cualquier conjunto de puntos S, se puede demostrar que V or(p) es una región no acotada en el plano si y sólo si p pertenece a la CC de S 7 .

5.2.

ALGORITMOS PARA CONSTRUIR EL DV

El enfoque más directo sería encontrar cada región Voronoi separadamente como una intersección de n − 1 semiplanos, usando el teorema 5.1.3. Tal construcción daría un tiempo computacional de O(n2 logn). Michael Shamos y Dan Hoey en 1975 suministraron un algoritmo divide-y-vencerás con complejidad en el tiempo de O(nlogn) . En 1985, Steve Fortune descubrió un algoritmo inteligente con la misma complejidad en tiempo O(nlogn), pero siguiendo un paradigma diferente conocido como “barrido del plano”. Presentamos un algoritmo que usa la técnica Divide y Vencerás. La idea del algoritmo consiste en dividir al conjunto S en dos partes S1 y S2 , mediante una 7

Es un problema sugerido

82

5.3 DUALIDAD Y TD línea vertical imaginaria, de tal forma que ambos conjuntos tengan casi el mismo número de puntos. Denotaremos por σ la subgráfica de Voronoi de S tal que los lados de σ están determinados por parejas de puntos pi y pj tales que pi ∈ S1 y pj ∈ S2 . Este σ será llamado el grafo frontera, ya que es el lugar geométrico de los puntos equidistantes de un punto en S1 y un punto en S2 . Esto sugiere un algoritmo de concatenamiento cuya complejidad es O(n), (ver algoritmo 11). input : Un conjunto S de puntos en el plano output: El Diagrama Voronoi de S inicio divida el conjunto S en dos partes iguales S1 y S2 ; // Usando el algoritmo de la mediana con respecto a las coordenadas-x Recursivamente aplicar el algoritmo de concatenamiento; fin Algoritmo 11: Voronoi (Divide y vence)

5.3.

DUALIDAD Y TD

Hay una maravillosa relación entre la triangulación TD y el DV, que describiremos aquí. El desarrollo histórico de estos conceptos siguió una línea directa desde el DV (redescubierto en 1908) pasando por la TD (descubierto en 1934) (de hecho, Delaunay (pronunciado Deloné) fue estudiante de doctorado de Voronoi en la Universidad de Kiev) hasta el estudio de sus propiedades (por ejemplo, la de ser la triangulación más gruesa). La unicidad del DV para un conjunto de puntos conduce inmediatamente a la misma conclusión para la TD. Mencionamos que el DV codifica proximidad de puntos a sitios o regiones V or(p). La proximidad de punto-a-punto puede ser capturada por la adyacencia de regio83

DIAGRAMA DE VORONOI (DV) nes Voronoi. Una representación conveniente de esta relación de adyacencia es el grafo dual del DV. Los nodos del grafo dual son los puntos de S, y dos puntos están conectados por un arco si ellos comparten una arista Voronoi. Debido a que el DV es dibujado sobre el plano, se desprende que el grafo dual es un grafo plano (ver 2.10.12), cuyos arcos se intersecan sólo en los puntos. Se resaltó anteriormente que tales conexiones entre puntos de S resultan ser triangulaciones (ver preliminares 2.5.3). Este resultado es un grafo plano, donde dos aristas duales no se intersecan. ¿Esto sería el caso general? Veremos. Lema 5.3.1. Supongamos A, B dos círculos con cuerdas que se cruzan propiamente. Entonces al menos un extremo de una cuerda circular está estrictamente dentro del otro círculo. Demostración. ver Apéndice sec. 8.8.2. Teorema 5.3.2. El grafo dual de líneas rectas del DV (S) es plano (ver 2.10.12). Demostración. Lo hacemos por contradicción. Asumimos que existen dos aristas p1 p2 y p3 p4 del dual de DV (S) que se intersecan. Debido al Teorema (Arista) 5.1.7 existe un punto x sobre la arista Voronoi entre p1 y p2 tal que el círculo Cx centrado en x y a través de p1 y p2 es vacío. Un círculo similar vacío Cy centrado en y existe para p3 y p4 . Por el lema anterior se mostró que estas condiciones implican que Cx o Cy es no vacío, lo cual es una contradicción. Corolario 5.3.3. Si S es un conjunto de puntos en posición general (ver 2.8.1), con 4 puntos no cocirculares, el grafo dual de líneas rectas de DV (S) es una triangulación de S. 84

5.3 DUALIDAD Y TD Demostración. Ya que 4 puntos no son cocirculares, cada vértice Voronoi tiene grado tres y por tanto corresponde a un triángulo en el dual. Siguiendo el corolario anterior, el grafo dual de líneas rectas de DV (S) se llama la triangulación dual del DV. La dualidad la podemos ver como una transformación geométrica entre grafos que asocia cada región Voronoi a un punto y asocia cada vértice Voronoi a un triángulo del dual, (ver [4] y Fig. 5.9).

Figura 5.9: Dualidad

Teorema 5.3.4. Supongamos S un conjunto de puntos en posición general, con 4 puntos no cocirculares. La triangulación dual de DV (S) es la T D(S). Demostración. El Teorema (Vértice) 5.1.6 muestra que el circuncírculo cerrado de cada triángulo en el dual de DV (S) no tiene puntos en su interior. Además, debido a que S está en posición general, el circuncírculo de cualquier triángulo en el dual de DV (S) contiene sólo los vértices de este triángulo. El Teorema (Propiedad del círculo vacío) 4.5.3 muestra que tal triangulación de S es una T D(S) (ver Fig. 5.10).

85

DIAGRAMA DE VORONOI (DV)

Figura 5.10: Dual del DV

Corolario 5.3.5. Supongamos S un conjunto de puntos en posición general, con 4 puntos no cocirculares. Entonces la T D(S) es única. Aquí, la suposición de posición general es sólo requerida para asegurar que se realiza una triangulación (ver algoritmo 12).

input : Un conjunto S de puntos en el plano output: La cápsula convexa CC de S inicio Hacer una Triangulación Deloné (TD); for cada triángulo do Hallar el circuncentro; end for cada arista do if es contigua a dos triángulos then agregar al conjunto cnt; if es exterior then agregar al conjunto ainf ; end unir los circuncentros según el conjunto cnt; Hacer puntos exteriores para las aristas en ainf ; Dibujar resultados anteriores; fin Algoritmo 12: Algoritmo dual DV

86

5.4 ÍNDICE DE PROXIMIDAD

5.4.

ÍNDICE DE PROXIMIDAD

Una vez obtenido el DV de un conjunto de sitios, se puede hallar el área de cada polígono convexo formado V or(p). A su vez, podemos calcular el “índice de proximidad” Ip: Ip = min



Ai Atotal



Para Ai = a ´reas_individuales y Atotal = a ´rea_total. Este índice muestra cuán próximos están los puntos, es decir, cuán agrupados están, si se agrupan en pequeñas áreas con respecto al área total decimos que están apiñados (Ip  1), pero si se agrupan cuando Atotal = k · Ai , con k = N °sitios la relación puede llegar a ser equitativa Ipmax =

1 k

Un ejemplo de relocalización de puntos: En la figura Fig. 5.8, vemos 5 puntos que comparten un área limitada por el borde exterior. Su índice de proximidad es Ip = 0,1599

Sin embargo, se decide hacer una distribución más equitativa del área, obteniéndose la siguiente figura Fig. 5.12, con un Ip = 0,2232 87

DIAGRAMA DE VORONOI (DV)

Figura 5.11: Puntos repartidos en una región

Figura 5.12: Puntos relocalizados

88

5.5 TEOREMA DE LAS TEJAS

5.5.

TEOREMA DE LAS TEJAS

Consultando el teorema de las tejas, o Tiling Theorem, propuesto por Lebesgue y Brouwer8 , tenemos lo siguiente: Teorema 5.5.1 (de las tejas). Si una figura n−dimensional es cubierta de cualquier manera por subregiones suficientemente pequeñas, existirán puntos que pertenezcan al menos a n + 1 de estas subregiones; además siempre es posible encontrar una configuración con regiones arbitrariamente pequeñas para la que ningún punto pertenecerá a más de n + 1 regiones. Se puede decir que la estructura DV es una de estas configuraciones en el sentido de que existen puntos donde confluyen a lo sumo n+1 regiones. En dos dimensiones sabemos que el DV tiene grado 3 (los puntos de intersección de las aristas Voronoi), mientras que en 3D el diagrama DV que se pueda construir, tiene puntos de intersección a lo sumo con 4 regiones, y así esto se puede generalizar a cualquier otra dimensión (ver Fig. 5.13).

5.6.

CÁLCULO DE PROMEDIOS EN DV

Otra aplicación interesante tomando en cuenta el área de una región V or(p) (sec. 7.2) es que ésta influye en el cálculo del promedio de una cierta magnitud de un conjunto de sitios medidores ri ubicados geográficamente, haciéndolo más verosímil. Si estos sitios están distribuidos uniformemente a lo largo de todo el r1 + r2 + . . . + rn . espacio, entonces se calcula el promedio como: q¯ = n 8

En Weisstein, Eric. "Tiling Theorem" De MathWorld. http://mathworld.wolfram.com/ TilingTheorem.html

89

DIAGRAMA DE VORONOI (DV)

Figura 5.13: DV en 3D con 4 sitios Pero si no existe una distribución regular, entonces el cálculo anterior falla. Lo que se debe hacer es calcular el área de cada región V or(ri ) y realizar el siguiente cálculo q¯ =

A1 r1 + A2 r2 + . . . + An rn A1 + A2 + . . . + An

donde Ai es el área de cada región V or(ri ) (ver [76]).

5.7.

APLICACIONES DEL DV

1. Resuelve el Problema de la Oficina Postal: Dado un conjunto de puntos de prueba (personas, etc.), encontrar la oficina postal más cercana para cada punto. Se organizan previamente las oficinas postales en una estructura (DV) facilitando la búsqueda de la oficina más cercana posible a cada punto de prueba (Chen [18]). 2. Estudios en los que hay que determinar áreas de influencia (centros hospita90

5.7 APLICACIONES DEL DV larios, estaciones de bomberos, bocas de metro, centros comerciales, control de tráfico aéreo, telefonía móvil, análisis de poblaciones de especies vegetales, etc.). Es una de las funciones de análisis básicas en los SIG o GIS, ver Gold [35]. 3. En Biología, modelar moléculas de proteínas. Hay un programa que lo muestra, que es el Voro3D, desarrollado por Franck Dupuis [24]. Modelaje de bosques (ver VOREST [2]), en biométrica. 4. Áreas como Modelos de Datos lógicos y conceptuales, Visualización, Animación y Transformación (morphing), Análisis de patrones y reconocimiento, Adelgazamiento de imágenes digitales (En Ovalles [59]). 5. Planeación de movimientos (ver Fraichard [31]), Navegación, Detección de colisiones y Evitación de obstáculos, Análisis de redes y comunicación, Agrupamiento usando varios enfoques, 6. Modelaje computacional y simulación, Estadística espacial y temporal, Procesamiento de imágenes, Además, el DV se aplica en investigación de operaciones (ver Fujita [32]), y otras áreas9 . 7. En Geofísica, Meteorología o Climatología para analizar datos distribuidos espacialmente (tales como medidas de lluvia), los DV son llamados Polígonos de Thiessen debido al meteorólogo americano Alfred H. Thiessen (ver [76]). 8. Como celdas Wigner-Seitz10 , el DV se utiliza en Ciencia de Materiales, de micro-estructuras policristalinas en aleaciones metálicas. En Minería, los polígonos de Voronoi son utilizados para estimar las reservas de materiales Según el ISVD 2012 (9° simposio internacional sobre DV en ciencia e ingeniería), ver http: //www.isvd12.rutgers.edu 10 Ver artículo en http://reference.iucr.org/dictionary/Wigner-Seitz_cell 9

91

DIAGRAMA DE VORONOI (DV) valiosos, minerales u otros recursos. 9. En Astronomía, Ramella et al [63], presenta un procedimiento objetivo y automático para detectar agrupaciones de galaxias en una exploración de imágenes de galaxias. 10. En Arquitectura (Wallner y Pottmann [81]), Diseño Ornamental (Obras de Gaudí11 como la 5.14c y una ventana de la casa Batlló, 5.14d; además ver cómo Kaplan trata el diseño en [47]), Fractales (Shirriff [75] y 5.14a) y en la misma naturaleza ( 5.14b).

11

Para saber más de sus obras, ir a http://www.antonigaudi.org

92

5.7 APLICACIONES DEL DV

(a) Fractal de Shirriff

(b) Ala de Anisóptera

93 (c) Dragón del Parque Güell de Gaudí

(d) Ventana

Figura 5.14: Fractal de Shirriff, Anisóptera, Gaudí y ventana

6 IMPLEMENTACIÓN EN SCILAB Procedemos a subdividir el problema en varias fases, siguiendo la metodología MAPS: 1. Introducción de datos 2. Cápsula Convexa CC 3. Puentes Interconexión (Divide-y-vence) 4. Triangulación TD 5. Diagrama DV 6. Prueba y verificación: Diagramas de Entradas y Salidas de datos. 7. Pruebas sobre la eficiencia. Para estas fases se desarrollaron funciones propias en conjunción con funciones de la librería básica de Scilab, descargable en [73]. Se explicará cada función, ayudado con un esquema y al final el código fuente que las relaciona a todas. Hay funciones Scilab y propias que se vuelven a utilizar en otras funciones, por lo tanto sólo se explican la primera vez que aparece1 . Ha sido de gran utilidad el siguiente “Principio de Implementación”: 1

Hay una buena introducción al Scilab en [10]. Además, Scilab acaba de cumplir 20 años, ver [25].

95

6.1 INTRODUCCIÓN DE DATOS “Si entiendes un concepto matemático suficientemente bien, entonces puedes escribir un programa que lo ejecute”2 . Muchos intentos de programación no dieron su resultado hasta entender completamente el concepto que lo sustentaba.

6.1.

INTRODUCCIÓN DE DATOS

La introducción de datos está coordinada en el siguiente diagrama de la Fig. 6.1:

Figura 6.1: Funciones para la entrada

Como se observa, para crear puntos de entrada, podemos elegir entre 4 opciones: al azar (rmt), mediante el mouse (localiz), con el mouse sobre una imagen (pvori2) o mediante una matriz de puntos previamente construida en la consola de Scilab. 2

Ver Hughes y otros[44]

96

IMPLEMENTACIÓN EN SCILAB

6.1.1.

Funciones de librería Scilab

6.1.1.1.

Cuadro Menú rep = x_choices(titulo, items)

Entradas: titulo es vector de string, items es una lista, donde cada ítem es también una lista del tipo: item = lista(“etiqueta”, por − def ecto, eleccs); por − def ecto es un entero que marca una tecla y eleccs es un vector fila de string. Salidas: rep es un vector de enteros. Descripción: Selecciona ítemes a través de listas de teclas y retorna los seleccionados.

6.1.1.2.

Estructura lista k = list(a1 , . . . , an )

Entradas: a1 , . . . , an son elementos de la lista, que son objetos arbitrarios. Salidas: k es nombre de la lista. Descripción: Es un objeto Scilab. Tiene operaciones como: extracción, inserción en índice i, agregar elemento en cola, agregar elemento en cabeza, eliminación de elemento en i, concatenación con otra lista, número de elementos, iteración.

6.1.1.3.

Tamaño de objetos n = size(A, sel)

Entradas: A es matriz o lista, sel puede ser ‘r’ (filas), ‘c’ (columnas), ‘ ∗ ’ (elementos) o ‘m’ (m-ésima dimensión). Salidas: n valor entero. Descripción: Retorna el tamaño de objetos A según la opción sel. 97

6.1 INTRODUCCIÓN DE DATOS

6.1.1.4.

Cuadro mensaje [botn] = messagebox(msg, titl, icon, butns, ismodal)

Entradas: msg es matriz de string (caracteres), titl el título, icon el icono que se ajusta al mensaje, butns los botones requeridos (1 × n vector), ismodal si es modal (varias opciones n ≥ 2 ) o no. Salidas: botn es número del botón que el usuario presionó. Descripción: Crea una ventana de dialogo con un mensaje esperando recibir respuesta de parte del usuario.

6.1.1.5.

Condicional if expre1 then instr1 elseif expri then instri ...else instrn end

Entradas: Las expresiones a ser evaluadas (expre1 , ..., expri , etc.). Salidas: La ejecución de las instrucciones correspondientes (instr1 , ..., instri , ..., instrn ). Descripción: Estructura de control. Comando para ejecución condicional, que funciona de la siguiente manera: si exprei es verdadero, se procede a las instrucciones instri ; si exprei es falso, entonces pasamos a verificar el valor de expri+1 y realizar las instrucciones instri+1 ; si todas las expri son falsas se realiza instrn como alternativa opcional.

6.1.1.6.

Control select var casei valori then instri elsei instrn end

Entradas: Variable var a ser analizada. Salidas: Ejecución de la selección. Descripción: Comando de selección. La instrucción instri será ejecutada si la variable var = valori . 98

IMPLEMENTACIÓN EN SCILAB

6.1.1.7.

Fecha f e = getdate(“s”)

Entradas: “s” es segundos (para indicar forma de salida). Salidas: f e es un escalar codificado de fecha UTC. Descripción: Obtiene la fecha y hora del reloj interno del CPU.

6.1.1.8.

Matriz aleatoria R = grand(m1 , m2 , ”uin”, lo, hi) , R = grand(“setsd”)

Entradas: m1 , m2 números enteros positivos,”uin” es abreviatura de distribución uniforme,lo y hi son enteros, “setsd” es la semilla que configura el generador base. Salidas: R es matriz aleatoria. Descripción: Retorna una matriz de enteros aleatoria m1 × m2 distribuidos uniformemente entre lo y hi incluidos.

6.1.1.9.

Evaluación H = evstr(Z)

Entradas: Z es una matriz de cadenas de caracteres (strings). Salidas: H es una matriz de expresiones. Descripción: Devuelve el resultado de la evaluación de la matriz de strings.

6.1.1.10.

Cuadro de diálogo rep = x_dialog(labels, valorini)

Entradas: labels es vector columna de string, valorini es vector de columnas de n valores iniciales string sugeridos. Salidas: rep es respuesta de usuario, vector de n columnas de string si se oprime “OK” o vacío [ ] si se oprime botón “cancelar”. 99

6.1 INTRODUCCIÓN DE DATOS Descripción: Abre diálogo para Entradas multilíneas interactivas.

6.1.1.11.

Acceso actual h = gca()

Entradas: No requiere. Salidas: h es el soporte de la entidad de ejes actual. Descripción: Obtiene el soporte de la entidad de ejes actual.

6.1.1.12.

Redondeo R = round(A)

Entradas: A es matriz real o compleja. Salidas: R es la matriz de valores enteros. Descripción: Redondea los elementos de A a los enteros más cercanos, a partir de ±0,5.

6.1.1.13.

Símbolos (symbols)

Descripción: Nombres de operadores Scilab. Son los siguientes (Fig. 6.2):

6.1.1.14.

Matrices E = [e11 , . . . , e1n ; e21 , . . . , e2n ; . . . ; em1 , . . . , emn ];

Entradas: eij es un elemento de la matriz. Salidas: E es el nombre de la matriz. Descripción: Son los objetos básicos de Scilab. Se inicializa con cualquier nombre de variable nvariable = []; . 100

IMPLEMENTACIÓN EN SCILAB

Figura 6.2: Símbolos en Scilab 6.1.1.15.

Localizador B = locate([n, f lag])

Entradas: n (número de puntos) y f lag (forma de los puntos: cruz, asterisco, otros) son valores enteros. Salidas: B es matriz de tamaño 2 × n. Descripción: Realiza selección con el ratón de un conjunto de puntos; obtiene sus coordenadas en una ventana gráfica. 101

6.1 INTRODUCCIÓN DE DATOS

6.1.1.16.

Matriz de píxeles M atplot(mi, opciones)

Entradas: mi es matriz real, opciones similares a plot2d. Salidas: Un gráfico. Descripción: Realiza un dibujo de la matriz mi en 2D a color.

6.1.1.17.

Lectura im = imread(ruta)

Entradas: string con ruta y nombre de archivo con extensión. Salidas: im es imagen gray (matriz m × n char sin signo) o imagen RGB (matriz m × n × 3 char sin signo). Descripción: Realiza lectura de imagen desde archivo situado en Archivos de programa, en la subcarpeta contrib/sivp de la carpeta Scilab3 .

6.1.1.18.

Conversión a gris B = rgb2gray(imRGB)

Entradas: Una imagen imRGB , que es hipermatriz m × n × 3. Salidas: B es matriz de tamaño m × n. Descripción: Realiza conversión de imagen RGB a tonos de grises.

6.1.1.19.

Apilamiento sz = stacksize(n)

Entradas: n es el tamaño de pila requerido dado en número de palabras de doble precisión (8 bytes cada uno), puede ser ‘max’ o ‘min’. 3

La ruta:“C : /Archivos de programa/Scilab 5,5,1/contrib/sivp/0,5,3,2 − 1/images/nombre_de_imagen + extensi´ on”

102

IMPLEMENTACIÓN EN SCILAB Salidas: sz es vector 1 × 2 (capacidad total y utilizado). Descripción: Obtiene el tamaño de apilamiento de Scilab.

6.1.2.

Menú Principal [sls, sp, coo2] = crm2(ptref, coord)

Entradas: ptref es matriz de puntos, coord es matriz de coordenadas (estos son datos predeterminados); también se puede hacer entrada de datos mediante un menú (x_choices ), en que se puede elegir datos aleatorios (rmt), mediante mouse (localiz ) o por medio de una imagen (pvori2 ). Salidas: sls es lista de objetos que dependen de la opción escogida, sp es matriz de puntos, coo2 es matriz de coordenadas. Descripción: Puede realizarse CC, puentes (o tangentes) de interconexión (TI), TD o DV (Fig. 6.3)

Figura 6.3: menú principal 103

6.1 INTRODUCCIÓN DE DATOS

6.1.3.

Puntos aleatorios [puntr, coord] = rmt()

Entradas: Coordenadas de la ventana (mínimo-izquierda y máximo-derecha) y número de puntos a insertar. Estas Entradas se piden a través de un cuadro de diálogo. Salidas: puntr es un vector de coordenadas de puntos, coord es una matriz de coordenadas de ventana (mínimo-izquierda y máximo-derecha). Descripción: Genera puntos aleatorios con distribución uniforme, en base a las coordenadas mínimas y máximas dadas.

6.1.4.

Función localizar [X, coord] = localiz()

Entradas: Coordenadas de la ventana (mínimo-izquierda y máximo-derecha) y número de puntos a insertar. Estas Entradas se piden a través de un cuadro de diálogo. Salidas: X es matriz n × 2 de puntos seleccionados, coord es una matriz de coordenadas de ventana (mínimo-izquierda y máximo-derecha). Descripción: Se generan puntos haciendo clic en la pantalla, en base a las coordenadas mínimas y máximas dadas.

6.1.5.

Puntos sobre imagen [X, coord] = pvori2()

Entradas: Se selecciona una imagen previamente almacenada en la carpeta imágenes (C:/SCI+’/contrib/sivp/0.5.3.2-1/images/nombre-de-Imagen’) del sistema Scilab, con extensión preferiblemente “.png”, con un tamaño específico (a determinar) y número de puntos a insertar. Estas Entradas se piden a través de 104

IMPLEMENTACIÓN EN SCILAB un cuadro de diálogo. Salidas: X es un vector de coordenadas de puntos, coord es una matriz de coordenadas de ventana (mínimo-izquierda y máximo-derecha). Descripción: Genera puntos de acuerdo con el mouse, sobre una imagen seleccionada.

6.1.6.

Seudocódigos y códigos fuente

1. Algoritmo rmt en seudocódigo4 (algoritmo 13) input : conjunto vacío Ø output: Conjunto de puntos puntr en el plano inicio Obtener fecha actual (semilla) con getdate; De parte del usuario se asignan las coordenadas de la ventana (coord); Además se obtienen cuántos puntos a insertar (n); Se recupera el operador de ejes con gca; // para actualizar los límites de datos con la matriz coord Generar la matriz aleatoria de puntos puntr con grand; Se ajustan los puntos generados de acuerdo a coord; fin Algoritmo 13: función rmt

2. Código fuente rmt (Listado de código 6.1) 3. Código fuente localiz (Fig. 6.4 y Fig. 6.5) 4. Código fuente de pvori2 (Listado de código 6.2) 4

Si aparecen pequeños rectángulos en los códigos de esta obra, significan matrices vacías. Al igual que si aparecen ovoides, éstas significan ausencia de parámetros de la función correspondiente. Ejemplos: puntr = [], rmt()

105

6.1 INTRODUCCIÓN DE DATOS

Listado de código 6.1: rmt-1 function [ puntr , coord ]=rmt ( ) // g e n e r a p u n t o s a l e a t o r i o s con d i s t r i b . uniforme puntr = [ ] ; coord = [ ] ; // m a t r i c e s n u l a s n=getdate ( ’ s ’ ) ; // o b t i e n e l a f e c h a a c t u a l para s e m i l l a grand ( ’ s e t s d ’ , n ) ; c oo r d=evstr ( x_dialog ( ’ c o l o q u e c o o r d s minIzq y maxDer ’ , [ ’ [ 0 0 ; 6 0 0 4 0 0 ] ’ ] ) ) ; // i n f o r m a c i o n a l u s u a r i o i f c oo rd ==[] then return end n2=evstr ( x_dialog ( ’ ¿ c u á n t o s puntos a i n s e r t a r ? ’ , ’ 10 ’ ) ) ; // p r e g u n t a a l u s u a r i o i f n2 ==[] then// s i no hay r e s p u e s t a return end a1=gca ( ) ; // o b t i e n e e l manejador de e j e s a c t u a l a1 . data_bounds=coord ; a1 . a x e s _ v i s i b l e =[ ’ on ’ , ’ on ’ , ’ on ’ ] ; // c o n f i g u r a r coordenadas p=grand ( 1 , n2 , ’ u in ’ , coord ( 1 , 1 ) , coord ( 2 , 1 ) ) ; p2=grand ( 1 , n2 , ’ u in ’ , coord ( 1 , 2 ) , coord ( 2 , 2 ) ) ; puntr2 =[p ; p2 ] ’ ; puntr=puntr2 ’ ; endfunction

106

IMPLEMENTACIÓN EN SCILAB

Figura 6.4: localiz1

Figura 6.5: localiz2

107

6.1 INTRODUCCIÓN DE DATOS

Listado de código 6.2: pvori2 function [ x2 , m1]= p v o r i 2 ( ) // b u s c a una imagen // y s e i n s e r t a n p u n t o s a s e r e v a l u a d o s x2 = [ ] ; m1 = [ ] ; // m a t r i c e s v a c í a s d i r e=x_dialog ( ’ I n t r o d u z c a nombre de f i g u r a ’ , ’ / roraima−w e i a s s i p u . png ’ ) ; i f d i r e ==[] then// s i no hay r e s p u e s t a return end s ta ck size ( ’max ’ ) ; // a j u s t e de p i l a i n t e r n a de almacenamiento im=imread ( SCI+ ’ / c o n t r i b / s i v p / 0 . 5 . 3 . 2 − 1 / images ’+d i r e ) ; // l e c t u r a Matplot ( im ) ; a1=gca ( ) ; a1 . a x e s _ v i s i b l e =[ ’ on ’ , ’ on ’ , ’ on ’ ] ; // c o n f i g u r a r coordenadas m1=a1 . data_bounds ; // s e puede l l e v a r a l a s a l i d a messagebox ( ’ i n s e r t e puntos con c l i c k i z q u i e r d o d e l mouse ’ ) ; n=evstr ( x_dialog ( ’ ¿ c u á n t o s puntos a i n s e r t a r con e l mouse ? ’ , ’ 10 ’ ) ) ; // p r e g u n t a a l u s u a r i o i f n==[] then// s i no hay r e s p u e s t a return end xc=locate ( n , 1 ) ; // l o c a l i z a p u n t o s con e l mouse x2=round ( xc ) ; endfunction

108

IMPLEMENTACIÓN EN SCILAB

6.2.

LA CÁPSULA CONVEXA (CC)

Pasamos a describir las funciones Scilab y propias usadas para la realización de la cápsula convexa ( Fig. 6.6)

Figura 6.6: funciones CC

6.2.1.

Funciones de librería Scilab

6.2.1.1.

Función convex-hull Metanet [nh, ind] = convex_hull(xy)

Entradas: xy es matriz real 2 × n de coordenadas de puntos. Salidas: nh es número entero de puntos de la cápsula; ind vector de enteros índices de los puntos de la cápsula. Descripción: Calcula la CC de xy. No se indica el algoritmo utilizado. 109

6.2 LA CÁPSULA CONVEXA (CC)

6.2.1.2.

Creador de grafos g = make_graph(nom, dir, n, colas, cabs)

Entradas: nom es nombre del grafo; dir si el grafo es dirigido o no (0-1); n, número de vértices o nodos; colas y cabs son vectores fila que representan los números de nodos en que parten las aristas (colas) y los números de nodos donde llegan (cabs). Salidas: g, grafo. Descripción: Se genera un grafo en Metanet.

6.2.1.3.

Muestra grafos N g = show_graph(G, [modo, escala, wsize])

Entradas: G, grafo; modo puede ser 0 rep0 o 0 new0 , escala = 1 por defecto, wsize vector real positivo de dimensiones [ancho, altura]. Salidas: N g, número de la ventana gráfica de salida. Descripción: Muestra una ventana gráfica.

6.2.1.4.

Ciclo f or variable = expresi´ on instr end

Entradas: La expresi´ on de la variable, que puede ser una matriz o vector para realizar instrucciones simples (instr) línea a línea. Salidas: La ejecución del ciclo. Descripción: Estructura de control, necesario para casi todos los algoritmos en Scilab. Define ciclos y los ejecuta.

6.2.1.5.

Tipo de objeto n = type(A)

Entradas: A es objeto Scilab. Salidas: n valor entero. 110

IMPLEMENTACIÓN EN SCILAB Descripción: Retorna un entero que es el tipo de A. En este algoritmo, si devuelve 15 es tipo lista, 1 es tipo matriz de doubles real o compleja.

6.2.1.6.

Trazador 1 xpolys(xpols, ypols, [draw])

Entradas: xpols, ypols son matrices del mismo tamaño, draw es vector de tamaño n , draw(i) es estilo para la polilínea i. Salidas: Una gráfica. Descripción: Dibuja un conjunto de polilíneas usando marcas o líneas punteadas. Las coordenadas de cada polilínea son guardadas en una columna de xpols y ypols.

6.2.1.7.

Trazador 2 xpoly(xv, yv, [dtype, close])

Entradas: xv, yv matrices del mismo tamaño, dtype es string estilo de dibujo, puede ser “lines” o “marks” , close = 1 indica polilínea cerrada, de lo contrario close = 0 (por defecto). Salidas: Una gráfica. Descripción: Dibuja una simple polilínea descrita por los vectores de coordenadas xv y yv. Si ellos son matrices, se consideran los vectores concatenando sus columnas.

6.2.1.8.

Título title([axes], A, [props])

Entradas: axes fuerza al título que aparezca dentro de los ejes seleccionados por axes_handle, A es string entre comillas, props son secuencias de pares de argumentos que definen propiedades de formato. Salidas: string. 111

6.2 LA CÁPSULA CONVEXA (CC) Descripción: Despliega un título sobre una ventana gráfica.

6.2.2.

Función CC [nhull, ind, graf ] = capsula(coord, puntr)

Entradas: coord es coordenadas de la ventana (abajo-izquierda y arriba-derecha) y puntr es puntos a insertar. Mediante una ventana de diálogo se obtiene el nombre del grafo resultante y si es dirigido o no. Salidas: nhull es número de vértices que forman el CC, ind es índice de vértices que forman CC, graf es el grafo que muestra el CC. Descripción: Realiza el CC mediante un procedimiento convex_hull del paquete Metanet y lo visualiza en una ventana especial para grafos.

6.2.3.

Función dibujo dibuc(ptref, li, coord)

Entradas: ptref es matriz de puntos de entrada, li es lista o matriz n × 2 de puntos-frontera de CC y coord es matriz de coordenadas de ventana. Salidas: Un gráfico. Descripción: Dibuja los puntos ptref y la CC con el operador gráfico de Scilab.

6.2.3.1.

Conversión a matriz [xmat] = li2m(li)

Entradas: li es una lista. Salidas: xmat es matriz. Descripción: Genera una matriz a partir de una lista. 112

IMPLEMENTACIÓN EN SCILAB

6.2.4.

Seudocódigos y códigos fuente

1. El seudocódigo del algoritmo capsula (algoritmo 14)

input : Un conjunto S de puntos en el plano output: La cápsula convexa CC de S inicio Pedir al usuario el nombre del grafo a crear (dire) y si es dirigido o no (nd); Se forma la matriz xy con los puntos de entrada; Aplicar la función convex_hull de Metanet a matriz xy; Se calcula el tamaño n de la matriz de índices resultantes; for índices de 1 a n − 1 do construir la matriz ari; Generar grafo (make_graph) con los elementos (dire, nd, tap, ari); Se asignan las coordenadas de los puntos de entrada a los nodos del grafo; Se muestra el grafo en una ventana Metanet; fin Algoritmo 14: capsula

2. Código fuente capsula (Listado de código 6.3) 3. El código fuente dibuc (Fig. 6.7)

6.3.

PUENTES (TANGENTES) DE INTERCONEXIÓN

Este algoritmo que usa el método Divide-y-vence calcula y muestra los puentes superior e inferior de dos conjuntos de puntos, tiene el siguiente diagrama de funciones (Fig. 6.8): 113

6.3 PUENTES (TANGENTES) DE INTERCONEXIÓN

Listado de código 6.3: capsula function [ n h u l l , ind , g r a f ]= c a p s u l a ( coord , puntr ) // c a p s u l a en metanet tap=s i z e ( puntr , ’ c ’ ) ; d i r e=x_dialog ( ’ I n t r o d u z c a nombre de g r a f o ’ , ’CC ’+string ( tap ) ) ; i f d i r e ==[] then// s i c a n c e l a n h u l l = [ ] ; in d = [ ] ; // i n i c i a l i z a c i ó n m a t r i c e s v a c i a s return end nd=evstr ( x_dialog ( ’ ¿ e s d i r i g i d o o no (1 −0)? ’ , ’ 1 ’ ) ) ; i f nd==[] then// s i c a n c e l a nd=0; end xy=[ puntr ( 1 , : ) ; puntr ( 2 , : ) ] ; [ n h u l l , i n d ]=convex_hull ( xy ) ; m=s i z e ( ind , ’ c ’ ) ; for i =1:m−1 a r i ( : , $+1)=[ i nd ( i ) ; i nd ( i + 1 ) ] ; end a r i ( : , $+1)=[ i nd (m) ; i nd ( 1 ) ] ; ari (: ,1)=[]; g r a f=make_graph( d i r e , nd , tap , a r i ( 1 , : ) , a r i ( 2 , : ) ) ; g r a f . nodes . g r a p h i c s . x=puntr ( 1 , : ) ; g r a f . nodes . g r a p h i c s . y=puntr ( 2 , : ) ; show_graph( g r a f , ’ new ’ , 1 ) ; endfunction

114

IMPLEMENTACIÓN EN SCILAB

Figura 6.8: divi-funciones

6.3.1.

Funciones de librería Scilab

6.3.1.1.

Mediana b = median(A, “c”/“r”)

Entradas: A es matriz, “c” columnas, “r” filas. Salidas: b es la mediana. Descripción: Retorna la mediana de todas las Entradas de A. En combinación con “r” se obtiene un vector fila b tal que b(j) contiene la mediana de la j-ésima columna de A. El dual es para “c”.

6.3.1.2.

Ciclo while var = expresi´ on then (instr1 ) [else (instr2 )] end

Entradas: La expresi´ on de la variable var, que puede ser una matriz o vector para realizar instrucciones instr1 , instr2 simples línea a línea. Salidas: La ejecución del ciclo. Descripción: Estructura de control. Realiza ciclos controlados por la expresión.

6.3.1.3.

Matriz y = zeros(m1 , m2 )

Entradas: m1 , m2 son enteros. 115

6.3 PUENTES (TANGENTES) DE INTERCONEXIÓN Salidas: y es matriz. Descripción: Devuelve una matriz llena de ceros.

6.3.1.4.

Máximo [b, k] = max(A, “c”/“r”), (Mínimo [b, k] = min(A, “c”/“r”))

Entradas: A es matriz, “c” columnas, “r” filas. Salidas: b es el máximo (mínimo), k es el índice del máximo (mínimo). Descripción: Combinado con “r” se obtiene un vector fila b tal que b(j) contiene el máximo (mínimo) de la j-ésima columna de A, k(j) es el índice de ese máximo (mínimo). Similar es para “c”.

6.3.1.5.

Longitud de objetos n = length(Z)

Entradas: Z es matriz de string o lista. Salidas: n es entero o matriz de enteros. Descripción: Longitud de objetos. Para matrices string, es la longitud de los caracteres de las entradas. Para listas, es la cantidad de elementos allí.

6.3.1.6.

Módulos i = modulo(n, m) e i = pmodulo(n, m)

Entradas: n, m vectores o matrices reales. Salidas: i es entero o matriz de enteros. Descripción: Calcula i = n(m´ odulo m), es decir, el resto de n dividido por m. Si n o m es negativo, entonces modulo(n, m) es negativo; mientras que pmodulo(n, m) siempre es positivo o cero. 116

IMPLEMENTACIÓN EN SCILAB

6.3.1.7.

Matriz y = ones(m1 , m2 )

Entradas: m1 , m2 enteros. Salidas: y es matriz. Descripción: Retorna una matriz llena de unos.

6.3.1.8.

Determinante e = det(x)

Entradas: x es una matriz cuadrada real o compleja. Salidas: e es un número entero. Descripción: Resuelve el determinante de la matriz cuadrada x.

6.3.2.

Función T I[ccf, ch1 , ch2 , g] = divi(ptref, coord)

Entradas: coord es coordenadas de la ventana (mínimo-izquierda y máximo-derecha) y ptref es matriz de puntos de entrada. Salidas: ccf es índice de nodos de los puentes inferior y superior, ch1 y ch2 son índices de CC izquierdo y derecho y g es el grafo resultante (Metanet). Descripción: Divide en dos un conjunto de puntos y calcula la CC de cada mitad, luego aplica algoritmo de Puentes y muestra el grafo resultante.

6.3.2.1.

Conversión li = m2li(xmat)

Entradas: xmat es una matriz de coordenadas de n puntos. Salidas: li es una lista. Descripción: Convierte matriz a lista. 117

6.3 PUENTES (TANGENTES) DE INTERCONEXIÓN

6.3.2.2.

Puente inferior [p1 , p2 , j1 , j2 ] = puen2(s1 , s2 )

Entradas: s1 , s2 son listas ordenadas en sentido reloj de CC izquierdo y derecho. Salidas: p1 , p2 son puntos, j1 , j2 indican el lugar donde están respectivamente con respecto a sus listas. Descripción: Obtiene los puntos p1 , p2 que forman el puente inferior.

6.3.2.3.

Puente superior [p1 , p2 , j1 , j2 ] = puens2(s1 , s2 )

Entradas: s1 , s2 son listas ordenadas en sentido reloj de CC izquierdo y derecho. Salidas: p1 , p2 son puntos, j1 , j2 indican el lugar donde están respectivamente con respecto a sus listas. Descripción: Obtiene los puntos que forman el puente superior.

6.3.2.4.

Conversión de índices ccf = conver(ptref, vin, vf i)

Entradas: ptref es matriz de puntos de entrada, vin y vf i son matrices del mismo tamaño con coordenadas de puntos. Salidas: ccf es matriz de índices de puntos en ptref . Descripción: Genera matriz de índices de puntos que concuerdan con valores numerados de ptref .

6.3.2.5.

Crea grafo graf = capsu(coord, ptref, ari)

Entradas: coord es coordenadas de la ventana (abajo-izquierda y arriba-derecha), ptref es matriz de puntos a insertar y ari es matriz de índices de aristas de CC. Además, se pide en una ventana el nombre del nuevo grafo y si es dirigido o no. 118

IMPLEMENTACIÓN EN SCILAB Salidas: Ventana de grafo graf . Descripción: Grafo de puntos y su CC.

6.3.2.6.

Inicio TI [sl1 , ym1 , sl2 , ym2 ] = inic(s1 , s2 )

Entradas: s1 , s2 son listas ordenadas en sentido reloj de CC izquierdo y derecho. Salidas: sl1 , sl2 son puntos extremos de inicio del algoritmo de Divide-y-vence, j1 , j2 son los índices de estos puntos en s1 y s2 . Descripción: Inicializa los puntos de la CC para realizar algoritmo de Puentes de Interconexión. Los algoritmos desci1 y desci2 son similares, aquí mostramos a desci1:

6.3.2.7.

Descendente (ascendente) [si2 , jd2 ] = desci1(sl2 , slc1 , slc2 , jd)

Entradas: sl2 es lista de CC, slc1 (fijo), slc2 son puntos extremos, jd es índice de slc2 . Salidas: si2 es nuevo punto ascendente (descendente) desde lista sl2 (sl1 ), jd2 es índice de si2 . Descripción: Algoritmo ascendente (descendente) desde sl2 derecho (sl1 izquierdo) para encontrar nuevo punto extremo. Requiere un algoritmo de prueba si el nuevo punto es el definitivo, si no es, vuelve a realizar el algoritmo.

6.3.2.8.

Primitiva CCW d = deti(xmat)

Entradas: xmat es una matriz de coordenadas de 3 puntos (dimensiones 3 × 2). El punto de búsqueda se inserta en la tercera fila. Salidas: d es un número de punto flotante. 119

6.4 LA TRIANGULACIÓN DELONÉ Descripción: Los dos primeros puntos p1 , p2 forman un vector de referencia en que el tercer punto p3 será al que se determine su orientación, a la derecha de p1 p2 si d > 0 o a su izquierda si d < 0.

6.3.2.9.

Prueba sale = prueb2(sl1 , sl2 , slc1 , slc2 , j1 , j2 )

Entradas: sl1 , sl2 son listas de CC izquierda y derecha, slc1 y slc2 son puntos de prueba con sus índices j1 y j2 en cada lista. Salidas: sale es variable booleana. Descripción: Hace la prueba si realmente slc1 y slc2 constituyen el puente, si no, la variable sale es falsa.

6.3.3.

Seudocódigos y códigos fuente

1. El seudocódigo para divi (algoritmo 15) 2. El código fuente de divi es (Listado de código 6.4) 3. El código fuente de conver es (Fig. 6.9) 4. El código fuente de puen2 (similar a puens2 ) es (Fig. 6.10) 5. El algoritmo inic tiene código fuente (Fig. 6.11) 6. Código fuente de desci1 (similar a desci2 ) (Fig. 6.12) 7. Ahora el código fuente de prueb2 (Fig. 6.13)

6.4.

LA TRIANGULACIÓN DELONÉ

El diagrama correspondiente es (Fig. 6.14) 120

IMPLEMENTACIÓN EN SCILAB

Figura 6.7: dibuc código fuente

input : Un conjunto S de puntos en el plano output: Puentes que unen las CC de S1 y S2 inicio Extraer tamaño de puntos de entrada; // con la función size Obtener mediana de puntos de entrada; for cada punto i do if (coordenada x)<mediana then lisiz←punto i; else lisd←punto i; end Calcular tamaños de lisiz, lisd; if los tamaños son mayores a 3 then aplicar convex_hull; Aplicar algoritmo puente inferior (puen2); Aplicar algoritmo puente superior (puens2); Extraer índices de nodos de los puntos obtenidos (conver); Dibujar en Scilab; Se crea un grafo correspondiente en Metanet ; fin Algoritmo 15: divi(TI) 121

6.4 LA TRIANGULACIÓN DELONÉ

Listado de código 6.4: divi function [ c c f , c1h , c2h , g3 ]= d i v i ( puns , c o o r d ) // d i v i d e en dos un c o n j u n t o de p u n t o s y a p l i c a l a CC a cada uno l i s i z = [ ] ; l i s d e r = [ ] ; g3 = [ ] ; // i n i c i a l i z a m a t r i c e s punts=puns ’ ; s=s i z e ( punts , ’ r ’ ) ; // i n i c i a l i z a medi=median( punts ( : , 1 ) ) ; // o b t i e n e l a mediana for i =1: s i f punts ( i ,1) < medi then l i s i z ( $ +1 ,:)= punts ( i , : ) ; // p u n t o s de p a r t e i z q u i e r d a else l i s d e r ( $ +1 ,:)= punts ( i , : ) ; // p u n t o s de p a r t e d e r e c h a end end lisiz (1 ,:)=[]; lisder (1 ,:)=[]; tmi=s i z e ( l i s i z , ’ r ’ ) ; tmd=s i z e ( l i s d e r , ’ r ’ ) ; // tamaños i f tmi>3 then [ nh1 , i n d 1 ]=convex_hull ( l i s i z ’ ) ; // f u n c i o n Metanet , CC i z q u i e r d a c1= l i s i z ( ind1 , : ) ; c l 1=m 2 l i ( c1 ) ; else c1= l i s i z ; c l 1=m 2 l i ( l i s i z ) ; end i f tmd>3 then [ nh2 , i n d 2 ]=convex_hull ( l i s d e r ’ ) ; // f u n c i o n Metanet , CC d e r e c h a c2=l i s d e r ( ind2 , : ) ; c l 2=m 2 l i ( c2 ) ; else c2=l i s d e r ; c l 2=m 2 l i ( l i s d e r ) ; end [ p3 , p4 , j3 , j 4 ]= puen2 ( c l 1 , c l 2 ) ; // a l g o r i t m o p u e n t e i n f e r i o r [ p1 , p2 , j1 , j 2 ]= puens2 ( c l 1 , c l 2 ) ; // a l g o r i t m o p u e n t e s u p e r i o r v i n =[p1 ’ , p3 ’ ] ; v f i =[p2 ’ , p4 ’ ] ; d i b u c ( l i s i z , c l 1 , c o o r d ) ; // para d i b u j a r en c o n s o l a dibuc ( l i s d e r , cl2 , coord ) ; dibu2 ( p3 , p4 , c o o r d ) ; dibu2 ( p1 , p2 , c o o r d ) ; c c f=c o n v e r ( puns , vin , v f i ) ; // v a l o r numerico de p u n t o s a nodos c1h=c o n v e r ( puns , c1 ’ , [ c1 ( 2 : $ , : ) ’ , c1 ( 1 , : ) ’ ] ) ; //CC i z q u i e r d a c2h=c o n v e r ( puns , c2 ’ , [ c2 ( 2 : $ , : ) ’ , c2 ( 1 , : ) ’ ] ) ; //CC d e r e c h a p i n t e r =[ c c f , c1h , c2h ] ; g3=capsu ( coord , puns , p i n t e r ) ; // c o n v e r s i o n a Metanet endfunction

122

IMPLEMENTACIÓN EN SCILAB

(a) conver-1

(b) conver-2

Figura 6.9: conver

123

6.4 LA TRIANGULACIÓN DELONÉ

(a) puen2-1

(b) puen2-2

Figura 6.10: puen2

124

IMPLEMENTACIÓN EN SCILAB

(a) inic-1

(b) inic-2

Figura 6.11: inic

125

6.4 LA TRIANGULACIÓN DELONÉ

(a) desci1-1

(b) desci1-2

Figura 6.12: desci1

126

IMPLEMENTACIÓN EN SCILAB

(a) prueb2-1

(b) prueb2-2

(c) prueb2-3

Figura 6.13: prueb2

127

6.4 LA TRIANGULACIÓN DELONÉ

Figura 6.14: TD funciones Describimos los algoritmos implementados y del sistema Scilab:

6.4.1.

Funciones de librería Scilab

6.4.1.1.

Triangulizador Metanet [nut, a] = mesh2d(x, y, [f ront])

Entradas: x, y coordenadas de n puntos; f ront vector que define la frontera (opcional). Salidas: nut matriz de enteros de los números de los nodos de cada triángulo; a es matriz de conexiones entre nodos. Descripción: Realiza triangulación de n puntos del plano. No especifica que sea Deloné, pero experimentalmente se han obtenido resultados de este tipo.

6.4.1.2.

Conversor a matriz k = matrix(Z, n, m)

Entradas: Z es un vector o matriz de enteros o reales, n es número de filas, m es número de columnas. 128

IMPLEMENTACIÓN EN SCILAB Salidas: k es vector o matriz. Descripción: Transforma Z en una matriz n × m apilando columna a columna las Entradas de Z.

6.4.1.3.

Operador de figura por defecto sdf () ; f = gdf ()

Entradas: No requiere. Salidas: f es operador de la figura (gráfica) por defecto. Descripción: Reconfigura el modelo de la figura para obtener valores por defecto.

6.4.1.4.

Trazador xf polys(xpol, ypol, [f ill])

Entradas: xpol, ypol son matrices del mismo tamaño (n × m), f ill es vector de tamaño m o n × m. Salidas: Un gráfico. Descripción: Llena un conjunto de polígonos del mismo tamaño definidos por las dos matrices xpol y ypol. Las coordenadas de cada polígono son guardadas en cada columna de xpol y ypol. Los polígonos pueden ser rellenados con un color dado (uniforme) o con interpolación de colores.

6.4.1.5.

Descarta repetidos [N, k] = unique(A, ”r”/”c”)

Entradas: A es vector o matriz, ”r” (filas), ”c” (columnas). Salidas: N vector o matriz, k es vector de enteros. Descripción: Despliega un vector o matriz que retiene las únicas entradas de A en orden ascendente; con “r” retorna las únicas filas de A en orden ascendente lexicográfico; k contiene la posición de las primeras entradas únicas encontradas. 129

6.4 LA TRIANGULACIÓN DELONÉ

6.4.1.6.

Ordenación [B, k] = gsort(Z, opc, dir)

Entradas: Z es un vector o matriz de enteros o reales, opc puede ser “r” para filas o “c” para columnas, dir puede ser creciente “i” o decreciente “d”. Salidas: B es un vector o matriz ordenado, k es un vector o matriz de índices de Z, de manera que B == Z(k). Descripción: Realiza un ordenamiento mediante el conocido algoritmo quicksort.

6.4.1.7.

Grafo simple gr1 = graph_simp(gr)

Entradas: gr es grafo, posiblemente multigráfica Metanet. Salidas: gr1 es grafo. Descripción: Devuelve el grafo gr1 simple no dirigido correspondiente al multigrafo gr. Elimina rizos en gr, reemplaza aristas dirigidas con no dirigidas y reemplaza aristas múltiples con aristas simples.

6.4.2.

Triangulizador [T r, ing] = trit(coord, ptref )

Entradas: coord es matriz de coordenadas, ptref es matriz de puntos de entrada. Salidas: T r es matriz de índices 3 × n , ing es matriz de índices de generadores. Descripción: Obtiene triangulación TD mediante mesh2d y la dibuja.

6.4.3.

Puntos-índices vecinos [ig2 , ig3 ] = sdel(ing)

Entradas: ing es matriz de índices de generadores. Salidas: ig2 , ig3 son matrices de índices. 130

IMPLEMENTACIÓN EN SCILAB Descripción: Realiza una ordenación de los generadores para visualizar los puntos vecinos de cada generador.

6.4.4.

TD en Metanet graf = delon(ptref, ing)

Entradas: ptref es matriz de puntos, ing es matriz de índices de generadores. Salidas: graf es estructura de grafo Metanet. Descripción: Obtiene una estructura de grafo TD a partir de los puntos de entrada y los índices respectivos.

6.4.4.1.

Intercambio [p3 , p4 ] = inteb(p1 , p2 )

Entradas: p1 , p2 son puntos iniciales. Salidas: p3 , p4 son puntos finales. Descripción: Intercambia los puntos p1 y p2 en una misma fila de una matriz o vector.

6.4.4.2.

Modificación aristas th = icamth(ini)

Entradas: ini es matriz de índices de aristas. Salidas: th es matriz de índices de aristas. Descripción: Verifica si es necesario intercambiar alguna cola o cabeza en aristas orientadas.

6.4.5.

Seudocódigos y códigos fuente

1. El seudocódigo para la TD general es (ver algoritmo 16) 131

6.4 LA TRIANGULACIÓN DELONÉ 2. El código fuente de trit es ( 6.15a y 6.15b) 3. El código fuente de sdel es ( 6.15c) 4. El código fuente de delon es (Fig. 6.16)

input : Un conjunto S de puntos en el plano output: La Triangulación Deloné de S inicio Función trit para realizar la Triangulación; Dibujar en Scilab (opcional); Función sdel para organizar índices de nodos vecinos; Función delon para representar en Metanet; fin Algoritmo 16: TD seudocódigo

132

IMPLEMENTACIÓN EN SCILAB

(a) trit-1

(b) trit-2

(c) sdel

Figura 6.15: códigos trit, sdel

133

6.4 LA TRIANGULACIÓN DELONÉ

(a) delon1

(b) delon2

Figura 6.16: delon

134

IMPLEMENTACIÓN EN SCILAB

6.5.

EL DIAGRAMA DE VORONOI

El diagrama de funciones asociadas es (Fig. 6.17)

Figura 6.17: DV- funciones

6.5.1.

Funciones de librería Scilab

6.5.1.1.

Elimina elemento l(i) = null()

Entradas: l(i) es un elemento de lista l. Salidas: l es una lista sin elemento i. Descripción: Borra elemento i de lista l.

6.5.1.2.

Búsqueda en filas in = vectorf ind(A, vec, ‘r’/‘c’)

Entradas: A es matriz, vec es un vector, ‘r’ (filas), ‘c’ (columnas). Salidas: in es vector fila que contiene índices. Descripción: Encuentra en una matriz A filas o columnas que son idénticas a vec.

6.5.1.3.

Sistema de ecuaciones lineales [x0 , kerZ] = linsolve(Z, b)

Entradas: Z es una matriz de reales n × m, b es un vector n × 1. Salidas:x0 es un vector real (una solución particular), kerZ es matriz real m × k (núcleo de Z). 135

6.5 EL DIAGRAMA DE VORONOI Descripción: Resuelve ecuaciones lineales, dando todas las soluciones de la forma Z · x + b = 0, donde x = x0 + kerZ · w, w es arbitrario. 6.5.1.4.

Signo R = sign(A)

Entradas: A matriz real o compleja. Salidas: R es matriz real o compleja. Descripción: Retorna la matriz hecha de los signos de A(i, j) o A./abs(A) 6.5.1.5.

Absoluto t = abs(x)

Entradas: x es matriz o vector real (punto flotante) o complejo. Salidas: Matriz o vector real t. Descripción: Calcula el valor absoluto de x. 6.5.1.6.

Frecuencias m = tabul(A, “d”/“i”)

Entradas: A es vector o matriz, ”d”, orden decreciente (por defecto) de valores de A, ”i”, orden creciente de valores de A. Salidas: m es matriz de dos columnas. Descripción: Retorna m(i, 2) que es el número de ocurrencias de m(i, 1) que son los distintos valores de A. 6.5.1.7.

Cambia a string R = string(A)

Entradas: A es matriz booleana, entera, real o compleja. Salidas: R es la matriz de valores string. Descripción: Convierte A en una matriz string. 136

IMPLEMENTACIÓN EN SCILAB

6.5.1.8.

Intersección [v, ka, kb] = intersect(a, b, ”r”/”c”)

Entradas: a, b son vectores o matrices, ”r” para filas y ”c” para columnas. Salidas: v es el vector o matriz, ka, kb son índices de v en a, b respectivamente. Descripción: Obtiene el vector o matriz ordenado de valores comunes de a, b.

6.5.1.9.

Diferencias [v, ka] = setdif f (a, b)

Entradas: a, b son vectores. Salidas: v es un vector con la misma orientación de a, ka es índice de v en a. Descripción: Obtiene un vector ordenado que retiene las entradas de a que no están en b.

6.5.1.10.

Nota sobre comandos de depuración (debugging):

Para llegar a depurar los algoritmos, usamos los siguientes comandos de Scilab: whereami, pause, resume, abort, los cuales fueron esenciales para detectar fallos en la implementación.

6.5.2.

Función dual DV [vv, ino, gdv] = dvtri(coord, ptref )

Entradas: ptref es matriz de puntos de entrada, coord es matriz de coordenadas. Salidas: vv es matriz de vértices Voronoi, ino es matriz de índices de aristas Voronoi, gdv es grafo en Metanet. Descripción: Función dual que realiza el DV a partir de ptref . 137

6.5 EL DIAGRAMA DE VORONOI

6.5.2.1.

Tabla de triángulos contiguos [cont, lime] = dvdu(T g)

Entradas: T g es matriz 3 × n de triángulos de la Triangulación Deloné. Salidas: cont es tabla de triángulos contiguos, numerados por fila, lime es tabla de triángulos que poseen aristas como parte de la CC. Descripción: Genera tablas de triángulos contiguos a partir de T g. Los triángulos contiguos comparten una arista, como máximo hay 3 contiguos y como mínimo ningún triángulo, pero dvdu funciona a partir de dos triángulos. Además, produce una tabla con las aristas de los triángulos que forman el CC.

6.5.2.2.

Mediatriz de dos puntos [ar, br, vmed] = mdtz(p1 , p2 )

Entradas: p1 , p2 son coordenadas de puntos de entrada. Salidas: ar es pendiente de segmento, br corte con eje vertical, vmed : (xmed , ymed ) es punto medio entre p1 y p2 . Según ymed = ar · xmed + br. Descripción: Realiza la mediatriz5 entre dos puntos p1 , p2 . Sólo proporciona la pendiente, un punto de corte y punto medio, no delimita el segmento.

6.5.2.3.

Circuncentros cent = tresp(ptref, T r)

Entradas: ptref es matriz de puntos de entrada, T r es matriz de índices de triángulos de TD. Salidas: cent es matriz de circuncentros y radios. Descripción: Calcula circuncentros dados 3 puntos de un triángulo a la vez. 5

Ver en Apéndice en sec. 8.1

138

IMPLEMENTACIÓN EN SCILAB

6.5.2.4.

Mediatrices y circuncentros [arp, wor] = medcc(punt, lime, cct)

Entradas: punt es matriz de puntos, lime es matriz de índices de triángulos CC, cct es matriz de circuncentros. Salidas: arp es matriz de circuncentros de triángulos CC, wor es matriz de pendientes de aristas “infinitas” (desde un punto de vista teórico, pero se interceptan en la ventana de visualización). Descripción: Encuentra las aristas “infinitas” correspondientes a las aristas de triángulos que están en el CC.

6.5.2.5.

Numeración de vértices indi = vervo(cont)

Entradas: cont es matriz de índices de triángulos contiguos. Salidas: indi es matriz de índices de aristas. Descripción: Realiza un arreglo más adecuado de triángulos contiguos, para formar aristas.

6.5.2.6.

Matriz de aristas Voronoi lice = voroc(ini, vv)

Entradas: ini es lista de índices de aristas Voronoi, vv es matriz de vértices Voronoi. Salidas: lice es matriz de aristas Voronoi. Descripción: Obtiene la matriz de aristas a partir de los índices ini y vv. 139

6.5 EL DIAGRAMA DE VORONOI

6.5.2.7.

Dibujo de Diagrama dvgraf (coord, puntr, arp, lice)

Entradas: coord es matriz de coordenadas, puntr es matriz de puntos de entrada, arp es matriz de vértices CC, lice es matriz de aristas Voronoi. Salidas: Una gráfica. Descripción: Dibuja el Diagrama Voronoi.

6.5.2.8.

Aristas alrededor de puntos [vevor, delau] = poliv3(vorli, ptref )

Entradas: ptref es matriz de puntos de entrada, vorli es matriz de aristas Voronoi.6 Salidas: vevor es matriz de aristas relacionadas a cada punto de ptref , delau es matriz de puntos vecinos a cada punto en ptref . Descripción: A través de vectorf ind, realiza una extracción de aristas Voronoi asociadas a cada punto de entrada.

6.5.2.9.

Verifica fórmula test = ceuler(nvr, nenv, npt, nliv, ini)

Entradas: nvr, nenv, npt, nliv son tamaños de vértices Voronoi, Cápsula Convexa CC, puntos de entrada y aristas respectivamente; ini es numeración de vértices. Salidas: test es booleano, además se produce en consola un mensaje de advertencia o de comprobación. Descripción: Comprueba la Fórmula de Euler modificada para el DV (ver Apéndice en sec. 8.6) y despliega un mensaje y un valor booleano. Se puede usar este programa para auto-correcciones. 6

función en preparación

140

IMPLEMENTACIÓN EN SCILAB

6.5.2.10.

Grafo Metanet graf = vorg(ptref, coor, ini, vv)

Entradas: ptref es matriz de puntos de entrada, coor es matriz de coordenadas, ini es matriz de índices de aristas, vv es matriz de vértices de aristas Voronoi. Salidas: graf es estructura de grafo Metanet. Descripción: A partir de los datos se crea una estructura de grafo del DV.

6.5.3.

Seudocódigos y códigos fuente

Presentamos algunos seudocódigos de DV. 1. El seudocódigo general para el DV es (ver algoritmo 17) input : Un conjunto S de puntos en el plano output: El Diagrama de Voronoi de S inicio Aplicar mesh2D para obtener Triangulación Deloné (TD); Función dvdu para obtener tabla de triángulos contiguos; Función tresp para obtener circuncentros; Función medcc para obtener mediatrices desde vértices CC; Función vervo para obtener índices de vértices Voronoi; Función sdel para corregir vértices repetidos; Función voroc para obtener matriz de aristas Voronoi; Función dvgraf para dibujar Diagrama en Scilab; Función ceuler para comprobar la fórmula de Euler; Función vorg para representar en Metanet; fin Algoritmo 17: DV -seudocódigo 2. Código fuente de dvtri (Fig. 6.18) 3. Código fuente de dvdut (Listado de código 6.5) 4. Código fuente de tresp (Fig. 6.19) 5. Código fuente de medcc (Listado de código 6.6) 141

6.5 EL DIAGRAMA DE VORONOI

(a) dvt1

(b) dvt2

Figura 6.18: DV dual

142

IMPLEMENTACIÓN EN SCILAB

Listado de código 6.5: dvdut function [ c o n t i , l i m e ]=dvdu (Tg) //Tg=m a t r i z −columna de t r i a n g s TD // l i m e=t r i a n g u l o s de CC, c o n t=t a b l a de t r i a n g s c o n t i g u o s l i m e = [ ] ; l c n=l i s t ( ) ; // i n i c i a l i z a m a t r i z y l i s t a v a c i a s [m, n]= s i z e (Tg ) ; //m==3 por d e f i n i c i o n for i =1:n c o n t = [ ] ; // i n c i a l i z a m a t r i z v a c i a i f i 1 then// a c o t a m i e n t o por i z q u i e r d a l=i −1; for k=1: l [ pct , k i 2 ]=unique ( [ Tg ( : , i ) ; Tg ( : , k ) , ’ r ’ ] ) ; d i f=s i z e ( ki2 , ’ r ’ ) ; i f d i f ==4 then// examinar c o n t ( $+1)=k ; // t r i a n g u l o k c o n t i g u o a i end end end mf=s i z e ( cont , ’ r ’ ) ; i f mf==1 then// c o n t i g u o a un t r i a n g u l o v i n=i n t e r s e c t (Tg ( : , i ) , Tg ( : , c o n t ) , ’ r ’ ) ; // v e r t i c e s comunes v d i= s e t d i f f (Tg ( : , i ) , v i n ) ; // e l v e r t i c e CC l i b r e c o n t ( $ +1: $ + 2 ) = [ 0 ; 0 ] ; // c o m p l e t a r con c e r o s e l p o l i n o m i o c o n t l i m e ( : , $+1)=[ v d i ; v i n ( 2 , : ) ; v i n ( 1 , : ) ; i ] ; // ya que t i e n e dos l a d o s CC e l s e i f mf==2 then// c o n t i g u o a dos t r i a n g u l o s v i n 2=i n t e r s e c t (Tg ( : , c o n t ( 1 , : ) ) , Tg ( : , c o n t ( 2 , : ) ) , ’ r ’ ) ; // e n t r e l o s t r i a n g u l o s c o n t i g u o s vd2= s e t d i f f (Tg ( : , i ) , v i n 2 ) ; // l o s dos v e r t i c e s CC l i b r e vu=i n t e r s e c t (Tg ( : , i ) , vin2 , ’ r ’ ) ; // puede h a b e r c o n t i g u o s e n t r e s i c o n t ( $ +1)=0; l i m e ( : , $+1)=[ vd2 ; vu ; i ] ; end l c n (0)= c o n t ; end// gran f o r c o n t i=l i 3 m ( l c n ) ; // c o n v i e r t e l i s t a a m a t r i z l i m e ( : , 1 ) = [ ] ; // b o r r a primera columna endfunction 143

6.5 EL DIAGRAMA DE VORONOI

(a) tresp-1

(b) tresp-2

Figura 6.19: tresp

144

IMPLEMENTACIÓN EN SCILAB

Listado de código 6.6: medcc function [ arp , wor ]= medcc ( puntr , a r i , c e n t ) // p u n t r=m a t r i z de p u n t o s // a r i=i n d i c e s CC, c e n t=m a t r i z c i r c u n c e n t r o s t r p=evstr ( x_dialog ( ’ Coloque a j u s t e s u p e r i o r ; i n f e r i o r ’ , [ ’ [ 1 e1 ’ ; ’ 1 e1 ] ’ ] ) ) ; i f t r p ==[] then// s i c a n c e l a l a o p e r a c i o n arp = [ ] ; wor = [ ] ; // s a l i d a s de m a t r i c e s v a c i a s return end coo ( 1 , : ) = [ − 1 0 0 0 , − 1 0 0 0 ] ∗ t r p ( 2 ) ; // a j min coo ( 2 , : ) = [ 1 e4 , 1 e4 ] ∗ t r p ( 1 ) ; // a j max , s e a j u s t a n c o o r d e n a d a s m=s i z e ( a r i , ’ c ’ ) ; arp=zeros ( 4 ,m) ; wor=zeros ( 4 ,m) ; f o r j =1:m v1=puntr ( : , a r i ( 1 , j ) ) ; // e x t r a e r p u n t o s que forman CC v2=puntr ( : , a r i ( 2 , j ) ) ; v3=puntr ( : , a r i ( 3 , j ) ) ; i f v1 (1 ,1) > v2 ( 1 , 1 ) then [ v1 , v2 ]= i n t e b ( v1 , v2 ) ; end [ arow , brow , vmed]=mdtz ( v1 , v2 ) ; wor ( : , j )=[ arow ; brow ; vmed ’ ] ; // p e n d i e n t e s de m e d i a t r i c e s arp ( 1 : 2 , j )= c e n t ( 1 : 2 , a r i ( 4 , j ) ) ; // p o s i c i o n r e l a t i v a t z =[v1 ’ ; v2 ’ ; v3 ’ ] ; // d e f i n i d o e l t r i a n g u l o d=d e t i ( t z ) ; i f sign ( arow)>0 then i f d>0 then i n=l i n s o l v e ( [ arow , − 1 ; 0 , − 1 ] , [ brow ; c o o r ( 2 , 2 ) ] ) ; // donde Ax+B=0 i f ( i n (1) < c o o r ( 2 , 1 ) ) & ( i n (1) > c o o r ( 1 , 1 ) ) then arp ( 3 : 4 , j )= i n ; else i n 2=arow ∗ c o o r ( 2 , 1 ) + brow ; arp ( 3 : 4 , j )=[ c o o r ( 2 , 1 ) ; i n 2 ] ; end e l s e // d cambiada i n=l i n s o l v e ( [ arow , − 1 ; 0 , − 1 ] , [ brow ; c o o r ( 1 , 2 ) ] ) ; // donde Ax+B=0 i f ( i n (1) < c o o r ( 2 , 1 ) ) & ( i n (1) > c o o r ( 1 , 1 ) ) then arp ( 3 : 4 , j )= i n ; else i n 2=arow ∗ c o o r ( 1 , 1 ) + brow ; arp ( 3 : 4 , j )=[ c o o r ( 1 , 1 ) ; i n 2 ] ; end end e l s e // s i g n o arow cambiado i f d>0 then i n=l i n s o l v e ( [ arow , − 1 ; 0 , − 1 ] , [ brow ; c o o r ( 2 , 2 ) ] ) ; // donde Ax+B=0 i f ( i n (1) < c o o r ( 2 , 1 ) ) & ( i n (1) > c o o r ( 1 , 1 ) ) then arp ( 3 : 4 , j )= i n ; else i n 2=arow ∗ c o o r ( 1 , 1 ) + brow ; arp ( 3 : 4 , j )=[ c o o r ( 1 , 1 ) ; i n 2 ] ; end e l s e // p o s i c i o n d cambiada i n=l i n s o l v e ( [ arow , − 1 ; 0 , − 1 ] , [ brow ; c o o r ( 1 , 2 ) ] ) ; // donde Ax+B=0 i f ( i n (1) < c o o r ( 2 , 1 ) ) & ( i n (1) > c o o r ( 1 , 1 ) ) then arp ( 3 : 4 , j )= i n ; else i n 2=arow ∗ c o o r ( 2 , 1 ) + brow ; arp ( 3 : 4 , j )=[ c o o r ( 2 , 1 ) ; i n 2 ] ; end end end end endfunction

145

6.5 EL DIAGRAMA DE VORONOI 6. El código fuente de vervo (Fig. 6.20)

(a) vervo-1

(b) vervo-2

Figura 6.20: vervo

7. El código fuente de voroc (Fig. 6.21) 8. El código fuente de dvgraf (Listado de código 6.7) 9. El código fuente de ceuler (Listado de código 6.8) 10. El código fuente de vorg (Fig. 6.22) 11. Código fuente de crm2 (Fig. 6.23 y Fig. 6.24) 146

IMPLEMENTACIÓN EN SCILAB

Figura 6.21: voroc

(a) vorg-1

(b) vorg-2

Figura 6.22: vorg

147

6.5 EL DIAGRAMA DE VORONOI

Listado de código 6.7: dvgraf function d v g r a f ( coord , puntr , arp , l i c e ) // s a l i d a s ó l o g r á f i c a v=s i z e ( puntr , ’ c ’ ) ; w=s i z e ( arp , ’ c ’ ) ; xpolys ( puntr ( 1 , : ) , puntr ( 2 , : ) , − 2 ∗ ones ( 1 , v ) ) ; // d i b u j a l o s p u n t o s l i n e=zeros ( 2 , 2 ∗w ) ; // i n i c i a l i z a r for i =1:w l i n e ( 1 , i )=arp ( 1 , i ) ; // s e arma una m a t r i z l i n e adecuada l i n e ( 2 , i )=arp ( 3 , i ) ; end for l =1:w l i n e ( 1 , l+w)=arp ( 2 , l ) ; l i n e ( 2 , l+w)=arp ( 4 , l ) ; end xpolys ( l i n e ( : , 1 : w) , l i n e ( : , w+1:2∗w) ,1+ ones ( 1 ,w ) ) ; // l i n e a s i n f i n i t a s t=s i z e ( l i c e , ’ c ’ ) ; l i n 2=zeros ( 2 , 2 ∗ t ) ; // i n i c i a l i z a r for i =1: t l i n 2 ( 1 , i )= l i c e ( 1 , i ) ; // s e arma una m a t r i z adecuada l i n 2 ( 2 , i )= l i c e ( 3 , i ) ; end for l =1: t l i n 2 ( 1 , l+t )= l i c e ( 2 , l ) ; l i n 2 ( 2 , l+t )= l i c e ( 4 , l ) ; end xpolys ( l i n 2 ( : , 1 : t ) , l i n 2 ( : , t +1:2∗ t ) , 1 ∗ ones ( 1 , t ) ) ; // d i b u j a l i n e a s −v g=gca ( ) ; // o b t i e n e e l manejador de e j e s a c t u a l g . data_bounds=coord ; //minx , miny ; mix , may g . a x e s _ v i s i b l e =[ ’ on ’ , ’ on ’ , ’ on ’ ] ; // a j u s t a coordenadas t i t l e ( ’ Diagrama de Voronoi ’ , ’ f o n t s i z e ’ , 4 , ’ e d g e c o l o r ’ , ’ r e d ’ ) ; endfunction

148

IMPLEMENTACIÓN EN SCILAB

Listado de código 6.8: ceuler function pas=c e u l e r ( nvr , nenv , npts , n l i v , i n i f ) // v e r i f i c a l a f o r m u l a de E u l e r // nvr , nenv , npts , n l i v son tamaños de v e r t i c e s −v ,CC, puntos , a r i s t a s // i n i f e s numeracion de v e r t i c e s pas=%f ; c ont =[ i n i f ( 1 , : ) , i n i f ( 2 , : ) ] ; m1=tabul ( c ont ) ; t a=s i z e (m1, ’ r ’ ) ; suma=0; for i =1: t a d=m1( i , 2 ) ; i f d==1 then suma=suma+1; end end a1=nvr−suma+npts ; a2=n l i v +1; ne= ’ numero completo de e n v o l t u r a convexa ( a p a r t e ): − ’+string ( nenv ) ; nav= ’ numero de a r i s t a s Voronoi := ’+string ( n l i v )+ ’+1 ’ ; npg= ’ numero de puntos g e n e r a d o r e s :+ ’+string ( npts ) ; nvx= ’ numero de v e r t i c e s extremos :− ’+string ( suma ) ; nvv= ’ numero de v e r t i c e s Voronoi : ’+string ( nvr ) ; i f a1==a2 then disp ( ne , nav , npg , nvx , nvv ) ; pas=%t; else disp ( ’ v e r i f i c a c e u l e r . s c i ’ ) ; end endfunction

149

6.5 EL DIAGRAMA DE VORONOI

(a) crm2-1

(b) crm2-2

(c) crm2-3

Figura 6.23: crm2-menu principal 150

IMPLEMENTACIÓN EN SCILAB

(a) crm2-4

(b) crm2-5

Figura 6.24: crm2-final

151

6.6 PRUEBA Y VERIFICACIÓN: ENTRADAS Y SALIDAS DE DATOS

6.6.

PRUEBA Y VERIFICACIÓN: ENTRADAS Y SALIDAS DE DATOS

6.6.1.

Datos técnicos de la computadora usada

Sistema operativo: M S W indows XP Home SP 3. Procesador: Intel Atom CP U N 270 @ 1,60 GHz, Memoria: 1,0 GB RAM .

6.6.2.

Menú principal

Cuando se teclea crm2() aparece el menú principal (Fig. 6.25)

Figura 6.25: menú En esta ventana ya están preseleccionadas las opciones “De forma aleatoria” y “Cápsula Convexa”, que el usuario cambiará a su conveniencia con el mouse. Al seleccionar se oprime “OK” para obtener los resultados.

6.6.3.

Generación de datos de entrada

1. Algoritmo aleatorio rmt(), desde consola de Scilab: 20 puntos ( 6.26a) 2. Algoritmo localiz(), desde consola: 20 puntos ( 6.26b) 152

IMPLEMENTACIÓN EN SCILAB 3. Algoritmo pvori2(), desde consola: 20 puntos ( 6.26c)

6.6.4.

Entradas y Salidas de CC

Usaremos los mismos datos de entrada, modo predeterminado, para mayor control. Con 10 puntos ( 6.27a) Sale más información en la consola: slis(1) es el número de puntos en la CC, slis(2) es el índice de los puntos en CC, numerados de acuerdo a los puntos de entrada en sp2, slis(3) es la estructura de grafo que se mostró al inicio ( 6.27c)

6.6.5.

Entradas y Salidas de puentes (TI)

Con 10 puntos ( 6.28a) En consola: slis(1) son los índices en columna de los puntos en sp2 que forman los puentes superior e inferior; slis(2) son los índices de los puntos que forman la CC izquierda; slis(3) son los índices de los puntos que forman la CC derecha; slis(4) es la estructura de grafo para los puentes (ver 6.28b)

6.6.6.

Entradas y Salidas de Triangulación Deloné (TD)

Con 15 puntos (Fig. 6.29) En consola: slis(1) son índices de puntos en columna de sp3 que forman un triángulo; slis(2) y slis(3) son índices ordenados de puntos en sp3 que tienen vecinos a otros puntos de sp3; slis(4) es la estructura de grafo de la triangulación (Fig. 6.30) 153

6.6 PRUEBA Y VERIFICACIÓN: ENTRADAS Y SALIDAS DE DATOS

(a) rmt con 20 puntos

(b) localiz con 20 puntos

154

(c) pvori2 con 20 puntos

Figura 6.26: 20 puntos con rmt, localiz, pvori2

IMPLEMENTACIÓN EN SCILAB

(a) CC (Scilab)

(b) CC (Metanet)

(c) CC- consola

Figura 6.27: CC Salidas

155

6.6 PRUEBA Y VERIFICACIÓN: ENTRADAS Y SALIDAS DE DATOS

(a) TI-en Scilab

(b) TI-consola

(c) TI-salida-consola

156

Figura 6.28: TI-salida

IMPLEMENTACIÓN EN SCILAB

6.6.7.

Entradas y Salidas de Diagrama Voronoi (DV)

Con 15 puntos (Fig. 6.31) En consola: 1. Se muestra un registro relacionado con la fórmula de Euler (salida de ceuler). En este caso se muestra el número de vértices Voronoi (28), le restamos 7, que es el número de vértices extremos (que pueden ser los duales de aristas CC, lo que varia si se recorta la gráfica) y le sumamos el número de puntos de entrada (generadores), que son 15, dando como resultado 36. Se compara con el número de aristas que exactamente es 35 y se suma 1, lo que comprueba la identidad de Euler. 2. La matriz de coordenadas. El punto mínimo se elige casi siempre (0, 0) y el máximo es (600, 400). 3. La matriz de puntos de entrada de tamaño 2 × 15 4. slis(1) es la matriz de vértices Voronoi. 5. La salida slis(2) es índices de aristas Voronoi (inicio y fin). 6. slis(3) es la identificación del grafo correspondiente (Fig. 6.32).

6.7.

PRUEBAS SOBRE LA EFICIENCIA

Se realizaron pruebas con 5, 10, 15, 20 puntos, lo que sirvió para generar una gráfica que muestra el comportamiento de algunas funciones en cuanto al tiempo de computación con respecto a la cantidad de puntos. No se pudo establecer un análisis del código fuente de funciones del paquete Metanet (convex_hull, mesh2d, entre otras) porque están bloqueadas. Describimos la función timer() de 157

6.7 PRUEBAS SOBRE LA EFICIENCIA Scilab:

6.7.1.

Temporizador timer(); f unci´ on(); timer()

Entradas: La ejecución de una f unci´ on implementada en Scilab. Salidas: Una medida de tiempo en segundos, con precisión de 10 nseg. Descripción: Retorna el tiempo CPU desde la precedente llamada a timer(). El tiempo CPU es el número de ciclos de procesador usados para hacer una cantidad determinada de cálculos. No es totalmente equivalente al tiempo en el mundo real, ya que no toma en cuenta los procesos de fondo que pueda ralentizar la computadora que se esté usando. Seleccionamos las funciones más representativas y las comparamos.

6.7.2.

Comparador de funciones timu(xe, ye)

Entradas: xe es vector de abscisas comunes a todas las funciones, ye es vector de ordenadas de cada función de entrada. Salidas: Un gráfico Scilab. Descripción: Realiza las gráficas de cada función según lo obtenido en timer o en cualquier otra fuente. Al colocarlas en una misma escala permite su comparación y análisis.

6.7.3.

Comparación entre capsula, divi, trit, delon, vorg

La estructura de capsula, divi, delon, vorg es similar en cuanto al comportamiento asintótico (Fig. 6.33). Se puede apreciar que los algoritmos utilizados son muy 158

IMPLEMENTACIÓN EN SCILAB eficientes, por el orden de O(log(n)).

6.7.4.

Función dvtri

El comportamiento asintótico aparece con una tendencia parecida a la descrita teóricamente de O(nlogn) (Fig. 6.34).

6.8.

NOTAS ACERCA DE LA IMPLEMENTACIÓN

Muchos algoritmos quedaron sin explicar explícitamente. Puede ser necesario hacer pruebas de estabilidad de algoritmos, para verificar cómo se comportan a la hora de hacer implementaciones dinámicas. Además, para la prueba de eficiencia se necesita una mayor cantidad de puntos para establecer un buen análisis de la complejidad en tiempo, con computadores de mayor capacidad. Al Parecer, el paradigma de los algoritmos adaptativos o de salida sensitiva, que dependen tanto de la entrada como de la salida (con estimación probabilística quizás) sea el modelo dominante (frente al modelo de salida independiente) y pueda definir una mejor cota de complejidad en tiempo. Una de las cosas que se tomó en cuenta fue la simetría para la realización de algoritmos recursivos en la implementación.

159

6.8 NOTAS ACERCA DE LA IMPLEMENTACIÓN

Figura 6.29: TD Scilab

160

IMPLEMENTACIÓN EN SCILAB

(a) TD-1

(b) TD-2

(c) TD-3

Figura 6.30: TD- consola

161

6.8 NOTAS ACERCA DE LA IMPLEMENTACIÓN

(a) DV- Scilab (gráfica)

(b) DV- Scilab (Metanet)

Figura 6.31: DV- salida 162

IMPLEMENTACIÓN EN SCILAB

(a) DV-1

(b) DV-2

163 (c) DV-3

Figura 6.32: DV- consola

6.8 NOTAS ACERCA DE LA IMPLEMENTACIÓN

Figura 6.33: comparación de 5 funciones

Figura 6.34: tiempo versus N° puntos en dvtri

164

7 CONCLUSIONES Y RECOMENDACIONES

7.1.

CONCLUSIONES

La Geometría Computacional ha provisto muchas herramientas para resolver problemas a nivel tecnológico (robótica, morfología, sistemas geográficos, etc.). En el país es necesario crear o reforzar los grupos de cómputo (con computadores entrelazados en un Sistema Nacional de Ciencia y Tecnología) que diseñen soluciones que puedan favorecer la industria y las necesidades de la población, para un mejor aprovechamiento de los recursos disponibles. Es de la mayor importancia para el matemático en formación hacer uso de lenguajes de programación, software y sus estructuras asociadas, como un laboratorio virtual para experimentar y probar las ideas. Scilab y Geogebra son dos ejemplos al alcance de todos. Se ha llegado a las siguientes conclusiones, en base a este trabajo: Se han descrito en forma general las bases de la Geometría Computacional, a saber, la geometría plana, aunque con la tarea pendiente de generalizarla 165

CONCLUSIONES Y RECOMENDACIONES desde el punto de vista de la geometría proyectiva, los temas interesantes de la computabilidad, ya que es lo que ha abierto las compuertas de las muy útiles computadoras, análisis de algoritmos, primitivas geométricas y teoría de grafos. Se han descrito varias estructuras de datos utilizadas en Scilab, que usa primordialmente matrices, listas usadas como pilas o colas, las estructuras de grafos y diferentes comandos y funciones. Se ha realizado un análisis de los algoritmos utilizados en la CC, TD y DV. Hay por supuesto mucho por desarrollar e implementar, en vista hacia la OOP. Se logró implementar satisfactoriamente estos algoritmos en Scilab. Desde el punto de vista de la Geometría Plana, al crear la Cápsula Convexa (CC) se generan segmentos que forman un polígono convexo, en la creación de la TD se generan muchos más segmentos que forman una cantidad determinada de triángulos por la fórmula de Euler, en la creación del DV no sólo se generan segmentos, sino que además se generan puntos, formando una combinación de polígonos convexos que llena todo el espacio Q × Q computacional. El algoritmo más eficiente para construir la cápsula convexa es el de T. Chan, pero se implementó aquí los algoritmos de Graham y Jarvis1 , que son la base para el ya mencionado. Los algoritmos de Graham y Jarvis no pueden compararse en cuanto a su complejidad computacional, ya que uno es de salida independiente y otro es de salida sensitiva. Va a depender de la configuración de los puntos de entrada. 1

No se incluye sus códigos fuentes en este trabajo, sin embargo están en el CD

166

7.1 CONCLUSIONES El algoritmo más eficiente para construir la Triangulación Deloné (TD) es el que sigue el camino dado por el algoritmo de Graham, modificado para construir una triangulación general, y empleando el algoritmo de Intercambio de Aristas. Hay otra forma de implementar la TD por el algoritmo de deWall (ver [19]), pero no alcanzó el tiempo de hacerlo ni de compararlo. Además, se utilizó una función del paquete Metanet que realiza una triangulación en el plano, que luego se comprobó que era TD. El algoritmo más eficiente para construir el Diagrama de Voronoi (DV) es el que sigue el concepto de dualidad, obteniéndose a partir de la TD con un cuidadoso algoritmo que no aumenta la complejidad computacional. Se gastó mucho tiempo tratando de implementar el DV usando el método Divide y Vence, pero no hubo resultados satisfactorios en Scilab. Los diagramas generados concuerdan en un 100 % con los generados por Geogebra. El teorema de Jordan relaciona muy bien la envoltura convexa (CC) y la Triangulación. La frontera del polígono generado (CC) sería el ∂P que separa el conjunto de puntos dentro del polígono del exterior. En el interior puede haber cualquier configuración, pero la más adecuada para muchas aplicaciones es la Triangulación y mucho mejor si es Deloné (TD). Para el Diagrama de Voronoi (DV), el Teorema de Jordan funciona en cada polígono convexo V or(p), pero no en los que forman polígonos no acotados. Lo interesante del caso es que la frontera ∂(V or(p)) es parte de la frontera de la unión de todos los V or(p). Si utilizamos esta gran frontera, que es el DV, no hay separación entre interior y exterior, es decir, el Teorema de Jordan no se aplica. 167

CONCLUSIONES Y RECOMENDACIONES No siempre la diagonal más pequeña de un cuadrilátero divide a dos triángulos que cumplan con la condición Deloné. Si el cuadrilátero está dentro de un círculo ocurre que la diagonal mayor cumple con la condición Deloné (Fig. 7.1).

Figura 7.1: Diagonales en un cuadrilátero Se observó que el número de aristas al infinito en un DV es equivalente al número de puntos que forman la CC del conjunto de puntos inicial. Estas aristas al infinito forman los polígonos no acotados del DV, aunque para efectos de la Fórmula de Euler sec. 8.6, estos polígonos se acotan por un “punto” ubicado en el infinito. Una vez obtenido el DV de un conjunto de sitios, podemos calcular el “índice de proximidad” Ip (ver Apéndice sec. 5.4) Se encontró una relación útil del Diagrama de Voronoi n-dimensional con el Teorema de las Tejas (ver Apéndice sec. 5.5) El área de regiones V or(p) es útil para efectuar promedios (ver Apéndice sec. 5.6). Hay una interesante conexión entre TD y CC en una dimensión más alta, descubierta por Kevin Brown en 1979, y perfeccionada por Herbert Edelsbrunner y Raimund Seidel en los principios de los 80. El corazón de esta 168

7.2 RECOMENDACIONES relación involucra al paraboloide z = x2 + y 2 (ver Devadoss [21]). En cuanto a la estabilidad2 , ya que la entrada está dada en números enteros (pero dentro de la APF) que representan píxeles, en el caso de la CC, KS, TD toleran las perturbaciones en la notación de punto flotante. Para el caso del DV sí hay una sensibilidad a los pequeños cambios en la entrada, por lo que se considera necesario especificar los puntos de entrada con precisión menor a un píxel. Sin embargo, gran parte de la inestabilidad está fuera del rango de la ventana que el usuario ha determinado.

7.2.

RECOMENDACIONES

Experimentar las implementaciones con conjuntos de más de 50 puntos. Realizar un programa que calcule el área de un polígono convexo (dado en sec. 8.3). Implementar la CC, TD, DV en la geometría hiperbólica plana y en la elíptica3 (Fig. 7.2). Implementar la CC, TD, DV en el espacio tridimensional (3D) y en dimensión n. Se puede hacer una representación 3D con la versión más reciente de Geogebra. Adaptar la implementación de estas estructuras mediante la Programación Orientada a Objetos (OOP en inglés).

2 3

Por estabilidad nos referimos al grado de atenuación de los errores producidos en la entrada Ver [13] y la pagina de Jason Davies http://www.jasondavies.com.

169

CONCLUSIONES Y RECOMENDACIONES

Figura 7.2: TD y DV en un disco de Poincaré

170

8 APÉNDICE

8.1.

MODO DE ENCONTRAR LA MEDIATRIZ DE UN SEGMENTO

Se dan dos puntos: P 1(x1 , y1 ) y P 2(x2 , y2 ). Calcularemos la recta mediatriz entre y2 − y1 , y la recta estos puntos. La fórmula de la pendiente de una recta es: m = x2 − x1 perpendicular tiene como pendiente m⊥ = −1/m siempre y cuando m 6= 0 Esta recta pasa por el punto medio de P1 y P2: x0 =

x1 +x2 2

y y0 =

y1 +y2 2

Por ecuación punto-pendiente: y − y0 = m⊥ (x − x0 ) Igualando a cero y ordenando: y = m⊥ x + (−m⊥ x0 + y0 ). Tenemos y = m⊥ x + b⊥ donde b⊥ = y0 − m⊥ x0 .

8.2.

ALGORITMO QUICKSORT

Algoritmo básico para los valores de un arreglo (array) con un solo subíndice: 171

APÉNDICE 1. Paso de partición: Tome el primer elemento del arreglo desordenado y determine su ubicación final (posición pivot) en el arreglo clasificado, es decir, todos los valores a la izquierda del elemento en el arreglo son menores que él, y todos los valores a la derecha del elemento en el arreglo son mayores que él. Ahora, tenemos el elemento en su ubicación principal y dos subarreglos desordenados. 2. Paso recursivo: Realiza el paso 1 en cada subarreglo desordenado. Cada vez que se realiza el paso 1 en un subarreglo, se coloca otro elemento en su ubicación final dentro del arreglo ordenado, y se crean dos arreglos desordenados. Cuando un arreglo consiste en un sólo elemento, ya éste se encuentra en su ubicación final. El tiempo de ejecución sería:

T (n) =

      

n≤1

O(1)

   

  O(n) + T (pivot − l) + T (r − pivot) n > 1 

(8.1)

donde O(1) el tiempo para el caso base, O(n) es el barrido de los elementos del arreglo, n = r − l + 1 es la longitud del arreglo, T (pivot − l) y T (r − pivot) son los tiempos correspondientes a las dos partes del arreglo. Si suponemos una permutación aleatoria, entonces la esperanza sobre el punto de partición se sitúa l+r en , por lo que la ecuación anterior se aproxima como: 2

T (n) =

      

172

O(1)

n≤1

   

  O(n) + 2T ( n2 ) n > 1 

8.3 ÁREA DE UN POLÍGONO con una duración total de O(nlog(n)), similar al cálculo de la complejidad “divide y vence”, ver sec. 8.5. En resumen el algoritmo 18. input : Una matriz 2 × n de puntos en el plano output: La matriz 2 × n ordenada según un pivote inicio Se fija un elemento que servirá de pivote (con coordenada-y mínima); while no esté ordenado i do Se obtiene el elemento pi ; se verifican todos los puntos a la derecha (o izquierda); for cada punto j do if CCW >0 then punto pi está antes del j; else si ocurre lo contrario pi está después del j; intercambiar los lugares; break end end end fin Algoritmo 18: La función principal Quicksort

8.3.

ÁREA DE UN POLÍGONO

Demostremos que A = 21 |

i=1 (xi yi−1

Pn

− xi−1 yi )| donde x0 = xn ∧ y0 = yn ∧ n ≥ 3.

Demostración. Comenzamos con el caso inicial n = 3: 3 1 X 1 A = (xi yi−1 − xi−1 yi ) = |(x1 y3 − x3 y1 ) + (x2 y1 − x1 y2 ) + (x3 y2 − x2 y3 )| 2 i=1 2



=

1 2











x1 x3





y1



+

y3



x2 x1



y2



+

y1



x3 x2



y3





y2



=

1 2











x1 x3



y1



−

y3



x1 x2



y1



−

y2



x2 x3 173



y2





y3



APÉNDICE

=

1 2











x2 x3



y2



−

y3



x1 x3



y1



+

y3



x1 x2



y1





y2



=

1 2









x1 y 1 1 x2 y 2 1 x3 y 3 1









que se asemeja a la fórmula para hallar el área de un triángulo, (Fig. 8.1).

Figura 8.1: Triangulo con sus vértices Para n = k tenemos Ak =

1 2

P k i=1 (xi yi−1



− xi−1 yi ) para el polígono de k lados.

Ahora Ak+1 = Ak + At donde At es el área del triangulo de vértices l, l + 1, k + 1 (Ver la Fig. 8.2). Desarrollando Ak+1 tenemos

Ak+1 =

1

x1 yk − xk y1 + ... + xl yl−1 − xl−1 yl +xl+1 yl − xl yl+1 + ... + 2

Figura 8.2: Paso inductivo 174

8.4 TEOREMA DE LA COMBINACIÓN CONVEXA eliminando los dos términos de Ak+1 con los dos primeros términos de At , obtenemos =

1 kx1 yk − xk y1 + ... + xl yl−1 − xl−1 yl + xk+1 yl − xl yk+1 + xl+1 yk+1 − xk+1 yl+1 + ...k 2

que es semejante a la fórmula para Ak con k = k + 1.

;

El área se puede expresar mejor como una sumatoria de determinantes:

A=

1 2

n

X

(xi yi−1

i=1



− xi−1 yi )

=

1 2





X

n

det

i=1



xi xi+1

yi

yi+1

donde xn+1 = x1 ∧ yn+1 = y1 en el último determinante, con n ≥ 3. Implementar esto es un problema propuesto en el capítulo anterior.

8.4.

TEOREMA DE LA COMBINACIÓN CONVEXA

Teorema. 3.1.2: Para un conjunto de puntos S = {p1 , ..., pn }, la CC de S es el conjunto de todas las combinaciones convexas de S. Demostración. Sea M el conjunto de las combinaciones convexas de S. Formalmente (se generaliza la ecuación (2.3)), M = {λ1 p1 + ... + λn pn | λi ≥ 0,

X

λi = 1}

(8.2)

Para demostrar que CC(S) = M , mostramos que CC(S) ⊆ M y CC(S) ⊇ M . 175

APÉNDICE Parte I CC(S) ⊆ M : Es fácil ver que M contiene S. Si λi = 1 y todas las otras son 0, obtenemos pi en M . Así, si podemos probar que M es una región convexa, entonces CC(S) ⊆ M ya que CC(S) es la intersección de todas las regiones convexas que contienen S. Sea x, y dos puntos cualquiera en M ; necesitamos verificar que el segmento xy está en M . Ya que x está en M , este se puede escribir como x = λ1 p1 + ... + λn pn donde λi ≥ 0 y

P

(8.3)

λi = 1. De la misma manera, y puede ser escrito con

y = λ01 p1 + ... + λ0n pn donde λ0i ≥ 0 y

P 0 λ

i

(8.4)

= 1. Ademas, cualquier punto del segmento xy puede ser

expresado como αx + βy = α

X

λi pi + β

X

λ0i pi =

(αλi + βλ0i )pi

X

para α ≥ 0, β ≥ 0 y α + β = 1. Debido a que (αλi + βλ0i ) ≥ 0, y X

(αλi + βλ0i ) = α

X

λi + β

X

λ0i = α · 1 + β · 1 = 1

se sigue que el segmento xy está en M . Se concluye que M es una región convexa. parte II: CC(S) ⊇ M . Cualquier punto en M , que puede ser expresado como en (8.3), está en CC(S) por inducción sobre n. Es claro que esto es verdad para cuando n = 1; entonces M = CC(S) = p1 . Asumamos que esto es verdad pa176

8.5 COMPLEJIDAD DE LA TÉCNICA “DIVIDE Y VENCE” ra todo conjunto de puntos S 0 con menos de n puntos, y ahora consideramos el conjunto S con n puntos, p1 , ..., pn . Por la hipótesis de inducción, cualquier punto x = λ01 p1 + ... + λ0n−1 pn−1 está en CC(S 0 ) ⊂ CC(S) si y sólo si λ0i ≥ 0 y λi/(1−λn )

P 0 λ

i

= 1. Ahora, elegimos λ0i =

debido a que λ1 + ... + λn−1 = 1 − λn . Nótese que aún satisfacemos las

condiciones dadas arriba. Y además CC(S 0 ) ⊂ CC(S), sabemos que x está en CC(S). Debido a que pn y x están ambas en CC(S), y ya que CC(S) es convexa, entonces cualquier punto en el segmento xpn está en CC(S). Así que (1 − λn )(

λn−1 λ1 p1 + ... + pn−1 ) + λn pn = λ1 p1 + ... + λn pn 1 − λn 1 − λn

está en CC(S), donde

P

λi = 1.

Este teorema da una considerable profundidad de lo que constituye la cápsula convexa, pero no es aún “efectivamente computable”.

8.5.

COMPLEJIDAD DE LA TÉCNICA “DIVIDE Y VENCE”

Obtendremos una cota para esta técnica. Ya que éste es recursivo, si T (n) es el tiempo total para n puntos, entoncesT (n) = 2T (n/2) + O(n), donde T (n/2) es el tiempo de cada mitad del conjunto S de puntos y O(n) es el paso de la concatenación. El caso base es T (1) = b unidades de tiempo y T (n) = 2T (n/2) + 177

APÉNDICE O(n), T (n/2) = 2T (n/4) + O(n/2), T (n/4) = 2T (n/8) + O(n/4) ...T (n/2s−1 ) = 2T (n/2s ) + O(n/2s−1 )

agrupando T (n) = 2(2T (n/4) + O(n/2)) + O(n) = 4T (n/4) + 2O(n/2) + O(n) = 4T (n/4) + 2O(n) aprovechando las propiedades de linealidad de O(n). Aún esto es igual a = 4(2T (n/8) + O(n/4)) + 2O(n) = 8T (n/8) + 4O(n/4) + 2O(n) = 8T (n/8) + 3O(n) = ... De manera que, en general, de (8.5) T (n) = 2s−1 (2T (n/2s ) + O(n/2s−1 )) + (s − 1)O(n) = 2s T (n/2s ) + sO(n) pero n = 2s , por lo tanto = 2s T (1) + sO(n) = n · b + log2 n · O(n) = bn + O(nlog2 n) T (n) = O(nlog(n)) Esta es la cota superior para la técnica Divide-y-Vencerás. 178

(8.5)

8.6 LA FÓRMULA DE EULER

8.6.

LA FÓRMULA DE EULER

El más importante de los descubrimientos en Topología es una fórmula que relaciona el número de vértices, de aristas y de caras de un poliedro simple (o un grafo plano), la cual fue observada desde 1640 por Descartes y re-descubierta y utilizada por Euler en 1752. Teorema (Fórmula de Euler). Sea G un grafo conectado con v : v´ ertices, e : aristas, f : sitios sobre el plano (donde la cara externa es no acotada). entonces v−e+f =2

(8.6)

Demostración. Usaremos inducción sobre el numero de aristas. Si e = 0 entonces G es un vértice aislado sobre el plano y v − e + f = 1 − 0 + 1 = 2. Por otro lado, elija cualquier arista e de G. Si e conecta dos vértices de G, contraiga (reduzca) esta arista, reduciendo v y e en una unidad. Si e es incidente a sólo un vértice (esto es, e es un lazo separando dos caras), elimine esta arista, reduciendo f y e en una unidad. En cualquier caso, el nuevo grafo permanece conectado y la fórmula se sigue por inducción.

8.6.1.

REFERENTE A LA TRIANGULACIÓN DE UN CONJUNTO DE PUNTOS

Teorema (triangulación). Sea S un conjunto de puntos, con h puntos en la CC y k en el interior, y así v = h + k es el total de puntos. Si no todos los puntos son colineales, entonces cualquier triangulación de S tiene exactamente 2k + h − 2 triángulos y 3k + 2h − 3 aristas. 179

APÉNDICE Demostración. Sea T una triangulación del conjunto de puntos S, y sea t el numero de triángulos de T . Sabemos que T subdivide el plano en t + 1 caras, t triángulos dentro de la cápsula y la cara fuera de la cápsula. Cada triangulo tiene 3 aristas, y la cara externa tiene h aristas. Como cada arista toca exactamente 2 caras, entonces 2e = 3t + h

(8.7)

Aplicando la fórmula de Euler (8.6) con f = t + 1, resulta lo siguiente 1 v − (3t + h) + (t + 1) = 2 2 Resolviendo para t t = 2v − 4 − h + 2 = 2v − h − 2 = 2(h + k) − h − 2 = 2k + h − 2 para las aristas e = (h + k) + [(2k + h − 2) + 1] − 2 = 2h + 3k − 3

8.6.2.

DERIVACIÓN DE RELACIONES AFINES

Tenemos la ecuación original (8.6) donde v : v´ ertices, e : aristas, f : sitios. Ademas, como característica de los grafos tipo Voronoi o Deloné, de la ecuación (2.9) v ≤ 2/3 e de allí salen dos relaciones que involucran las relaciones entre e ↔ f y v ↔ f : sustituyendo en (8.6): e + 2 − f ≤ 2/3 e e − 2/3 e = 1/3 e ≤ f − 2 180

8.6 LA FÓRMULA DE EULER y tenemos que e ≤ 3f − 6. Sustituimos ahora e en (8.6): v ≤ 2/3(v + f − 2) 3/2

v − v = 1/2 v ≤ f − 2

y así tenemos v ≤ 2f − 4

8.6.3.

EL CASO DE UN DIAGRAMA DE VORONOI (DV)

Para poder aplicar la ecuación de Euler, podemos colocar en el infinito un vértice donde todas las aristas externas se unen1 . Por tanto, en un DV v = vd + 1, donde vd es el numero de vértices Voronoi. Sustituimos en (8.6) para obtener vd − e + f = 1

(8.8)

Ahora en (2.9) vd + 1 ≤ 2/3 e vd ≤ 2/3 e − 1

(8.9)

Y en (sec. 8.6.2) vd + 1 ≤ 2f − 4 vd ≤ 2f − 5

(8.10)

Estas son las ecuaciones que podemos obtener gracias a la Fórmula de Euler. 1

ver Nandy [53]

181

APÉNDICE

8.7.

DEMOSTRACIÓN DE TEOREMAS EN TD

8.7.1.

LA PROPOSICIÓN 4.5.2

Veamos la siguiente Fig. 8.3 donde D está dentro del círculo definido por ABC. Mostraremos que AC es una arista ilegal.

Figura 8.3: Verificación de aristas legales

Demostración. Vemos cómo están etiquetados los 8 ángulos, el cuadrilátero cortado por ambas diagonales. Debido a que C está fuera del circuncírculo de ABD, por el teorema 4.5.1, el ángulo ∠b1 es más grande que el ángulo ∠a1 . De manera similar, debido a que A está fuera del circuncírculo BCD, nuevamente por Thales, el ángulo ∠b2 es más grande que el ángulo ∠a2 . Continuando de esta manera, se desprende que bi > ai para todo i. Además, ya que D está dentro del círculo ABC, la secuencia de ángulos para la arista AC debe tener (a1 , . . . a4 ) como sus más pequeños ángulos. Así, para cada uno de los seis ángulos formados por la arista BD existe un ángulo más pequeño formado por la arista AC, demostrando que AC es ilegal. 182

8.7 DEMOSTRACIÓN DE TEOREMAS EN TD Existe otro criterio válido: Contemplando dos triángulos ABD y BCD con la arista común BD, si la suma de los ángulos α y γ es menor o igual a 180◦ , la arista BD es legal (Fig. 8.4).

Figura 8.4: Otro Criterio de legalidad Con esto ya está demostrada la proposición 4.5.2.

8.7.2.

DEMOSTRACIÓN DEL TEOREMA DEL CIRCULO VACÍO

Del teorema 4.5.3, si ningún punto de S es interior a cualquiera de los circuncírculos, entonces cualquier flip producirá una arista ilegal (por el teorema 4.5.1). Así, todas las aristas de la triangulación son legales. Probemos el inverso de la declaración usando contradicción. Demostración. Asumamos que T es TD y supongamos que existen triángulos cuyos circuncírculos sí contienen puntos en su interior. Tal situación se vería como en la Fig. 8.5(a), para un triángulo ABC y un punto D dentro de su circuncírculo. De todos los triángulos de T cuyos circuncírculos contienen puntos, elijamos el punto que está más cerca a la arista del triángulo, es decir, el que minimiza la distancia x dada en la parte (b) de la Fig. 8.5. Debido a que T es Deloné todas 183

APÉNDICE

Figura 8.5: Propiedad del circulo vacío sus aristas son legales. Así, por la proposición 4.5.2 el triángulo BCD no puede existir en T . Tenemos a BCE el triángulo adyacente a ABC a lo largo de la arista BC. Nuevamente por la proposición anterior E debe estar fuera del circuncírculo de ABC, como en (c) de la Fig. 8.5. Note que el circuncírculo de BCE contiene a D, y D no puede estar dentro del triángulo BCE. Hemos alcanzado una contradicción: D es un punto dentro del circuncírculo de BCE, con la distancia de D a EC menos que la distancia x.

8.8.

DEMOSTRACIÓN DE TEOREMAS DE DV

8.8.1.

TEOREMA 5.1.8

Demostración. Si todos los puntos de S son colineales, se sigue fácilmente que DV (S) consiste en líneas paralelas y ningún vértice. Así que podemos asumir que no todos los puntos de S son colineales. Asumimos que DV (S) tiene una línea entera llamada L, definido como el borde de regiones V or(p) y V or(q). Tenemos a r un punto en S no colineal con p y q y (sin pérdida de generalidad) asumamos que r está en H(p, q). Entonces el bisector perpendicular de pr debe intersecar L. Además, el rayo L ∩ H(r, p) no pertenece a DV (S) porque ésta se encuentra más 184

8.8 DEMOSTRACIÓN DE TEOREMAS DE DV cerca a r que a p (ver Fig. 8.6 ). Por consiguiente, la línea entera L no puede estar en DV (S).

Figura 8.6: Demostración aristas

8.8.2.

LEMA 5.3.1

Demostración. Si un círculo está contenido dentro del otro, la afirmación se sigue trivialmente. De otra manera, coloquemos los centros de A y B sobre una horizontal, con el extremo izquierdo de A a la izquierda del extremo izquierdo de B. Cada círculo naturalmente divide al otro en 2 partes. B corta A en A0 (parte fuera de B) y A1 (parte dentro de B); de manera similar, A corta B en B0 (fuera de A) y B1 (dentro de A). Decimos a1 a2 la cuerda de A y b1 b2 la cuerda de B. Además, tenemos a L el segmento vertical determinado por los dos puntos de intersección de A ∩ B. Si ambos a1 y a2 están en A0 , entonces a1 , a2 ≤x L y si ambos b1 y b2 están en B0 , entonces b1 , b2 ≥x L. Así que si ambas condiciones se cumplen, las cuerdas no se pueden cruzar (ver Fig. 8.7). Por lo tanto, debemos tener a1 o a2 en A1 o b1 o b2 en B1 . Cualquiera de las 4 posibilidades resulta en que algún extremo de las cuerdas se encuentre dentro del otro disco, como ilustra la Fig. 8.8. 185

APÉNDICE

Figura 8.7: Cuerdas1

Figura 8.8: cuerdas cruzándose En fin, el cruce entre las dos cuerdas fuerza que algún extremo esté estrictamente dentro del otro disco, estableciendo la afirmación del lema 5.3.1.

8.9.

DESCUBRIENDO PUNTOS GENERADORES

Si se da un DV sin los puntos generadores, ¿Cómo encontrarlos? Probamos con un radio adecuado y un punto cualquiera. dependiendo el resultado se recomienda aumentar o disminuir el angulo donde está el punto de prueba, de manera que coincida el triángulo formado con el circulo planteado al inicio. Como 186

8.9 DESCUBRIENDO PUNTOS GENERADORES datos está el centro del circulo, los valores de las tres ramas que parten de este centro. A estas tres ramas se les calcula su pendiente, y a partir de allí, se calculan las pendientes de los tres lados perpendiculares a cada rama de los triángulos −1 ) (ver Fig. 8.9). (m ⊥= mrama

Figura 8.9: DV sin puntos Dados: ma , mb , mc , h, k Prueba:r, Ax , Ay . Se trazan perpendiculares a las ramas para encontrar Bx , By , Cx , Cy mediante la intersección de este sistema: (Bx − h)2 + (By − k)2 = r2 junto a

ma =

Ay − By Ax − Bx

(8.11)

sumamos k a (8.11) ma (Ax − Bx ) + k = (Ay − By ) + k ma (Ax − Bx ) + k − Ay = −(By − k) (−ma Ax + ma Bx − k + Ay )2 = (By − k)2 (ma Bx + Ay − k − ma Ax )2 = r2 − (Bx − h)2 Se hace z = Ay − k − ma Ax 187

APÉNDICE m2a Bx2 + 2zma Bx + z 2 = r2 − (Bx2 − 2hBx + h2 ) (m2a + 1)Bx2 + 2Bx (zma − h) + z 2 − r2 + h2 = 0 Se resuelve esta ecuación cuadrática para obtener Bx1 , Bx2 , se escoge una de las soluciones o la solución real Bx =

Bx =

−2(zma − h) ±

q

4(zma − h)2 − 4(m2a + 1)(z 2 − r2 + h2 ) 2(m2a + 1)

−zma + h ±

q

(zma − h)2 − (m2a + 1)(z 2 − r2 + h2 ) (m2a + 1)

By se obtiene de By = −ma (Ax − Bx ) + Ay Sabiendo Ax , Ay , Bx , By se resuelve de nuevo el sistema (Cx − h)2 + (Cy − k)2 = r2 junto a mb =

Se obtiene Cx =

−z2 mb + h ±

q

By − Cy Bx − Cx

(z2 mb − h)2 − (m2b + 1)(z22 − r2 + h2 ) (m2b + 1)

con

z2 = By − k − mb Bx y Cy = −mb (Bx − Cx ) + By Luego calculamos la intersección de la recta con mc y obtenemos con CCW si el punto está fuera o dentro de la circunferencia. La meta es que el punto de 188

8.10 PROBLEMAS ABIERTOS

intersección sea igual que Ax , Ay . sea el sistema

   

y − ma x = −ma Ax + Ay

  

  y − mc x = −mc Cx + Cy 

   

y − Ay = ma (x − Ax )

  

  y − Cy = mc (x − Cx ) 

   

   

re-ordenando         











ma −1   x   −ma Ax + Ay   0  + =      mc −1 y −mc Cx + Cy 0

       

de esta manera se introduce la función linsolve de Scilab y se resuelve para x, y. Ahora, se aplica el CCW (A, B, C, [x, y]) para saber si el punto está dentro o fuera de la circunferencia dada por r, h, k. Si x, y está fuera entonces se disminuye el angulo con respecto a la primera rama de A, de otra manera, se aumenta el angulo de A hasta que x ≈ Ax ∧ y ≈ Ay . Hasta este punto, se puede ajustar el radio para concordar con los demás puntos si es necesario, pero ya se habrá encontrado tres puntos generadores, por lo menos en su posición angular.

8.10.

PROBLEMAS ABIERTOS

1. De lo dicho en capítulo IV sec. 4.2, es un problema abierto encontrar un algoritmo que cuente el número de triangulaciones de un conjunto S de puntos en el plano que corra en tiempo polinomial. Probar con construir un algoritmo que cuente el número de triangulaciones de un conjunto a partir 189

APÉNDICE de 10 puntos. 2. En la realización del DV, surgió un problema a resolver: Dado el DV de un conjunto de puntos desconocido, hallar estos puntos. En la naturaleza se ven estas figuras, pero no aparecen los sitios que generan cada región Voronoi. Se intenta encontrar los puntos por aproximación, utilizando las aristas Voronoi como datos de entrada. De estas aristas, se recuperan sus pendientes, y de allí las pendientes de sus perpendiculares. Se comienza con un punto de prueba y se intenta lograr un triángulo intersecando segmentos (ver sec. 8.9). 3. Dado un conjunto de puntos, realizar con ellos un DV, con la diferencia de que estos puntos son vértices Voronoi (y no sitios), tomando la precaución de que cada nodo tiene grado exactamente 3, y que los polígonos formados sean convexos. Parece que no todas las configuraciones de puntos funcionan. 4. Usando conceptos de grafos sec. 2.10 de aquí en adelante, comprobar que el grado de la cápsula convexa JCCK es cero en su interior y 2 en su frontera, el

JT DK es mayor que 2, y el JDV K es exactamente 3 en su componente conexa y cero en los demás. Además, se verifica que el DV es regular, al igual que ∂(CC).

5. Usando conceptos de grafos, comprobar que el orden de TD y CC es kV k, mientras que orden(DV ) > kV k referido al mismo conjunto de puntos. Además, Notar que tama˜ no(CC) < tama˜ no(T D) y tama˜ no(DV ) < tama˜ no(T D). 6. Verificar que la CC es subgráfica incorporada de TD. Para ciertas aplicaciones, se pueden extraer subgráficas inducidas del CC, TD y DV. 7. Comprobar que el diagrama TD es conexo, mientras CC tiene conexidad 190

8.10 PROBLEMAS ABIERTOS sólo en ∂(CC) y DV es conexo sin considerar los vértices generadores. 8. Verificar que las aristas de ∂(CC) no son cortadas, la TD (con más de tres sitios) no tiene aristas cortadas y el DV tampoco, a excepción de las aristas externas, que idealmente son infinitas, pero que en la práctica tienen un vértice en la ventana o región de observación del usuario. 9. Comprobar que la ∂(CC) es un ciclo, la TD está formada por ciclos de longitud 3, el DV tiene ciclos de longitud variable. 10. Comprobar que el numero cromático χ(Cn ) se evidencia en ∂(CC). El índice cromático en la componente conexa del DV es 4 a excepción del punto en el infinito, y el de TD es el del vértice de mayor grado más uno. 11. Implementar un algoritmo que verifique si una gráfica es plana. No es fácil hacerlo. 12. Demostrar la siguiente conjetura: Conjetura. “Cualquier configuración de figuras convexas en el plano que formen un teselado irregular y con vértices de grado 3, es un DV”. Esto puede ser una consecuencia de lo visto en el capítulo V. No deja de ser sorprendente. 13. Dado un polígono convexo o no, hallar el DV asociado a él. Es un problema fácil de resolver con Geogebra. Probar colocando aristas al infinito definidas arbitrariamente. 14. Recortar el DV mediante un polígono convexo cualquiera y no solamente por el recuadro delimitado por las coordenadas. Esto permitiría realizar una implementación fractal del DV (ver [75]).

191

Bibliografía [1] M. Abellanas, “Introducción a la geometría computacional.” [Online]. Available: http://www.dma.fi.upm.es/mabellanas/antenas/aratm/contenido.htm [2] M. Abellanas, B. Abellanas, and C. Vilas, “Vorest: Modelización de bosques mediante dv.” [Online]. Available: www.dma.fi.upm.es/mabellanas/vorest/ vorestegc07.pdf [3] M. Abellanas(c), “Sobre la vecindad geométrica.” [Online]. Available: www.dma.fi.upm.es/mabellanas/trabajos/vecindadgeo.pdf [4] M.

Abellanas(d),

launay

y

tricas

en

“Envolvente

diagrama una,

con

de

convexa,

voronoi: muchas

tres

triangulación estructuras

aplicaciones,”

2003.

de

de-

geomé[Onli-

ne]. Available: http://divulgamat2.ehu.es/divulgamat15/index.php?option= comcontentandview=articleandid=10884%3Aun-paseo-por-la-geometria [5] J. Altamirano and X. Rodríguez, “Escaneo óptico y reconstrucción de rostros humanos,” Master’s thesis, Universidad Central de Ecuador, Quito, Ecuador, 2012. [Online]. Available: http://www.dspace.uce.edu.ec/handle/25000/538 [6] F. Arias, El proyecto de investigación, 5th ed.

Episteme, 2006. [Online].

Available: http://www.fidiasarias.com/publicaciones.html 193

Bibliografía

Bibliografía

[7] J. Baerentzen, J. Gravesen, and F. Anton, Guide to C. Geometry, 1st ed. Springer-Verlag, 2012. [Online]. Available: www.link.springer.com/book/10. 1007%2F978-1-4471-4075-7 [8] P. Barceló, “Clase 1. grafos: modelos, tipos, representación e isomorfismo,” slides, 2010. [Online]. Available: www.u-cursos.cl/ingenieria/2010/1/ CC3101/1/materialdocente/ [9] P. Barceló(b), “Clase 3: Grafos planares y colorabilidad de grafos,” slides, 2010. [Online]. Available: www.u-cursos.cl/ingenieria/2010/1/CC3101/1/ materialdocente/ [10] M. Baudin, Introduction to Scilab.

The Scilab Consortium-Digiteo, 2010.

[Online]. Available: www.scilab.org/resources/documentation/tutorials [11] M. Bern and D. Eppstein, “Mesh generation and optimal triangulation.” [Online]. Available: https://www.ics.uci.edu/~eppstein/pubs/BerEpp-CEG-95. pdf [12] M. Berón, E. Gagliardi, and G. Hernández, “Factibilidad de uso del ruteo voraz en los grafos de gabriel, de vecindad relativa y triangulación de delaunay.” [Online]. Available: http://sedici.unlp.edu.ar/bitstream/handle/ 10915/22348/Documentocompleto.PDF?sequence=1 [13] M. e. a. Bogdanov, “Hiperbolic delaunay complexes and voronoi diagrams made practical,” JOCG, vol. 5, no. 1, pp. 56–85, 2014. [Online]. Available: https://journals.carleton.ca/jocg/index.php/jocg/article/view/141 [14] S. Carlsson, Geometric Computing in image analysis and visualization, 1st ed. KTH, 2007. [Online]. Available: http://www.nada.kth.se/~stefanc/ gclecnotes.pdf 194

Bibliografía [15] CGAL. User and Reference Manual, 4th ed., cgal.org, 2012. [Online]. Available: http://doc.cgal.org/latest/Manual/index.html [16] T. Chan, “Optimal output-sensitive convex hull algorithms in two and three dimensions,” Discrete Comput. Geom., no. 16, pp. 361–368, 1996. [Online]. Available: https://www.cs.ucsb.edu/~suri/cs235/ChanCH.pdf [17] D. Chand and S. Kapur, “An alg. for convex polyt.” JACM, vol. 17, no. 1, pp. 78–86, 1970. [Online]. Available: http://www.academia.edu/7138385/ AnAlgorithmforConvexPolytopes [18] J. Chen, Computational Geometry.

Texas A and M University, 1996.

[Online]. Available: www.faculty.cs.tamu.edu/chen7notes/geo.pdf [19] P. Cignoni, C. Montani, and R. Scopigno, “Dewall: A fast divide and conquer dt,” 1997. [Online]. Available: http://vcg.isti.cnr.it/publications/ papers/dewall.pdf [20] M. De Berg, O. Cheong, and M. Van Kreveld, Computational Geometry, 3rd ed. Springer, 2008. [Online]. Available: http://www.cs.uu.nl/geobook [21] S. Devadoss and J. O’rourke, Discrete and Comp. Geometry, 1st ed. Princeton University P., 2011. [Online]. Available: www.press.princeton.edu/ titles/9489.html [22] R. Diestel, Graph Theory, 3rd ed. Springer-Verlag, 2005. [Online]. Available: http://esi2.us.es/~mbilbao/pdffiles/DiestelGT.pdf [23] A. Dumitrescu and et al, “Bounds on the maximum multiplicity of some common geometric graphs,” Proc. 28th International Symposium on Theoretical Aspects of Computer Science, pp. 637–648, 2011. [24] F. Dupuis, “Voro3d,” software, 2012. [Online]. Available: www.lmcp.jussieu. 195

Bibliografía

Bibliografía

fr/~mornon/voronoi.html [25] S. Enterprises, “20 a˜ nos de scilab,” video, 2014. [Online]. Available: http://www.youtube.com/channel/UCFWJxS5gUSdO4B2Vtl2QvA [26] A. Espejo, Topología de espacios métricos, 1st ed.

Universidad Nacional

Abierta, 2009. [27] M. Ettrich and et al, “lyx 2.1.2,” free software, 2014. [Online]. Available: http://www.lyx.org [28] D.

Expósito,

“Estudio

y

visualización

de

e.c.

y

t.

con

direc-

ciones restringidas en gc,” Master’s thesis, Universidad de Alcalá, Espa˜ na, 2009. [Online]. Available: http://www2.uah.es/ordend/files/ TFC-TriangulacionesRestringidas-Memoria.pdf [29] N. Falacci and C. Heuton, “Extracto de "numbers 2.10",” video, 2011, género policial. [Online]. Available: http://www.youtube.com/watch?v= bbKqPcTdv9o [30] R. Fitzpatrick and J. Heiberg, Euclid’s Elements of Geometry, 1st ed., T. U. of Texas, Ed.

The University of Texas, 2008. [Online]. Available:

http://farside.ph.utexas.edu/books/Euclid/Elements.pdf [31] T. Fraichard, “Path planning approaches,” slides, 2008. [Online]. Available: http://digi.physic.ut.ee/mw/images/4/40/16mpapproaches.pdf [32] K. Fujita, N. Hirokawa, and T. Tachikawa, “Vd based cum. approx.” 2000. [Online]. Available: http://syd.mech.eng.osaka-u.ac.jp/papers/2000/ 09AIAAco.pdf [33] Gaussianos(b), 196

“Una

interesante

introducción

a

la

Bibliografía gc,”

2011.

[Online].

Available:

www.gaussianos.com/

una-interesante-introduccion-a-la-geometria-computacional [34] B. Giles and P. Bratley, Algorithmics t. and p., 1st ed.

Prentice

Hall, 1988. [Online]. Available: https://jobscare.files.wordpress.com/2013/ 02/algorithmics-theory-and-practice.pdf [35] C. Gold, “What is gis and what is not?” Transactions in GIS, vol. 10, no. 4, 2006. [36] C. Gold and S. Cormack, “Spatially ordered networks and topographic reconstructions,” Journal of GIS, vol. 1, no. 2, pp. 137– 148, 1987. [Online]. Available: http://www.voronoi.com/wiki/images/0/0d/ Spatiallyorderednetworks%26topographicreconstructions1987.pdf [37] G. Gonthier, “A computer checked proof of the fct,” microsoft Research Cambridge. [Online]. Available: http://research.microsoft.com/en-us/um/ people/gonthier/4colproof.pdf [38] R. Graham, “An efficient algorithm for determining the convex hull of a finite planar set,” 1972. [Online]. Available: www.math.ucsd.edu/~ronspubs/ 7210convexhull.pdf [39] C.

Grima,

“Cada

uno

en

su

región

y

voronoi

en

la

de todos,” 2011. [Online]. Available: http://naukas.com/2011/12/23/ cada-uno-en-su-region-y-voronoi-en-la-de-todos/ [40] C. Grima(b), “Scan,” video, género educativo. [Online]. Available: www.youtube.com/watch?v=dw120Yclav8 [41] R. Guerequeta and A. Vallecillo, T. de dise˜ no de Algoritmos, 1st ed., U. de Málaga, Ed., 2000. [Online]. Available: http://www.lcc.uma.es/~av/ 197

Bibliografía

Bibliografía

Libro/Indice.html [42] L. Guibas, “Basic algorithms and combinatorics in cg,” stanford University. [Online]. Available: https://graphics.stanford.edu/courses/cs268-09-winter/ notes/basic.pdf [43] M. d. Hohenwarter, “Geogebra 5.0.61.0-3d,” free software, 2015. [Online]. Available: www.geogebra.org/ [44] J. Hughes and et al, Computer Graphics, 3rd ed.

Addison-Wesley, 2014.

[Online]. Available: www.informit.com/aw [45] F.

Hurtado,

“Qué

es

la

geometría

computacional?”

2003.

[Onli-

ne]. Available: http://divulgamat2.ehu.es/divulgamat15/index.php?option= comcontentandview=article [46] R. A. Jarvis, “On the identification of the convex hull of a finite set of points in the plane,” Information Processing Letters, no. 2, pp. 18–21, 1973. [Online]. Available: http://www.sciencedirect.com/science/article/pii/ 0020019073900203 [47] C. Kaplan, “Voronoi diagrams and ornamental design.” [Online]. Available: http://www.cgl.uwaterloo.ca/~csk/papers/kaplanisama1999.pdf [48] C. Lawson, “Transforming triangulations,” Discrete Math., vol. 3, pp. 365– 372, 1972. [49] L. León, Tejiendo Algoritmos.

Universidad de los Andes, 2012, vol. 1.

[Online]. Available: www.webdelprofesor.ula.ve/ingenieria/lrleon/tejiendo. html [50] Maplesoft and W. M. Inc., “Maple 14.00,” software, 2010. [Online]. Available: www.maplesoft.com 198

Bibliografía [51] S. Meeran and A. Share, “Optimum path planning using convex hull and local search heuristic algorithms,” Mechatronics, vol. 8, no. 7, pp. 737–756, 1997. [52] J.-E.-M. Miraikan, “Exp. combinatoria,” video, discrete Structure Manipulation S. P. [Online]. Available: http://www.youtube.com/watch?v= Q4gTV4r0zRs [53] S. Nandy, “Voronoi diagram,” slides, indian Statistical Institute. [Online]. Available: http://www.tcs.tifr.res.in/~ghosh/subhas-lecture.pdf [54] F. Nielsen, “Algorith. geom. adaptatifs,” Ph.D. dissertation, Universidad de Nice-Sophia, 1996. [Online]. Available: http://www.sonycsl.co.jp/person/ nielsen/PT/phdthesis [55] J. O’Connor and E. Robertson, “Georgy f. voronoi,” 2007. [Online]. Available: http://www-history.mcs.st-and.ac.uk/Biographies/Voronoy.html [56] J. O’Connor(b) and E. Robertson, “Boris nikolaevich delone,” 2010. [Online]. Available: http://www-history.mcs.st-and.ac.uk/Biographies/Delone.html [57] J. O’Connor(c) and E. Robertson, “Ronald lewis graham,” 2010. [Online]. Available: http://www-history.mcs.st-and.ac.uk/Biographies/Graham.html [58] D. Orden, “Une los puntos...” 2013, universidad de Alcalá. [Online]. Available: http://cifrasyteclas.com/2013/05/10/ [59] J. Ovalles, “Tratamiento de imágenes binarias planas con topología digital,” Master’s thesis, Universidad Nacional Abierta, Caracas, Venezuela, 2012. [60] I. Pinelis, “Polygon convexity: A minimal test,” 2008. [Online]. Available: http://arxiv.org/pdf/cs/0609141.pdf [61] F. Preparata and M. Shamos, Computational Geometry, An Introduction. 199

Bibliografía

Bibliografía

Springer-Verlag, 1985. [Online]. Available: www.link.springer.com/book/10. 1007%2F978-1-4612-1098-6 [62] J. Priego and M. Porres, “La triangulación de delaunay aplicada a los modelos digitales del terreno,” 2002. [Online]. Available: http: //cgat.webs.upv.es/bigfiles/priegoporres2002.pdf [63] M. Ramella, W. Boschin, and D. Fadda, “Finding galaxy clusters,” 2000. [Online]. Available: http://web.cs.swarthmore.edu/~adanner/cs97/f06/pdf/ galaxyVoronoi.pdf [64] P. Reyes, “Fundamentos geometría computacional. tema 1: Cierre convexo,” html. [Online]. Available: http://personal.us.es/preyes/fgc/contenidos/ gctem1ma.htm [65] F. Rivero, Geometría Computacional, 1st ed.

Universidad de los Andes.

[Online]. Available: www.webdelprofesor.ula.ve/ciencias/lico/geomecomp/ index4 [66] E. Rodríguez, “Introducción a gc,” slides, 2012, cinvestav-Tamaulipas. [Online]. Available: http://www.tamps.cinvestav.mx/~ertello/gc/sesion01. pdf [67] E. Rodríguez(b), “Dv,” slides, 2013, cinvestav-Tamaulipas. [Online]. Available: http://www.tamps.cinvestav.mx/~ertello/gc/sesion16.pdf [68] E. Rodríguez(c), “Triangulaciones,” slides, 2013, cinvestav-Tamaulipas. [Online]. Available: http://www.tamps.cinvestav.mx/~ertello/gc/sesion18. pdf [69] M. Rosas, “Los números de (euler)-catalán,” Boletín de la Asociación Matemática Venezolana, vol. 10, no. 1, pp. 43–58, 2003. [Online]. Available: 200

Bibliografía www.emis.de/journals/BAMV/conten/vol10/catalan.pdf [70] J. Ruiz, “Algunas estructuras de datos y algoritmos para geometría computacional,” Master’s thesis, Universidad de los Andes, Merida, Venezuela, 2007. [Online]. Available: http://tesis.ula.ve/pregrado/tdearquivos/8/ TDE-2007-06-29T10:41:36Z-329/Publico/Jose%20Ruiz.pdf [71] E. son

Scheinerman, Learning,

Matemáticas 2001.

[Online].

Discretas, Available:

1st

ed.

Thom-

www.amazon.com/

Matematicas-Discretas-Spanish-Edition-Scheinerman/dp/97068607 [72] C. Schenk, “Miktex 2.9,” free software, 2013. [Online]. Available: www.miktex.org/download [73] E. Scilab, INRIA, and ENPC, “Scilab 5.5.1,” free software, 2014. [Online]. Available: www.scilab.org [74] M. Sharir and A. Sheffer, “Counting triangulations of planar p. s.” Electr. J. Comb., vol. 18, no. 1, 2011. [Online]. Available: http: //www.cs.tau.ac.il/~sheffera/counting/PlaneGraphs.html [75] K. Shirriff, Generating Fractals from VD, 1st ed. Elsevier Science, 1998, pp. 23–25. [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/download? doi=10.1.1.56.4446andrep=rep1andtype=pdf [76] A. Thiessen and C. Alter, “Climatological data,” Monthly Weather R., vol. 39, no. 1082, 1911. [Online]. Available: http://docs.lib.noaa.gov/rescue/ mwr/039/mwr-039-07-1082b.pdf [77] A. Tucker, W. Bradley, and R. Cupper, Fundamentos de Informática. Lógica, Resolucion de Problemas, Programas y Computadoras, 1st ed. McGraw-Hill, 1994. [Online]. Available: www.unatachira.com.ve/academia/ 201

Bibliografía

Bibliografía

documentos/20131/20131marce323libroA.pdf [78] P. Valenzuela, “Implementación de una biblioteca de triangulación de polígonos basada en el algoritmo lepp delaunay,” Master’s thesis, Universidad de Chile, Santiago de Chile, 2009. [Online]. Available: http://www.tesis. uchile.cl/bitstream/handle/2250/103727/cf-valenzuelaps.pdf?sequence=3 [79] C. Vila, “Nature by numbers,” video, 2010. [Online]. Available: http: //www.etereaestudios.com/docshtml/nbynhtm/intro.htm [80] G. Voronoi, “Nouvelles applications des paramètres continus à la théorie des formes quadratiques,” J. Reine Angew. Math., vol. 134, no. 1, pp. 198–287, 1908. [Online]. Available: http://wwwuser.gwdg.de/~subtypo3/ gdz/pdf/PPN2439196890134/LOG0014.pdf [81] J. Wallner and H. Pottmann, “Geometric computing for freeform architecture,” pdf, 2011, king Abdullah University of Science and Technology. [Online]. Available: http://www.dmg.tuwien.ac.at/pottmann/ 2011/freeform/paperdocs/freeform2011.pdf

202

Nomenclatura ∀(x, y)

Para todo (x,y)

kx − pk

Distancia euclidiana de x-p

N

Conjunto de números naturales

ab

Segmento con extremos a y b

∂P

frontera del poligono P

P

Sumatoria de todos los v que pertenecen a V

kV k

Número de elementos de V

{a, b}

Conjunto de elementos a y b

En

Espacio Euclidiano n-dimensional

f :A→B

Función definida desde el conjunto A hacia el conjunto B

S\p

Conjunto S sin el elemento p

u≺v

u comparte arista con v

v∈V

V (G) ⊆ V (H) V(G) subconjunto de V(H) 3D

Espacio tridimensional 203

Términos técnicos APF

Aritmética de Punto Flotante

arrays

Arreglos de datos en forma tabular

CC

Cápsula Convexa de un conjunto de puntos

CCW

Primitiva Contrarreloj

char

caracter ASCII

CPU

Unidad Central de Procesos de la computadora

doubles

Números de punto flotante de 64 bits

DV

Diagrama de Voronoi de un conjunto de puntos

flip

Intercambio de aristas en un cuadrilátero

MDT

Modelo Digital de Terreno

METANET

Módulo de Scilab (grafos)

morphing

Transformación de una imagen en otra

O(f(n))

Orden de complejidad en el peor caso

quicksort

Ordenamiento rápido

range scanner explorador de área efectiva RGB

Siglas de Rojo-Verde-Azul

Scan

exploración

SIG

Sistema de Información Geográfica (en inglés GIS)

SIVP

Scilab Image and Video Processing Toolbox

204

Nomenclatura

Nomenclatura spline

Guía para dibujar curvas

string

cadena de caracteres

TD

Triangulación de Delaunay de un conjunto de puntos

Vor(p)

Región Voronoi en torno a p, puede ser acotada o no

205

View publication stats