Which the algorithm of triangulation is the faster among existings? does he exist with complexity O(N)? Which algorithm is used by OpenGl? I implemented the algorithm with dynamic cache of searching triangle, but it is slow
You can use an incremental algorithm and a monster curve to presort the points. Translate x- and y coordinate to a binary and concatenate it and sort the points. I think it can work with other triangulation but I recommend to try it with bowyer-watson. You can look into CGAL sourcecode it uses a monster curve and bowyer-watson.