Escuela Técnica Superior

de Ingenierı́a Informática

Boletı́n de Problemas

de

Geometrı́a Computacional

Dpto. de Matemática Aplicada I

Geometrı́a Computacional Boletı́n de problemas

1. Sean →
−
u (u1 , u2 ) y →
−
v (v1 , v2 ) dos vectores del plano. Se define el producto cruz como

→
− u1 u2
u ×→
−
v =
v1 v2

(a) Probar que el producto cruz de dos vectores coincide con el área (con signo) del paralelogramo cuyos
lados son dichos vectores.
(b) Comprobar con un ejemplo que el signo del producto cruz es el mismo que el del ángulo formado
por los vectores. Es decir es negativo (alternativamente, positivo) si, situados los vectores con un
mismo punto origen, el desplazamiento desde → −
u hasta →
−
v se hace en sentido de las agujas del reloj
(alternativamente, contrario a las agujas del reloj).
(c) ¿Qué ocurre si el producto cruz vale 0?
2. Dados tres puntos p(p1 , p2 ), q(q1 , q2 ) y r(r1 , r2 ), probar que al realizar la trayectoria p − q − r hacemos un
giro a la izquierda (alternativamente, derecha) si el siguiente determinante es positivo (alternativamente,
negativo):
1 p1 p2
1 q1 q2
1 r1 r2

3. Diseñar un método, utilizando el producto cruz, para saber si dos segmentos pq y rs se cortan. En caso
afirmativo, indicar cómo se obtiene el punto de corte.
Aplicarlo en los casos: p(2, 0), q(0, 2), r(1, −2), s(4, 1) y p(2, 0), q(0, 2), r(1, −2), s(2, 2)
4. Diseñar un algoritmo que resuelva el siguiente problema: dada una colección P de n puntos en el plano,
encontrar el mayor valor l > 0 tal que si transformamos cada punto (x, y) de P en el (x + ly, y), el orden
de los puntos de P no cambia en la dirección del eje de las X.
5. Dado un conjunto de n puntos en el plano, encontrar en tiempo O(n log n) un polı́gono simple que tenga
a dicho conjunto como sus vértices.
6. Dado un conjunto de n puntos en el plano en posición general, obtener un polı́gono simple x-monótono
que tiene como vértices dichos puntos.
7. Sea P un polı́gono monótono (existe una recta tal que toda perpendicular a dicha recta a lo más corta en
dos puntos al polı́gono). Diseñar un algoritmo que calcule su envolvente convexa en tiempo lineal.
8. Dado un conjunto de n puntos ordenados según su coordenada x, dar un algoritmo que calcule su envolvente
convexa en tiempo O(n).
9. Dado un conjunto S, un semiplano soporte de S es todo semiplano cerrado que contenga a S. r es una
recta soporte de S si uno de los semiplanos que genera es soporte de S y no contiene a ningún semiplano
soporte de S.
(a) Dado un polı́gono convexo P de n vértices y un punto q exterior a él, dar un procedimiento que
permita hallar las rectas soporte a P pasando por q en tiempo O(log n).
(b) Dados dos polı́gonos convexos P y Q, separados por una lı́nea vertical, dar un procedimiento para
calcular las rectas soporte de ambos polı́gonos en tiempo O(n).
10. Dado un conjunto de puntos en el plano S, demostrar que las siguientes dos definiciones de envolvente
convexa son equivalentes:
(a) La envolvente convexa es la intersección de todos los convexos que contienen a S.
(b) La envolvente convexa es el conjunto convexo de menor perı́metro que contiene a S.
Para ello probar que:
i. La intersección de dos convexos es un convexo. Esto implica que la intersección de una familia de
convexos es a su vez un convexo.
ii. El polı́gono de menor perı́metro P que contiene a S es convexo.

[Link]́tica Página 1
Geometrı́a Computacional Boletı́n de problemas

iii. Cualquier conjunto convexo que contenga a S también debe contener a P .

