Skip to main content
2 of 4
added an idea for speeding up the generating of centroidal voronoi diagrams.
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Generating Convex Polygonal Neigborhoods from Triangulations of Discrete Pointsets

The wellknown Delaunay Triangulation $DT$ has as a straight line dual the also wellknown Voronoi Diagram $VD$.

Both are most commonly defined in the Euclidean plane and are primarily beneficial for solving problems related to geometric proximity, but they have also been generalized to higher dimensions, different distance measures and also for problems related to $n$-th nearest neighbor queries up to farthest neighbor queries.

This question is however only related to the planar euclidean case.

Question:

Have analogous "tandems" of triangulations and convex polygonal neighborhoods of discrete pointsets in the euclidean plane already appeared, resp., investigated where the corners of the polygonal neighborhoods are not the circum centers of triangles (which can also be outside of triangles e.g. in random triangulations), but other special points associated to triangles, like the ones listed in the ETC (of which the incircle center seems the most interesting choice because it is guaranteed to be inside the most degenerated triangle with nonzero area and, because it seems to generate polygonal neighborhoods with longer short sides)?

I am especially interested in results related to optimality criteria that the selection of specific triangle points (apart from the circum center) implies for the generated polygonal diagrams.


Additional thoughts:

constructing the polygonal regions from other triangle points might also have positive impact on the convergence rate of generating centroidal $VD$s; the triangulaton of the generated centers of gravity would however still be the $DT$ and after having reached good convergence, switching back to circumcenters could be done.

The question would then be, which of the special triangle points gives better performance improvements: incircle center or centroid? Further question in that respect: can convergence of the algorithm be improved by initially taking as new points for the subsequent $DT$ not the centers of gravity of the generated polygonal regions, but rather the centers of the largest enclosed circles?

Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76