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 To-

talidad, 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 Ad-
ministració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, Al-
fredo 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 EUCLI-

DIANA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . 57
4.2. TRIANGULACIONES Y FÓRMULA DE EULER . . . . . . . . 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
6.2. LA CÁPSULA CONVEXA (CC) . . . . . . . . . . . . . . . . . . 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.3. PUENTES (TANGENTES) DE INTERCONEXIÓN . . . . . . . 113
6.3.2. Función T I[ccf, ch1 , ch2 , g] = divi(ptref, coord) . . . . . . 117
6.4. LA TRIANGULACIÓN DELONÉ . . . . . . . . . . . . . . . . . 120
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.5. EL DIAGRAMA DE VORONOI . . . . . . . . . . . . . . . . . . 135
6.5.2. Función dual DV [vv, ino, gdv] = dvtri(coord, ptref ) . . . . 137
6.6. PRUEBA Y VERIFICACIÓN: ENTRADAS Y SALIDAS DE DA-

TOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 unción(); 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 CON-

JUNTO 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
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 VA-
CÍ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, visua-

lizar 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 herramien-
tas 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 compu-
tabilidad, 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 estruc-

turas. Se darán tres algoritmos (Incrementable, de Graham y Divide&vence) y se
explicará con detalles. Hay una construcción interesante llamada Puentes de Inter-
conexió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 confun-
dirse 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 algorit-

mos geométricos eficientes. Estos algoritmos frecuentemente operan y son guiados
por un conjunto de Estructuras de Datos que poseen todos los sistemas actual-
mente. 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 ma-
llas), visión computacional (reconstrucción 3D). No sólo estas áreas han sido fuen-
te 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 con-
junto 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 Trian-
gulació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 Eu-
clides2 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 prue-
bas matemáticas a simples cálculos. Entonces, durante el siglo XIX lógicos como
Babbage, Boole, Frege y Peano intentaron formalizar el razonamiento matemáti-
2
Ver Elementos [30], libros 7,8,9. Según parece, estos libros son atribuidos a la escuela Pitagó-
rica.
7
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 exis-
tencia, 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,
3
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.
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 pro-
piedades 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, sis-
temas 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
Actores de los que se ha recopilado información están los españoles Manuel Abe-
llanas, 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. Law-
son, 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, bus-

cando 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 discre-
to. En seguida, realizar una implementación en lenguaje Scilab. Luego verificar
la corrección comparando resultados con Geogebra, que ya tiene instalados es-
tos 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
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, recu-

peració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 Biblio-
grafía fue generada automáticamente usando el archivo de estilo IEEEtranS.
6
Si no aparece en Internet, puede enviarme un email a osmer montilla
12
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 PRO-

BLEMAS ALGORÍTMICOS, en español, y es la sucesión de las siguientes eta-
pas: diálogo, especificaciones, subdivisión, definición de abstracciones, codifica-
ció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 geō, “tierra”; metrein, “medir”), rama de las matemáti-
cas 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 repre-
sentan 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

1
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
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 mis-
ma 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 Geo-
metrí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 propieda-

des 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 interpre-

tado 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
i1/2
d(x, y) = (y1 − x1 )2 + (y2 − x2 ) 2
h
(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 (2.3)
18
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 com-
binació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 seg-

mento 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 nu-
mé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
4
Veremos en capítulo III Capítulo 4 que la estructura TD es la unión de triángulos con carac-
terí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 ) = Ø
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 compo-

nentes. 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 di-

recció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 conta-

remos 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 in-
tersecció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 be-
neficio 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

1 2n

vértices es el número de Catalán8 cn = 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 =
grado de vertice 1 de T . Dado que el polígono es convexo, esto es verdad
P
T ∈τn+1
para todos los vértices de T . Por lo tanto, sumaremos para todos los vértices de
T , obteniendo (n + 1) · tn+2 =
Pn+1 P
i=1 T ∈τn+1 grado de vertice i de T
=
P Pn+1
T ∈τn+1 i=1 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
2(2n − 1) (2n − 1) (2n − 3) 3 1 (2n)! 1 2n
!
tn+2 = tn+1 = 2n ... = =
n+1 n+1 n 32 (n + 1)!n! n+1 n
que es el número de Catalán buscado
Sabemos que a
= a!
8

