Implementation of Balaban's Line intersection algorithm in Mathematica

You'll be interested in the (undocumented!) functions Graphics`Mesh`IntersectQ[] (for checking the intersections) and Graphics`Mesh`FindIntersections[] (for actually finding them). As a sample:

BlockRandom[SeedRandom[42, Method -> "MersenneTwister"]; (* for reproducibility *)
            lins = Table[{Line[RandomReal[1, {2, 2}]]}, {42}];]

Graphics`Mesh`MeshInit[];

pts = FindIntersections[lins]; (* intersection points *)
Graphics[{{AbsoluteThickness[1], lins}, {Directive[Red, AbsolutePointSize[4]], Point[pts]}}]

Is a runtime that's $O(n \log n)$ even achievable? I feel I can create a sequence of line sets with a quadratic amount of intersections:

ReIm[z_] := Through[{Re, Im}[z]]

Graphics`Mesh`MeshInit[];
numInts[n_] := numInts[n] = BlockRandom[
    Length@Graphics`Mesh`FindIntersections[
      Most@Table[Line[{-ReIm[Exp[I t]],ReIm[Exp[I t]]+RandomReal[{0,.1}]}],{t,0,2Pi,2Pi/n}]
    ]
]

Plot[x(x + 1)/2, {x,1,1001}, Epilog -> {Red, Line[{#, numInts[#]}& /@ Range[1, 1001, 100]]}]

and the relative error to $n(n+1)/2$ seems to approach zero:

relError[n_] := 1 - 2numInt[n]/(n(n + 1))

ListLinePlot[{#, relError[#]}& /@ Range[201, 1001, 100]]