Are there applications of Voronoi diagrams or Delaunay triangulations where the order in which the points are generated (and given to the algorithm) have some known properties (e.g. concatenation of points belonging to distinct entities, such as when a data set is the union of several pre-existing data sets)?More specifically:Snoeyink and van Kreveld showed that the Delaunay triangulation could be encoded in a good order of the points, in such a way that it could be reconstructed in linear time from the coordinates given in this order (and many equivalent orders). Many other algorithms are known to compute the Voronoi diagram in linear time if the points are randomly distributed.I am wondering if in some practical applications, the order in which the points are generated is close to those good orders (as in, the concatenation or shuffling of several subsequences in a good order).
Voronoi diagrams applications where the input order has some known properties?
delaunay triangulation;voronoi