11. Dos conjuntos de puntos A y B se dicen que son linealmente separables si existe una recta r de forma
que cada uno de los conjuntos está contenido en uno distinto de los dos semiplanos abiertos (es decir,
excluyendo la recta) que define dicha recta.
(a) Demostrar que dos conjuntos son linealmente separables si y sólo si lo son sus envolventes.
(b) Demostrar que dos convexos son linealmente separables si y sólo si son disjuntos.
(c) Diseñar un algoritmo que decida cuando dos conjuntos son linealmente separables.
12. Probar que todo polı́gono convexo tiene cuatro vértices N, S, E, O (que pueden coincidir entre ellos)
y cuatro cadenas monótonas entre ellos que son de N a O descendente hacia la izquierda, de O a S
descendente hacia la derecha, de S a E ascendente hacia la derecha y de E a N ascendente hacia la
izquierda.
13. Un polı́gono se dice ortogonal si todas sus aristas son verticales u horizontales. Y un polı́gono ortogonal
se dice ortogonalmente convexo si al intersectar dicho polı́gono con una lı́nea vertical u horizontal resulta
un segmento (pudiendo ser vacı́o).
(a) Encontrar una caracterización similar a la del Problema 12 para polı́gonos ortogonales ortogonalmente
convexos.
(b) Diseñar un algoritmo que decida cuando un polı́gono ortogonal es ortogonalmente convexo.
(c) Diseñar un algoritmo que encuentre la envolvente ortogonalmente convexa de un polı́gono orotogonal
(menor polı́gono ortogonalmente convexo que lo contiene).
14. Sea S un conjunto de n cı́rculos con el mismo radio que pueden cortarse entre sı́. Se pide:
(a) Demostrar que la envolvente convexa de S está formada por arcos de circunferencias de S y segmentos.
(b) Demostrar que cada cı́rculo de S aparece a lo más una vez en la frontera de la envolvente convexa,
salvo casos degenerados de discos alineados, es decir sus centros están en la misma recta.
(c) Sea S 0 el conjunto de los centros de los cı́rculos de S. Demostrar que un cı́rculo de S aparece en la
frontera de la envolvente convexa si y sólo si su centro aparece en la envolvente convexa de S 0 .
(d) Dar un algoritmo O(n log n) que calcule la envolvente convexa de S.
15. Sea E un conjunto no ordenado de n segmentos que forman los lados de un polı́gono convexo. Dar un
algoritmo O(n log n) que calcule, a partir de E, la lista de vértices del polı́gono ordenados angularmente.
16. Dar un algoritmo que, con un preprocesamiento lineal, determine en tiempo O(log n) si un punto está en
el interior o exterior de un polı́gono y-monótono de n vértices.
NOTA: Un polı́gono se dice y-monótono si es monótono respecto del eje OY; es decir, cualquier recta
horizontal corta al polı́gono en un único intervalo, pudiendo este ser vacı́o o reducirse a un punto.
17. Sea un conjunto S de n segmentos disjuntos dos a dos. Diremos que dos puntos se ven si existe un segmento
que los tiene como extremos y que no corta a ningún elemento de S. Dar un algoritmo O(n log n) tal que,
dado un punto p del plano que no esté sobre ningún segmento:
(a) Calcule los segmentos de S que son visibles desde p (p ve a algún punto del segmento).
(b) Calcule los segmentos totalmente visibles desde p (p ve a todos los puntos del segmento).
18. Sea S un conjunto de n segmentos disjuntos dos a dos y sea C el conjunto de sus puntos extremos.
(a) Dado un punto q cualquiera exterior a la envolvente convexa de C, siempre existe al menos un
segmento de S que es totalmente visible desde q. Diseñar un algoritmo que corra en tiempo O(n log n)
para calcular dicho segmento.
(b) ¿Se puede afirmar esta propiedad si q es un punto interior a la envolvente convexa de C?
19. Dar ejemplos de PSLG para los que el método de la banda requiera un preprocesamiento de O(n) y O(n2 ).
20. Describir las mediatrices (lugar geométrico de los puntos que equidistan) de:

[Link]́tica Página 2
Geometrı́a Computacional Boletı́n de problemas

(a) Un punto y una recta.

