crossings of edges of a geometric graph

Question

I am considering geometric graphs $G=(V,E)$ where $V$ is a set of points in $\mathbb{R}^2$ and the edges are straight line segments between vertices. See the image: Now I want to calculate all pairs of edges that cross, i.e. intersect in their interior. I want to do this as efficient as possible. I could brute-force it in time $O(m^2)$ or I could use Bentley–Ottmanns algorithm, for a runtime of $O((m+k)\log m)$ where $m$ denotes the number of edges and $k$ the number of crossings.

Both of these algorithms do not use the graph structure at all. Can I get a more efficient algorithm by using the graph-structure? My literature-search with respect to geometric graphs, did not yield any interesting algorithms regarding my problem.

Answer 1

I think the incremental construction method would be useful here. Start with an empty graph, and add your edges one by one. For each new edge, you want to query the intersections with the current subgraph. This can be done via a binary search over the existing line segments (use e.g. the inner product with the normal vector of the new line segment as a key for the binary search). So, merely counting will take $O(m\log m)$, while reporting all edges will take $O(m\log m + x)$, where $x\in O(m^2)$ is the total number of intersecting pairs of edges.

Note that this algorithm does not really use the structure of the graph, and only treats them as line-segments. I think this is to be expected, as there is no difference between the intersections of this graph and the intersections of the line segments of the graph.