ner_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B-Model I-Model O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B-Citation I-Citation I-Citation O O O O O O O O O O O O O O O O O O O B-Citation I-Citation O O O O O O O O O O O O O O O O O O O O O O O B-Model I-Model O O O O O B-Model I-Model O O O O O O B-Model I-Model O O O B-Model I-Model O O O O O O O O O O O O O O B-Model I-Model O O O O O O O O O O O O O B-Model I-Model I-Model O O O O O O O O O O O O O O O O B-Model I-Model O O O O O O O O O O
tokens: triangles that connect to these points. 2.3.2 Identifying parent triangles Identifying the triangle which contains a given point can be done most easily by checking every triangle individually by brute force. Since the total cost for finding the triangles containing ALL points scales as , this method rapidly becomes too expensive even for a modest number of triangles and will dominate the CPU time for constructing the tessellation. A simple but effective speed-up is the so-called ‘jump and walk’ method. In this method, we select an initial triangle to start the search for a given point. This might be informed from the previous iteration of the triangulation or simply selected at random. The method then tests each face of the triangle to see if the point lies outside or inside the face. If the point is inside every face, then the triangle contains the point. If outside one or more faces, then the triangle is false. We would then ‘walk’ to the neighbouring triangle closest to the point. We then perform the tests again until the triangle has been correctly identified. 2.3.3 Degenerate triangles One common problem that is found in almost all Delaunay triangulation algorithms is that of degenerate triangles. Consider the simple 2D example where four points are exactly the vertices of a square, A, B, C and D. Due to the symmetry, then both of the triangle pairs ABC–CDA and ABD–BCD are possible triangulations. However, both fail the circumcircle test because the exterior fourth point lies exactly on the circle. There is algorithmically no way to distinguish the two cases. A similar related problem occurs when we compute which triangle contains a given point; if the point lies exactly (to floating point precision) on the line dividing two triangles, then there is no way to distinguish which triangle the point lies in. There are three common solutions to this problem: (i) add a small random perturbation to the positions of one of the points to break the degeneracy; (ii) add a virtual perturbation (without physically moving the particles) to each particle position to force the computation of the degenerate state to fall one side or the other (Edelsbrunner Mücke 1990 ), or (iii) use higher precision when computing the determinants, either using exact floating point arithmetic or long-integer arithmetic (Springel 2010 ). For our purposes, we chose the first solution, partly due to simplicity and secondly due to the fact that even though the Delaunay triangulation can be slightly altered, the Voronoi tessellation is (mainly) unaffected. 2.3.4 Creating the Voronoi tessellation To create the Voronoi tessellation, each face of the cell can be constructed by joining the circumcircle centres of Delaunay triangles that are common between two points. In 2D, this is trivial since each Voronoi cell face is a simple line represented by two points. In 3D, it is more complex since each Voronoi face is a complex polygon with an arbitrary number of vertices.