(b) Dos rectas.
(c) Un punto y un segmento.
(d) Dos segmentos.
21. La distancia d1 (conocida como métrica de Manhattan) entre dos puntos P1 (x1 , y1 ) y P2 (x2 , y2 ) se define
como d1 (P1 , P2 ) = |x1 − x2 | + |y1 − y2 |.
(a) Cı́rculo de centro P y radio r: ¿Cúal es el lugar geométrico de los puntos cuya distancia al punto P
es menor o igual que r?
(b) Mediatriz de P y Q: ¿Cúal es el lugar geométrico de los puntos que equidistan de P y Q?
NOTA: Es conveniente distinguir algunos casos, dependiendo de la posición relativa de P y Q.
(c) Obtener el diagrama de Voronoi de tres puntos.
22. La distancia d∞ (conocida como métrica infinito) entre dos puntos P1 (x1 , y1 ) y P2 (x2 , y2 ) se define como
d1 (P1 , P2 ) = max{|x1 − x2 |, |y1 − y2 |}.
(a) Cı́rculo de centro P y radio r: ¿Cúal es el lugar geométrico de los puntos cuya distancia al punto P
es menor o igual que r?
(b) Mediatriz de P y Q: ¿Cúal es el lugar geométrico de los puntos que equidistan de P y Q?
NOTA: Es conveniente distinguir algunos casos, dependiendo de la posición relativa de P y Q.
(c) Obtener el diagrama de Voronoi de tres puntos.
23. Diseñar un algoritmo, indicando su complejidad, para dados dos conjuntos de puntos A y B, cada uno de
ellos con n puntos, encontrar el mı́nimo de la distancia de un punto de A a uno de B.
24. Sea S una nube de n puntos en el plano, cuyo diagrama de Voronoi tiene v vértices y a aristas.

(a) Probar que v ≤ 2n − 5 y a ≤ 3n − 6.

(b) ¿Cuántos vecinos tiene, de media, cada generador de la nube de puntos?
INDICACIÓN: Téngase en cuenta que, tanto el diagrama de Voronoi como su dual, la triangulación de
Delaunay, son grafos planos y por tanto verifican la fórmula de Euler.

25. Dados n puntos en el plano, dar un algoritmo que encuentre el cı́rculo de menor radio que los contenga.
26. Queremos construir dos centros que den servicio a un conjunto de n ciudades. Su localización debe estar
dentro de la envolvente convexa que delimitan, cumpliendo en cada caso que:
(a) Minimicen la mayor distancia a las ciudades (localización de un recurso deseado, como un hospital).
(b) Maximice la menor distancia a las ciudades (localización de un recurso no deseado, como un vert-
edero).
Dar algoritmos que resuelvan los problemas de localización en tiempo O(n log n).
27. Encontrar un algoritmo tal que dado un conjunto S de n puntos en el plano encuentre el cı́rculo centrado
en algún punto del interior de su envolvente convexa que no contenga puntos de S y que tenga el mayor
radio posible.
28. Dados dos triángulos que comparten una arista formando un cuadrilátero convexo, un flip diagonal consiste
en sustituir la arista que tienen en común por la otra diagonal del cuadrilátero. Demostrar que dadas dos
triangulaciones distintas de un conjunto de puntos siempre es posible pasar de una a otra mediante una
secuencia de flips diagonales.

29. Diseñar un algoritmo eficiente para calcular el área de un polı́gono simple.

30. ¿Es cierto que todo árbol binario es el dual de la triangulación de un polı́gono? Demostrarlo en caso
afirmativo o dar un contraejemplo en caso negativo.

[Link]́tica Página 3
Geometrı́a Computacional Boletı́n de problemas

