Supongamos que tengo n segmentos de línea en posición general. ¿Cómo puedo contar rápidamente, para cada uno de mis n segmentos, cuántos de los otros n-1 que intersecta?

Puedo hacer esto ingenuamente en O (n2) hora. Puedo encontrar todas las intersecciones usando un algoritmo de línea de barrido bastante sencillo (Bentley-Ottmann) en O ((n + k) log n), donde k es el número de dichas intersecciones, y luego agregar las intersecciones que encontré en un montón de cuenta.

No necesitoencontrar las intersecciones, sin embargo; Solo quiero saber cuantos hay. No veo cómo modificar el algoritmo de la línea de barrido para ser más rápido, ya que necesita reordenar dos cosas en un árbol para cada intersección, y no puedo pensar en ninguna otra técnica que no tenga el mismo problema.

También me interesa escuchar cómo contar cuántas intersecciones totales hay.