Suponha que eu tenha n segmentos de linha na posição geral. Como posso contar rapidamente, para cada um dos meus n segmentos, quantos dos outros n-1 se cruzam?

Eu posso fazer isso ingenuamente em O (n2) Tempo. Eu posso encontrar todas as interseções usando um algoritmo de varredura razoavelmente direto (Bentley-Ottmann) no tempo O ((n + k) log n), onde k é o número de tais interseções e agregar as interseções que eu encontrei em um grupo de conta.

Eu não precisoencontrar os cruzamentos, no entanto; Eu só quero saber quantos existem. Não vejo como modificar o algoritmo de varredura para ser mais rápido, já que ele precisa reordenar duas coisas em uma árvore para cada interseção, e não consigo pensar em nenhuma outra técnica que não sofra do mesmo problema.

Também estou interessado em saber como contar quantos cruzamentos totais existem.