b b!(a−b)!
24
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 computado-

ra, 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 adecua-
damente 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 compu-
25
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 Gauss-
Jordan 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 cons-
tante 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. máximo[O(f (n)), O(g(n))] = O(máximo[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íci-

tamente 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 efi-
cientes 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 pro-
piedades 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 resolver-
10
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 fre-
cuentemente pasa por tres fases: en la primera fase, ignoramos todo lo que pueda
obstaculizar nuestro entendimiento de los conceptos geométricos con los que esta-
mos 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 ge-

nerales 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 ope-

raciones 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étri-
co (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 secuen-
cia 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 pro-
cedimientos 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
13
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
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 mo-
delos 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 imple-
mentaciones de estos algoritmos.
15
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].
32
PRELIMINARES
2.9.2. Recursividad
La recursividad (recursión) es aquella propiedad que posee una función o proce-

dimiento 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 proble-
mas 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 compu-
tació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 con-
trarreloj alrededor de su círculo común por medio del cálculo del signo del deter-
minante
 
 xA y A 1 
 
xB y B 1  (2.5)
 
det 
 
 
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 suficientepara 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
 
 xA y A x2A + yA2 1 
 
x2B + yB2 1
 
 xB yB 
(2.6)
 
det  
xC yC x2C + yC2 1
 
 
 
 
xD yD x2D + yD
2
1
 
2.10. GRAFOS
Tienen aplicaciones en sociología, química, geografía, ingeniería eléctrica e indus-

trial, 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 proyec-
to, 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
19
desde una fuente de agua potable a, por ejemplo, una urbanización.
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.
18
En el capitulo VI está definida la función asociada a CCW y Ccírculo
19
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 pala-
bra multigráfica, que no se usará aquí
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,
JG(v)K = 2kEk (2.8)

X
v∈V
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érti-

ces. 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 equiva-

lencia 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 ilumina-

ció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 :

 
2 si n es par

 

 
χ(Cn ) = (2.14)
3 si n es impar 

 
 
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 cualquie-

ra, 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.
21
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. Des-
cargable desde https://coq.inria.fr
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

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 docu-
mento 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
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).

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 usare-
mos indistintamente.
45
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 mues-
tra, 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 acer-
carí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. Da-
47
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 exis-
tente 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:
n(n − 1) n2 n
3 + 4 + . . . + (n − 1) = − (1 + 2) = − −3 (3.1)
2 2 2
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
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 deter-

minar 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)

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
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 tiem-
po 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 de-
penden 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 des-

viaciones 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
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 pun-
tos, 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 aplicacio-
nes. 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 po-

lí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

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 utili-

zamos el concepto de visibilidad:
La complejidad en tiempo no pasa de O(n2 ), debido a la verificación de la visibi-
57

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
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 co-
nectadas 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 pa-

ra 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 de-
cimos 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
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 teo-
rema 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 en-
tradas 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
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 angu-
lares 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
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.
2
“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]).
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 pun-

tos en posición general, donde 4 puntos son siempre extra-circulares. Una trian-
gulació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 .
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

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 erro-
res;
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 represen-

tació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 tridimensio-
nales. 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 po-
lí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
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 co-
menzando 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 conjun-
to 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, pasare-
mos 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, Descompo-
sició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 . La idea es asignar a cada punto la
Sn
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} (5.1)

2
En su libro ([21]). Hay buenas introducciones al tema en [39, 67]
74
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):
n
Reg(S) = 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
(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
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 semi-

planos H(p, q) donde q es cualquier otro punto en S. Es decir:
V or(p) = (5.2)
\
H(p, q)
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 geome-

trí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
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 in-
tersecciones de bisectores crean vértices Voronoi5 . Sin embargo, ciertamente no
todas las intersecciones llegan a ser vértices Voronoi. ¿Existe una manera fácil pa-
4
Elementos, libro IV, proposición 5, en [30]
5
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
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írcu-
lo 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
Voronoi son partes de bisectores perpendiculares entre puntos, pero no todos es-
tos 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
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.
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érti-
ces 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
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 comple-

jidad 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 al-
goritmo 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).

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 regio-
83
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 propia-
mente. 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
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).

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:
Ai

