origamimagiro
commented
3 months ago New $O(m \log n)$ algorithm has been tested against all examples in the data set, though the new algorithm can produce different (hopefully better) results due to an adaptive epsilon versus a fixed epsilon with the old algorithm. Here is a graph comparing both algorithm running times on all examples of the instagram data set, resulting in a roughly ~50x speed up on average. Most significant improvement is for processing example 304, which for the old algorithm took ~12 minutes but for the new algorithm takes ~2 secs.
Currently uses an $O(n^2)$-time algorithm to find line intersections. This can be sped up to $O(n\log n)$ using appropriate data structures like an AVL tree.