Contando cruces en tiempo cuadrático

Ponente(s): Ruy Fabila Monroy, Frank Duque, César Hernández-Vélez, Carlos Hidalgo-Toscano
Una gráfica geométrica es una gráfica cuyos vértices son puntos del plano y sus aristas son segmentos de recta que unen estos vértices. En esta plática damos un algoritmo que dado una gráfica geométrica $G$ de $n$ vértices cuenta cuántos pares de sus aristas se cruzan. El algoritmo corre en tiempo $O(n^2 \log n)$.