Euler characteristic of 3D triangulation

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Euler characteristic of 3D triangulation

Adam Getchell
Hello all,

I was debugging my Pachner move code and ran into the lines:

frame #0: 0x000000010000fd61 unittests`CGAL::Triangulation_data_structure_3<CGAL::Triangulation_vertex_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Triangulation_cell_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_cell_base_3<CGAL::Epick, CGAL::Triangulation_ds_cell_base_3<void> > >, CGAL::Parallel_tag>::is_valid(this=0x0000000100703ea8, verbose=false, level=0) const + 769 at Triangulation_data_structure_3.h:3310
   3307       if ( cell_count - facet_count + edge_count - vertex_count != 0 ) {
   3308         if (verbose)
   3309             std::cerr << "Euler relation unsatisfied" << std::endl;
-> 3310         CGAL_triangulation_assertion(false);
   3311         return false;
   3312       }
   3313

Which is, I believe, enforcing the constraint that the Euler characteristic of the 3D (odd-dimensional manifold) is zero.

Now if I look at the (2,3) Pachner move implemented by flip(Cell_handle, facet) I count as follows:



On the left we have:

Cell count: 1345 + 2345 = 2
Facet count: 134 + 135 + 145 + 345 + 234 + 235 + 245 = 7
Edge count: 13 + 14 + 15 + 23 + 24 + 25 + 34 + 35 + 45 = 9
Vertex count: 5

2 - 7 + 9 - 5 = -1 != 0

On the right we have:

Cell count: 1235 + 1234 + 1245 = 3
Facet count: 123 + 125 + 135 + 235 + 124 + 134 + 234 + 145 + 245 = 9
Edge count: 12 + 13 + 14 + 15 + 23 + 24 + 25 + 34 + 35 + 45 = 10
Vertex count: 5

3 - 9 + 10 - 5 = -1 != 0

So, how am I counting wrong? Clearly flip() and flip_really() pass this test.

Looking at the literature[1], they count a triangle in the following manner:

1 2-face (the triangle), 3 1-faces (the edges), 3 0-faces (the vertices), plus the null set = 8. (!)

Any insights appreciated.



Reply | Threaded
Open this post in threaded view
|

Re: Euler characteristic of 3D triangulation

Guillaume Damiand
Hi Adam,


Le 05/04/2016 05:06, Adam Getchell a écrit :
Hello all,

I was debugging my Pachner move code and ran into the lines:

frame #0: 0x000000010000fd61 unittests`CGAL::Triangulation_data_structure_3<CGAL::Triangulation_vertex_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Triangulation_cell_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_cell_base_3<CGAL::Epick, CGAL::Triangulation_ds_cell_base_3<void> > >, CGAL::Parallel_tag>::is_valid(this=0x0000000100703ea8, verbose=false, level=0) const + 769 at Triangulation_data_structure_3.h:3310
   3307       if ( cell_count - facet_count + edge_count - vertex_count != 0 ) {
   3308         if (verbose)
   3309             std::cerr << "Euler relation unsatisfied" << std::endl;
-> 3310         CGAL_triangulation_assertion(false);
   3311         return false;
   3312       }
   3313

Which is, I believe, enforcing the constraint that the Euler characteristic of the 3D (odd-dimensional manifold) is zero.

This is true only if you have a 3D manifold without boundary which is not the case of your two examples below. (One solution to compute Euler characteristic of an object with boundary is to count cells that must be present in the corresponding closed object, which explain the null set in the reference [1]).

For a ball (a 3D manifold with one boundary), the Euler characteristic is 1.

Note that this is also only true if your have only one connected component in your object.

there is another problem: the formula is vertex_count-edge_count+face_count-cell_count (you inverse the signs).

Best
Guillaume




Now if I look at the (2,3) Pachner move implemented by flip(Cell_handle, facet) I count as follows:



On the left we have:

Cell count: 1345 + 2345 = 2
Facet count: 134 + 135 + 145 + 345 + 234 + 235 + 245 = 7
Edge count: 13 + 14 + 15 + 23 + 24 + 25 + 34 + 35 + 45 = 9
Vertex count: 5

2 - 7 + 9 - 5 = -1 != 0

On the right we have:

Cell count: 1235 + 1234 + 1245 = 3
Facet count: 123 + 125 + 135 + 235 + 124 + 134 + 234 + 145 + 245 = 9
Edge count: 12 + 13 + 14 + 15 + 23 + 24 + 25 + 34 + 35 + 45 = 10
Vertex count: 5

3 - 9 + 10 - 5 = -1 != 0

So, how am I counting wrong? Clearly flip() and flip_really() pass this test.

Looking at the literature[1], they count a triangle in the following manner:

1 2-face (the triangle), 3 1-faces (the edges), 3 0-faces (the vertices), plus the null set = 8. (!)

Any insights appreciated.


Adam Getchell
about.me/adamgetchell



-- 
===================================================================
Guillaume DAMIAND

CNRS - LIRIS UMR 5205
Université Claude Bernard
Bâtiment Nautibus (710)
43 Boulevard du 11 Novembre 1918
69622 Villeurbanne Cedex (France)
-------------------------------------------------------------------
Tél: +33 (0)4.72.43.14.34                 Fax: +33 (0)4.72.43.15.36
Mail: [hidden email]
Web: http://liris.cnrs.fr/guillaume.damiand/
===================================================================

smime.p7s (3K) Download Attachment