how to fix neighbor relationship of newly created tetrahedron after Bowyer-Watson point insertion

Question

I'm implementing Bowyer-Watson point insertion algorithm and I'm wondering if there is any better way to fix neighbor relationship of newly created tetrahedron after a point is inserted.

One possible solution may be every tetrahedron that sharing the inserted point search its neighbor by comparing if there are 3 points are same between two tetrahedrons. But this solution seems slow, I don't know how CGAL implement this. Any ideas?

UPDATE:

the pseudocode of Bowyer-Watson: http://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm

Answer 1

In my opinion your algorithm and the bowyer-watson incremental are the fastest. You can try a point-in polygon test but its very complicated. For example you can search for rectangles and then use a point-in polygon test. Or you can try hierarchical point-in-polygon like the kirkpatrick data structure but it's a very difficult problem.