Ip = min
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
1
Ipmax =
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én-
dose la siguiente figura Fig. 5.12, con un Ip = 0,2232
87
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 cual-
quier manera por subregiones suficientemente pequeñas, existirán puntos que per-
tenezcan al menos a n + 1 de estas subregiones; además siempre es posible encon-
trar 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
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
A1 r1 + A2 r2 + . . . + An rn
q̄ =
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 hospita-
90
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 vegeta-
les, 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 mues-

tra, 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, Anima-

ció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, Agru-
pamiento usando varios enfoques,
6. Modelaje computacional y simulación, Estadística espacial y temporal, Pro-

cesamiento de imágenes, Además, el DV se aplica en investigación de ope-
raciones (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
9
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
91
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, enton-

ces puedes escribir un programa que lo ejecute”2 .
Muchos intentos de programación no dieron su resultado hasta entender comple-

tamente 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 seleccio-

nados.
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), ‘ ∗ ’ (elemen-
tos) 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.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 res-
puesta 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 fun-

ciona 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 reali-
zar 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
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 uni-

formemente 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
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
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.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 pro-

grama, 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 + extensión”
102
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.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 coor-

denadas de ventana (mínimo-izquierda y máximo-derecha).
Descripción: Se generan puntos haciendo clic en la pantalla, en base a las coorde-

nadas 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áge-

nes (C:/SCI+’/contrib/sivp/0.5.3.2-1/images/nombre-de-Imagen’) del sis-
tema 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
un cuadro de diálogo.
Salidas: X es un vector de coordenadas de puntos, coord es una matriz de coor-

denadas de ventana (mínimo-izquierda y máximo-derecha).
Descripción: Genera puntos de acuerdo con el mouse, sobre una imagen seleccio-
nada.
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 corres-
pondiente. Ejemplos: puntr = [], rmt()
105
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
Figura 6.4: localiz1
Figura 6.5: localiz2
107
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
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.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 = expresión instr end
Entradas: La expresión 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
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).
Descripción: Dibuja una simple polilínea descrita por los vectores de coordena-
das 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 argu-
mentos 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.
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
1. El seudocódigo del algoritmo capsula (algoritmo 14)

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
Figura 6.8: divi-funciones
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 = expresión then (instr1 ) [else (instr2 )] end
Entradas: La expresión 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
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 ca-

racteres 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(módulo 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
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.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 )
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 nu-
merados 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
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 )
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.
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
Figura 6.7: dibuc código fuente

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
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
(a) conver-1
(b) conver-2
Figura 6.9: conver
123
(a) puen2-1
(b) puen2-2
Figura 6.10: puen2
124
(a) inic-1
(b) inic-2
Figura 6.11: inic
125
(a) desci1-1
(b) desci1-2
Figura 6.12: desci1
126
(a) prueb2-1
(b) prueb2-2
(c) prueb2-3
Figura 6.13: prueb2
127
Figura 6.14: TD funciones
Describimos los algoritmos implementados y del sistema 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 (op-

cional).
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
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.
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.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
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.
1. El seudocódigo para la TD general es (ver algoritmo 16)
131
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)

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
(a) trit-1
(b) trit-2
(c) sdel
Figura 6.15: códigos trit, sdel
133
(a) delon1
(b) delon2
Figura 6.16: delon
134
6.5. EL DIAGRAMA DE VORONOI
El diagrama de funciones asociadas es (Fig. 6.17)
Figura 6.17: DV- funciones
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
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.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án-

gulos 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
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 pen-

dientes 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 Voro-

noi.
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.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.
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 Voro-

noi.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én-