31. Sea P un polı́gono de n vértices {P1 , P2 , . . . , Pn }. Diremos que tres vértices consecutivos Pi−1 Pi Pi+1
constituyen una oreja del polı́gono si el segmento Pi−1 Pi+1 es una diagonal.
(a) Probar que el dual de una triangulación (excluyendo la cara exterior) es un árbol con vértices de
valencia máxima 3.
(b) Probar que todo polı́gono tiene al menos dos orejas.
(c) Describir un algoritmo de triangulación de un polı́gono, basado en la eliminación de orejas. Indicar
su complejidad.
32. El Teorema de las dos orejas(Teorema de Meister) dice: Excepto los triángulos, todo polı́gono tiene al
menos dos orejas no superpuestas (o sólo comparten un lado o la intersección es vacı́a).
Probar que dadas dos triangulaciones distintas de un mismo polı́gono siempre es posible pasar de una a
otra mediante flips (Indicación: fijar una oreja y utilizar inducción en el resto del polı́gono).
33. Dadas dos triangulaciones de una nube de puntos, diseñar un algoritmo cuadrático que lleve una triangu-
lación a la otra mediante flips.
34. El grafo de Gabriel de un conjunto S de n puntos en el plano es un grafo cuyo conjunto de vértices es S
y dos puntos p, q ∈ S están unidos mediante una arista si y sólo si el cı́rculo de centro el punto medio del
segmento pq y diámetro pq no contiene ningún otro punto de S en su interior.
(a) Probar que el grafo de Gabriel de S está contenido en la triangulación de Delaunay de S.
(b) Probar que una arista de Delaunay es arista del grafo de Gabriel si, y sólo si corta a su arista dual
de Voronoi.
(c) Dar un algoritmo O(n log n) que calcule el grafo de Gabriel de un conjunto de n puntos.
35. Sea S un conjunto de n puntos. Una triangulación voraz (o greedy) de S se obtiene ordenando por su
longitud todas las posibles aristas entre puntos de S y añadiéndolas a la triangulación de menor a mayor,
siempre y cuando la nueva arista no corte a ninguna que se haya añadido anteriormente.
(a) Estudiar los tiempos de ejecución asociados a cada paso en la construcción de una triangulación
voraz, ası́ como orden de ejecución del algoritmo.
(b) Dados los siguientes enunciados probar si son ciertos o dar un contraejemplo si son falsos (donde
d(x, y) representa la distancia euclı́dea entre dos puntos x e y):
i. Supongamos que estamos en un paso intermedio de la construcción de la triangulación, y tenemos
ya dos triángulos abc y bcd (que comparten la arista bc) sin puntos en su interior, formando un
cuadrilátero convexo, entonces d(b, c) = d(a, d).
ii. Consideramos dos puntos p y q de S y sea C el cı́rculo centrado en el punto medio entre p y
q y de diámetro d(p, q). El segmento pq divide a C en dos semicı́rculos. Si ambos semicı́rculos
contienen al menos un punto de S, entonces pq no puede formar parte de la triangulación voraz
de S.
(c) Dar un conjunto cuyas triangulaciones voraz y Delaunay sean distintas.
36. Una triangulación de una nube S de puntos en el plano se dice que es una triangulación de Pitteway si
para cada triángulo (a, b, c), cualquier punto en su interior tiene a uno de los tres puntos a, b o c como el
punto más cercano de la nube. Probar:
(a) Toda triangulación de Pitteway es una triangulación de Delaunay.
(b) No toda triangulación de Delaunay es de Pitteway y por tanto existen nubes de puntos que no
admiten triangulación de Pitteway.
(c) Caracterizar las triangulaciones de Delaunay que son de Pitteway.
37. Dos puntos p y q de un conjunto P de puntos en el plano se dice que son vecinos relativos si no existe
ningún otro punto de P que esté más cerca de p y q simultaneamente. Es decir, no existe ningún otro
punto x ∈ P tal que d(x, p) < d(p, q) y d(x, q) < d(p, q),
El Grafo de Vecindad Relativa , RN G(P ), del conjunto P se define de la forma siguiente: Sus vértices
son los puntos de P ; un segmento pq conectando dos puntos de P serán un arista si, y sólo si, p y q son
vecinos relativos.

[Link]́tica Página 4
Geometrı́a Computacional Boletı́n de problemas

