half-edge data structure delaunay triangulation

I am writting Python delaunay triangulation with half edge data structure.

Also, in triangulation algorithm, I try to store only half-edges. I retrieve triangles from the list of edges.

However, this is pretty redundant, right? I have much more edges than needed to describe triangles, since one triangle is defined by one edge and can be walked through easily since each edge has got a pointer to the next.

1/ is that OK to implement Watson algo for delaunay storing only a list of half-edges? Will it be difficult then to walk through?

In Watson's algorithm step to determine the edges inside the cavity, I would like to walk on edges and find those edges vertices that are at the end of more than three distinct half-edges.

2/ Is this property 'more than two edges end at this vertex' a correct an appropriate criterion to discard edges in Bowyer Watson algo?

For walking through the mesh, I would iterate on each half-edge. So, I am working edge by edge, not triangle by triangle. I am walking through the mesh without using the 'next' property, which sounds not good.

3/ What is the way to walk through the triangles in the mesh, stored as a list of edges? Or how to better store the mesh so as to make the walk through it easier?



Half-edge data structure is fine! Use a list of faces and a list of edges, this may be sufficient.


 ? Calculate bounding polygon of alpha shape from the Delaunay triangulation
 ? Confusion on Delaunay Triangulation and Largest inscribed circle
 ? Creating a Delaunay Triangulation around Polygons
 ? Equivalent to Lloyd's algorithm using solelly the Delaunay triangulation
 ? Complexity of nested for loops starting from the last iteration
 ? Complexity of nested for loops starting from the last iteration
 ? Complexity of nested for loops starting from the last iteration
 ? Time complexity of nested for-loop
 ? Time complexity for 3 nested loops with 2 variables
 ? Time complexity of iterating over a k-layer deep loop nest always Θ(nᵏ)?