dice 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
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.
Presentamos algunos seudocódigos de DV.
1. El seudocódigo general para el DV es (ver algoritmo 17)

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
(a) dvt1
(b) dvt2
Figura 6.18: DV dual
142
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 <n then// a c o t a m i e n t o de b a r r i d o a l a d e r e c h a
for j=i +1:n
[ pct , k i ]=unique ( [ Tg ( : , i ) ; Tg ( : , j ) , ’ r ’ ] ) ;
d i f=s i z e ( ki , ’ r ’ ) ;
i f d i f ==4 then// examinar
c o n t ( $+1)= j ; // t r i a n g u l o j c o n t i g u o a i
end
end
end
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
(a) tresp-1
(b) tresp-2
Figura 6.19: tresp
144
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
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
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
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. 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
Figura 6.21: voroc
(a) vorg-1
(b) vorg-2
Figura 6.22: vorg
147
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
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
(a) crm2-1
(b) crm2-2
(c) crm2-3
Figura 6.23: crm2-menu principal
150
(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
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án-
gulo; 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
(a) rmt con 20 puntos
(b) localiz con 20 puntos
(c) pvori2 con 20 puntos

154
Figura 6.26: 20 puntos con rmt, localiz, pvori2
(a) CC (Scilab)
(b) CC (Metanet)
(c) CC- consola
Figura 6.27: CC Salidas

155
(a) TI-en Scilab
(b) TI-consola
(c) TI-salida-consola
Figura 6.28: TI-salida

156
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 unción(); timer()
Entradas: La ejecución de una f unción 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
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 sensi-

tiva, 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
(a) TD-1
(b) TD-2
(c) TD-3
Figura 6.30: TD- consola
161
(a) DV- Scilab (gráfica)
(b) DV- Scilab (Metanet)
Figura 6.31: DV- salida
162
(a) DV-1
(b) DV-2
163
(c) DV-3
Figura 6.32: DV- consola

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 pro-

blemas 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 entre-
lazados 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 lengua-

jes 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 de-
terminada 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 cons-
truir 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 se-
para 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
No siempre la diagonal más pequeña de un cuadrilátero divide a dos trián-

gulos 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 Edels-
brunner 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 dimen-

sió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
Por estabilidad nos referimos al grado de atenuación de los errores producidos en la entrada
3
Ver [13] y la pagina de Jason Davies http://www.jasondavies.com.
169
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
estos puntos. La fórmula de la pendiente de una recta es: m = , y la recta
x2 − x1
perpendicular tiene como pendiente m⊥ = −1/m siempre y cuando m 6= 0
x1 +x2 y1 +y2
Esta recta pasa por el punto medio de P1 y P2: x0 = 2
y y0 = 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 de-

termine 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 ubica-
ció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:

 
O(1) n≤1

 

 
T (n) = (8.1)
O(n) + T (pivot − l) + T (r − pivot) n > 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
 
O(1) n≤1

 

 
T (n) =
O(n) + 2T ( n2 ) n > 1 

 


172
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 − xi−1 yi )| donde x0 = xn ∧ y0 = yn ∧ n ≥ 3.

Pn
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 x1 y1 x2 y2 x3 y3 1 x1 y1 x1 y1 x2 y2

= + + =

− −
2
x3

y3 x1

y1 x2

y2 2
x3

y3 x2

y2 x3

y3

173
APÉNDICE

x1 y 1 1

1 x2 y2 x1 y1 x1 y1 1

= + = x2 y 2 1

−
2
x3

y3 x3

y3 x2

y2 2

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
P
1
Para n = k tenemos Ak = i=1 (xi yi−1 − xi−1 yi ) para el polígono de k lados.
k
2
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
1
Ak+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 , obte-
nemos
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:

1 n
1 n xi yi
X
X
A= (xi yi−1 − xi−1 yi ) =

det

2
i=1
2
i=1 xi+1

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. Formal-

mente (se generaliza la ecuación (2.3)),
M = {λ1 p1 + ... + λn pn | λi ≥ 0, λi = 1} (8.2)

X
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 (8.3)
donde λi ≥ 0 y λi = 1. De la misma manera, y puede ser escrito con

P
y = λ01 p1 + ... + λ0n pn (8.4)
donde λ0i ≥ 0 y = 1. Ademas, cualquier punto del segmento xy puede ser

P 0
λ i
expresado como
αx + βy = α λi pi + β λ0i pi = (αλi + βλ0i )pi

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

X X X
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 pa-
176
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 = 1. Ahora, elegimos λ0i =

P 0
λ i
λi/(1−λn ) 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−1
(1 − λn )( p1 + ... + pn−1 ) + λn pn = λ1 p1 + ... + λn pn
1 − λn 1 − λn
está en CC(S), donde λi = 1.

P
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 ) (8.5)
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.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 re-

laciona 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 : vértices, 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 nu-

mero 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 : vértices, 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 cor-

tado 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 Tha-
les, 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 circun-

