En contexto geometrico

Hallar la interseccin de dos poligonos convexos.



Supongamos que tenemos dos poligonos de R y S lados, respectivamente (con R+S=N, numero de puntos)








Tendremos como mucho R+S cintas



En cada cinta solo intersecamos poligonos de hasta cuatro lados.



-- Determinar la interseccin de dos poligonos de 4 lados o menos llevara un tiempo C, constante.

Por otra parte hay a lo mas R+S regiones. Luego, en total, esto nos llevara C*(R+S)=C*N pasos.