Geometria Computacional

Cap´ıtulo 1
Introducci´on
1.1. ¿ Qu´e es la geometr´ıa computacional?
La geometr´ıa computacional se ocupa del dise˜no y an´alisis de algoritmos de computaci
´on, para resolver problemas de tipogeom´etrico. En este curso, a menos que se diga
lo contrario, los problemas geom´etricos se refieren al plano de dos dimensiones. La clase de
objetos estudiados, ser´an los puntos del plano,definidos mediante un par de coordenadas
cartesianas, las rectas, los tri´angulos, pol´ıgonos y c´ırculos.
El tema de la geometr´ıa computacional es de data reciente. Los or´ıgenes se encuentran
en latesis doctoral de M. I. Shamos en 1975. Desde entonces el campo se ha expandido
considerablemente con una cantidad apreciable de resultados. La investigaci´on en esta
´area ha encontrado muchasaplicaciones en la vida real: rob´otica, reconocimiento de voz
y de patrones, dise˜no gr´afico, sistemas de informaci´on geogr´afica,...etc.
1.2. Algunos ejemplos importantes
1.2.1. Area de un tri´anguloUn primer problema bastante simple es el siguiente. Consid´erese una recta l en el
plano y un punto p fuera de ella. El problema es responder a la pregunta: ‘ El punto p se
encuentra a la derecha oa la izquierda de l ? ver la figura.
Supongamos que p tiene coordenadas P(x0; y0) y la recta viene dada por la ecuaci´on
y = ax + b.
Podemos suponer, sin p´erdida de generalidad, que la recta noes horizontal ni vertical,
esto es, a 6= 0,1.
5
6 CAP´ITULO 1. INTRODUCCI ´ON
Figura 1.1: el punto p se halla a la derecha de L
Una forma de resolver este problema es la siguiente:
1. Trazamosuna recta horizontal pasando por el punto p.
2. Hallamos el punto q de intersecc´on de l con esta recta horizontal, (Esto se hace
sustituyendo y = y0 en la ecuaci´on de la recta y luego se despeja lacoordenada x ).
Sea q = (x1, y1) el punto en cuesti´on. (N´otese que y1 = y0)
3. Comparamos la coordenada x = x0 del punto p con la coordenada x = x1 del punto
q. Entonces:
1) si x0 = x1 p est´a...