Gibt es eine effiziente Möglichkeit, die Anzahl der Schnittpunkte in einer gegebenen Gruppe von Liniensegmenten zu zählen?

Question

Angenommen, ich habe n Liniensegmente in der allgemeinen Position. Wie kann ich schnell für jedes meiner n Segmente zählen, wie viele der anderen n-1 es schneidet?

Ich kann dies naiv in O (n) Zeit tun. Ich kann alle Schnittpunkte mit einem ziemlich einfachen Sweepline-Algorithmus (Bentley-Ottmann) in der Zeit O ((n + k) log n) finden, wobei k die Anzahl solcher Schnittpunkte ist, und dann die Schnittpunkte, die ich gefunden habe, zu einem Haufen zusammenfassen zählt.

Ich brauche nicht finden Sie die die Kreuzungen, obwohl; Ich möchte nur wissen, wie viele es sind. Ich sehe nicht, wie man den Sweep-Line-Algorithmus ändert, um schneller zu sein, da er für jeden Schnittpunkt zwei Dinge in einem Baum neu anordnen muss, und ich kann mir keine anderen Techniken vorstellen, die nicht an demselben Problem leiden.

Ich bin auch interessiert zu hören, wie man zählt, wie viele totale Kreuzungen es gibt.

Answer 1

Ich habe eine harte Zeit zu glauben, dass Sie im allgemeinen Fall besser als Bentley Ottman tun können. Sie können die Berechnung ein wenig vereinfachen, wenn es Ihnen egal ist, wo sich die Liniensegmente schneiden, aber ich sehe nicht, wie Sie Kreuzungen zählen könnten, ohne sie zu finden.

Im Wesentlichen ist Bentley Ottman eine Möglichkeit, den Suchraum für Kreuzungen zu vereinfachen. Es gibt andere Möglichkeiten, die für bestimmte Anordnungen von Liniensegmenten funktionieren könnten, aber wenn es keine vorhersagbare geometrische Beziehung zwischen Ihren Segmenten gibt, werden Sie nicht in der Lage sein, zuerst eine clevere Methode zu verwenden, um Kandidatenkreuzungen in Kombination mit einem zu finden individuelle Überprüfung jedes Kandidaten.

Wenn Ihre Problemdomäne nicht über bestimmte Funktionen verfügt, die eine verwertbare Substruktur bieten könnten, würde ich meinen, dass Sie Bentley Ottman (oder einen ähnlichen, übergreifenden Algorithmus) für die parallele Ausführung verwenden sollten. (Das Zuschneiden der Liniensegmente in Bänder ist einfach. Das Herausfinden einer optimalen Menge von Bändern wäre ebenfalls interessant.) Natürlich ist das eher eine praktische als eine akademische Übung; der parallele Algorithmus könnte am Ende mehr Arbeit machen; Es nutzt nur Hardware, um die Arbeit in (einem konstanten Faktor) weniger Zeit zu erledigen.