How do we select neighboring vertices to ensure that the center point creates traingles with closer areas or even equilateral traingles. How can we decide how many to select in our algorithm.

ellinzhao

if we center a given vertex, then local to that vertex and its neighbors, the "shape" is improved. but are there any global improvements guaranteed? how do we know that other vertices won't be less optimally shaped?

chen-eric

@ellinzhao I believe that the Delaunay process, which already conditions that no vertices should exist within circumcircles, removes in large part most of the irregular triangles which would cause issues globally with centering vertices alone. Centering vertices should be guaranteed to create equilateral triangles globally following conditioning of Delaunay.

akyang

Interesting that Delaunay triangulation is the dual of the Voronoi diagram, so an algorithm used to generate the graph of one problem can be used to solve the other problem.
https://en.wikipedia.org/wiki/Delaunay_triangulation#Relationship_with_the_Voronoi_diagram

How do we select neighboring vertices to ensure that the center point creates traingles with closer areas or even equilateral traingles. How can we decide how many to select in our algorithm.

if we center a given vertex, then local to that vertex and its neighbors, the "shape" is improved. but are there any global improvements guaranteed? how do we know that other vertices won't be less optimally shaped?

@ellinzhao I believe that the Delaunay process, which already conditions that no vertices should exist within circumcircles, removes in large part most of the irregular triangles which would cause issues globally with centering vertices alone. Centering vertices should be guaranteed to create equilateral triangles globally following conditioning of Delaunay.

Interesting that Delaunay triangulation is the dual of the Voronoi diagram, so an algorithm used to generate the graph of one problem can be used to solve the other problem. https://en.wikipedia.org/wiki/Delaunay_triangulation#Relationship_with_the_Voronoi_diagram