Załóżmy, że mam n segmentów linii w pozycji ogólnej. Jak mogę szybko policzyć, dla każdego z moich n segmentów, ile innych n-1 przecina?

Mogę to zrobić naiwnie w O (n2) czas. Mogę znaleźć wszystkie skrzyżowania za pomocą dość prostego algorytmu linii przemiatania (Bentley-Ottmann) w czasie O ((n + k) log n), gdzie k jest liczbą takich przecięć, a następnie zsumować przecięcia, które znalazłem w grupie liczy się.

Nie muszęodnaleźć przecięcia; Chcę tylko wiedzieć, ile ich jest. Nie rozumiem, jak zmodyfikować algorytm linii przeciągania, aby był szybszy, ponieważ musi zmienić kolejność dwóch rzeczy na drzewie dla każdego skrzyżowania, i nie mogę wymyślić żadnych innych technik, które nie cierpią z powodu tego samego problemu.

Interesuje mnie również, jak liczyć, ile jest całkowitych skrzyżowań.