cí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 hori-
zontal, 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
(m ⊥= ) (ver Fig. 8.9).
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
Ay − By
ma = (8.11)
Ax − Bx
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
q
−2(zma − h) ± 4(zma − h)2 − 4(m2a + 1)(z 2 − r2 + h2 )
Bx =
2(m2a + 1)
q
−zma + h ± (zma − h)2 − (m2a + 1)(z 2 − r2 + h2 )
Bx =
(m2a + 1)
By se obtiene de By = −ma (Ax − Bx ) + Ay
Sabiendo Ax , Ay , Bx , By se resuelve de nuevo el sistema
By − Cy
(Cx − h)2 + (Cy − k)2 = r2 junto a mb =
Bx − Cx
q
−z2 mb + h ± (z2 mb − h)2 − (m2b + 1)(z22 − r2 + h2 )
Se obtiene Cx = con
(m2b + 1)
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
 
y − Ay = ma (x − Ax )

 

 
intersección sea igual que Ax , Ay . sea el sistema
y − Cy = mc (x − Cx ) 

 
 
 
y − ma x = −ma Ax + Ay

 

 
y − mc x = −mc Cx + Cy 

 
 
re-ordenando
      
ma −1   x   −ma Ax + Ay   0

 

 
  + = 
−mc Cx + Cy 0
      
mc −1 y

 
 
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. Ade-
más, Notar que tamaño(CC) < tamaño(T D) y tamaño(DV ) < tamaño(T D).
6. Verificar que la CC es subgráfica incorporada de TD. Para ciertas aplicacio-

nes, 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]. Availa-

ble: 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), “Envolvente convexa, triangulación de de-

launay y diagrama de voronoi: tres estructuras geomé-
tricas en una, con muchas aplicaciones,” 2003. [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 isomorfis-

mo,” 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.” [On-
line]. 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 com-
mon 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
fr/~mornon/voronoi.html
[25] S. Enterprises, “20 años 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 Alca-
lá, España, 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), “Una interesante introducción a la
196
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 topo-

graphic 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 diseño de Algoritmos, 1st ed.,

U. de Málaga, Ed., 2000. [Online]. Available: http://www.lcc.uma.es/~av/
197
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 Ma-

nipulation 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
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 conve-

xo,” 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, Vene-
zuela, 2007. [Online]. Available: http://tesis.ula.ve/pregrado/tdearquivos/8/
TDE-2007-06-29T10:41:36Z-329/Publico/Jose%20Ruiz.pdf
[71] E. Scheinerman, Matemáticas Discretas, 1st ed. Thom-

son Learning, 2001. [Online]. Available: 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
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
Sumatoria de todos los v que pertenecen a V

P
v∈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 (G) ⊆ V (H) V(G) subconjunto de V(H)
3D Espacio tridimensional
203
Términos técnicos Nomenclatura
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
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

mithesisGC Intro2 PDF

Cargado por

Copyright:

Formatos disponibles

mithesisGC Intro2 PDF

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

mithesisGC Intro2 PDF

Cargado por

Copyright:

Formatos disponibles

See discussions, stats, and author proﬁles for this publication at: https://www.researchgate.

algoritmos geométricos sobre conjuntos ﬁnitos de puntos

Thesis · May 2015

construir una guia para Algebra 1 View project

desarrollo de algoritmos geometricos View project

The user has requested enhancement of the downloaded ﬁle.

Algoritmos Geométricos sobre

Autor: Osmer A. Montilla Rangel

Algoritmos Geométricos sobre

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

Considero que lo primero a lo que debo agradecer es a lo que representa la To-

Esta investigación se ubica en los Fundamentos de la GEOMETRÍA

This investigation is about the foundations of COMPUTATIONAL

1. UBICACIÓN DEL TRABAJO 5

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

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

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

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

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

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

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

2.3. POSTULADOS DE CONEXIÓN DE LA GEOMETRÍA EUCLI-

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

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.3. Estructuras de Datos . . . . . . . . . . . . . . . . . . . . . 33

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

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

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

4.1.2. Algoritmo Incremental . . . . . . . . . . . . . . . . . . . . 57

4.2. TRIANGULACIONES Y FÓRMULA DE EULER . . . . . . . . 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

5. DIAGRAMA DE VORONOI (DV) 73

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

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

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.1. INTRODUCCIÓN DE DATOS . . . . . . . . . . . . . . . . . . . 96