CGAL users discussion list

[Daniel Duque <>]

Hello everyone,

I have found that for some applications it is desirable to have a 
triangulation
in which each node has "many" neighbours. I understand that for a random
triangulation the mean number of neighbours is fixed to be about 6 from
topological reasons. In my case, 5 is already "many", so in principle it 
seems feasible
to start from a given triangulation (Delaunay, for example), look for 
low-neighbour
nodes, and flip adjacent triangles to increase their neighbour counts. 
Of course, this
would have to be recursively done, since other nodes might be affected 
by this
flipping. A bit like the "Delaunay restore" algorithm I have seen somewhere.

My general question is whether anyone knowns about these sort of 
triangulations,
and how feasible my idea is. I am afraid this turns out to be a hard 
problem, as e.g.
the minimum-weight triangulation.

Thanks you. Best regards,

Daniel