1. Sea S un conjunto finito de puntos en el plano. Sea p1 el punto con la coordenada y mínima. Si varios puntos tienen la misma coordenada y mínima, elija el que tiene la menor coordenada x. Pruebe que p1 está en el casco convexo de S.
2. Pruebe el Teorema 13.2.5 para x1 =x0.
3. Pruebe el Teorema 13.2.5 para x1 > x0.
4. Use el algoritmo de Graham para encontrar el casco convexo de los puntos
(10, 1), (7, 7), (3, 13), (6, 10), (16, 4), (10, 5), (7, 13), (13, 8), (4, 4), (2, 2), (1, 8), (10, 13), (7, 1), (4, 8), (12, 3), (16, 10), (14, 5), (10, 9).
5. Utilice el algoritmo de Graham para encontrar el casco convexo de los puntos
(7, 8), (9, 8), (3, 11), (5, 1), (7, 11), (9, 5), (9, 1), (6, 7), (4, 5), (2, 1), (10, 17), (7, 3), (7, 14), (4, 8), (11, 3), (10, 12).
6. Suponga que el algoritmo de Graham se usó para encontrar el casco convexo de un conjunto S de n puntos. Demuestre que si se agrega un punto a S para obtener S′, el casco convexo de S′ se puede encontrar en un tiempo o(n).
Los ejercicios 7 al 10 se refieren a la marcha de Jarvis, otro algoritmo que calcula el casco convexo de un conjunto finito de puntos en el plano. Al igual que el algoritmo de Graham, comienza por encontrar el punto con la coordenada y mínima. Si ésta es igual para varios puntos se elige la que tiene la coordenada x mínima. Después, la marcha de Jarvis encuentra el punto p2 tal que el ángulo de la horizontal al segmento de recta p1, p2 es mínimo. (En caso de empates, se selecciona el punto más alejado de p1). Después de encontrar p1, . . . , pi, la marcha de Jarvis encuentra el punto pi+1 tal que pi−1, pi, pi+1 hacen el menor giro a la izquierda. (En caso de empates, se elige el punto más alejado de pi).
7. Demuestre que la marcha de Jarvis, de hecho, encuentra el casco convexo.
8. Escriba un seudocódigo para la marcha de Jarvis.
9. Encuentre el tiempo en el peor caso para la marcha de Jarvis.
10. ¿Existen conjuntos para los que la marcha de Jarvis sea más rápida que el algoritmo de Graham? Explique su respuesta.