(a) Dados dos puntos p, q ∈ P , se llama lente de focos p y q, lens(p, q), a la intersección de los cı́rculos
abiertos (no incluyendo la circunferencia exterior) de radio d(p, q) y centros en p y q. Probar que p
y q son vecinos relativos si, y sólo si, lens(p, q) no contiene ningún otro puntos de P .
(b) Probar que el Grafo de Vecindad Relativa de P está contenido en el grafo de Delaunay de P .
(c) Diseñar un algoritmo eficiente para calcular RN G(P ).
38. Un corte en un rectángulo es en guillotina si es paralelo a uno de los lados y es maximal en el subrectángulo
en el que es dado. Esto es: el primer corte ha de ir de lado a lado y divide el rectángulo en dos sub-
rectángulos, el siguiente corte también ha de ir de lado a lado en alguno de los subrectángulos obtenidos
en el paso anterior y ası́ sucesivamente.
(a) Diseñar un algoritmo que determine si un rectángulo está dividido por cortes en guillotina.
(b) Diseñar un algoritmo que determine, dado un rectángulo dividido por cortes en guillotina, un orden
en el que se han producido dichos cortes.
(c) Diseñar un algoritmo que localice un punto en un rectángulo dividido por cortes en guillotina.
39. Dado un conjunto con n puntos rojos y n puntos azules, dar un algoritmo que construya una poligonal
que separe ambos conjuntos.
40. (Policı́as y ladrones) Dados dos conjuntos de n puntos en el plano P y L. Un punto en el plano se dice
a salvo si está en el interior de un triángulo formado por puntos de P , en peligro si no está a salvo y
está en el interior de un triángulo formado por puntos de L y sospechoso si no está a salvo ni en peligro.
Determinar un preprocesamiento que permita decidir en tiempo logarı́tmico si un punto dado está a salvo,
en peligro o es sospechoso.
41. Dado un conjunto con n puntos rojos y n puntos azules, dar un algoritmo que una cada punto rojo con un
único punto azul mediante segmentos que no se corten entre sı́ (emparejamiento geométrico bicromático
perfecto).
Indicación: Utilizar el “Teorema del corte ham-sandwich” (Lo, Matousek y Steiger, 1997)
42. Preprocesar un conjunto S de n segmentos disjuntos de tal forma que se pueda responder en tiempo
logarı́tmico a la siguiente pregunta: dado una semirecta horizontal en el sentido positivo r determinar el
primer segmento de S que intersecta r.
43. Dado un conjunto de puntos S y un objeto geométrico G, decimos que G recubre a S si S está incluido
en G. Diseñar algoritmos que dado S encuentren:
(a) El mı́nimo cuadrado recubridor paralelo a los ejes.
(b) El rectángulo recubridor paralelo a los ejes de mı́nima área.
(c) El rectángulo recubridor de mı́nima área.
(d) El polı́gono convexo recubridor de mı́nima área.
(e) El mı́nimo cı́rculo recubridor.
44. Se considera un conjunto de n rectángulos en el plano, de lados paralelos a los ejes coordinados y cuyo
lado inferior se encuentra sobre el eje OX. Se pide:
(a) Dar un algoritmo que calcule el contorno de su unión en tiempo O(n log n).
(b) Describir un preprocesamiento en tiempo O(n log n) tal que, dado un punto sobre el eje OX, nos
permita encontrar, en tiempo O(log n), a cuántos rectángulos pertenece.
45. Sea R un conjunto de n rectángulos de lados paralelos a los ejes coordenados, de forma que sus lados no
están en ningún caso alineados. Diseñar un algoritmo eficiente para obtener el área de la unión de los
rectángulos de R.
46. Se considera un conjunto de n intervalos en la recta. Se pide:
(a) Dar un algoritmo que obtenga su unión en tiempo O(n log n).
(b) Describir un preprocesamiento en tiempo O(n log n) tal que, dado un punto sobre el eje OX, nos
permita encontrar, en tiempo O(log n), a cuántos intervalos pertenece.

[Link]́tica Página 5
Geometrı́a Computacional Boletı́n de problemas

47. Dada una nube de n puntos en el plano, en posición general (no existen ni tres puntos alineados ni cuatro
cocirculares),
(a) ¿Cuántos triángulos distintos se pueden formar?
(b) Un triángulo se dice ”vacı́o” si no contiene a ningún otro punto de la nube. ¿Existen siempre
triángulos vacı́os?
(c) ¿Cuántos triángulos vacı́os pueden formarse simultáneamente sin que se corten sus lados?, ¿depende
este número únicamente de n?
(d) ¿Existen nubes de puntos en las que todos los triángulos son vacı́os?
(e) Diseñar un algoritmo que encuentre un triángulo vacı́o, indicando su complejidad computacional.
48. Sea S un conjunto de n puntos rojos y n puntos azules en el plano. Añadimos un nuevo punto p:
(a) Supongamos que p no tiene color, y le asignaremos el color del punto de S más cercano. Diseñar un
algoritmo que calcule la frontera entre las regiones en las que los nuevos puntos tomarán el color azul
y en las que tomarán el color rojo.
(b) Si p es un punto rojo, se pide:
i. ¿Qué condición debe cumplir p para que la frontera entre los puntos rojos y azules no varı́e?
ii. En el caso en que sı́ varı́e la frontera, indicar un procedimiento para actualizarla.
(En cada apartado se debe indicar el algoritmo empleado y justificar su complejidad)
49. Dada una nube S de n puntos en el plano,

(a) Demostrar que el punto más cercano a cada punto es un vecino suyo en el diagrama de Voronoi (sus
regiones son limı́trofes).
(b) Diseñar un algoritmo, que corra en tiempo O(n log n), para obtener la pareja de puntos de S más
cercanos.
50. Sea S una nube de puntos en el plano. Se define el grafo EM SP (S) como el árbol recubridor de los puntos
de S, de forma que la suma de las longitudes de sus aristas es mı́nima. Se pide:
(a) Probar que el grafo EM SP (S) es un subgrafo del grafo de Delaunay, D(S), que no es otro que el
grafo cuyos vértices son los puntos de la nube y las aristas son las aristas de la triangulación de
Delaunay.
(b) Diseñar un algoritmo para encontrar el grafo EM SP (S), indicando su complejidad.

[Link]́tica Página 6