# A Fast Particle-Locating Method for the Arbitrary Polyhedral Mesh
## 3 Tests and Results
By choosing a much better initial guess of the host cell in GHNNC and GNHHC, the computational efficiency was obviously improved. Thus, the computational efficiency of face-to-face methods relies heavily on the starting host cell. With GNHHC method, only the point-in-cell test was conducted. The computational efficiency of the point-in-cell test depended on the types of the computational cell, i.e., fastest on tetrahedral mesh and slowest on the polyhedral mesh. The reason is that cells with more boundary faces require more CPU time to conduct the operation defined in (8). Octree method had similar computational overheads to the GNHNC methods. The PLUG algorithm (with 400\({}^{3}\) background cubes) was the fastest one among all methods and its computational efficiency was independent of the types of the computational cells. Shown in Figure 10 is the relative CPU times of octree, GNH, GNHNC, GNHHC methods normalized by those of the PLUG method, with background grid of different resolutions. The horizontal axis is the number of background cubes in one spatial direction. The total number of background cubes is \(N_{bc}=n_{bc}^{3}\). The PLUG method was better than octree and GNH methods on all three meshes with any background grids. On the hexahedral mesh, the PLUG method was always the best one, which was about 17.8 times, 50.2 times, 984.9 times, 36.5 times faster than GNHHC, GNHNC, GNH, and octree methods. With a coarse 100\({}^{3}\) background grid, CPU time consumed by PLUG method was about two times that of GNHHC and similar to that of GNHNC on the tetrahedral mesh. As the CPU times of PLUG method reduced very quickly with the increasing resolution of the background grid, the CPU time of the PLUG method was about 15% of that of the GNHHC method and 6.3% of that of the GNHNC, using a 400\({}^{3}\) background grid on the tetrahedral mesh. Similar results were observed on the polyhedral mesh. The PLUG method had the similar computational overheads to the GNHHC method and a little larger expenses than that of the GNHHC method, when using 100\({}^{3}\) background grid. Increasing the number of the background cubes to 400\({}^{3}\), the PLUG method was about 38.7 times faster than the GNHHC method. Figure 9: CPU times consumed by different particle-locating methods on different grids. (**a**) CPU times of PLUG method; (**b**) CPU times of other methods. The proposed PLUG method is faster than GHNHC and independent of the types of meshes if a background grid with adequate cubes is adopted. As the method GNHHC has an optimal starting host cell and only one point-in-cell test is required, the reason for better computational efficiency of the PLUG method is that the point-in-cell test is not conducted for many particles during searching their host cells. In other words, there are many background cubes that are fully contained by a computational cell, since the background cubes are much smaller than computational cells on fine background grid. For clarifying this point of view, we conducted a count of the number of such background cubes during the numerical tests, and the results are shown in Figure 11. The horizontal axis is the given number of the computational cells. The vertical axis is the percentage of the cubes covered by a given number of cells. It should be pointed out that the percentage corresponding to number 5 means the percentage of the background cubes covered by more than four computational cells. The computational efficiency of the PLUG method can be explained by the percentages corresponding to the number 1 and 5 in Figure 11. It can be seen that, with a \(100^{3}\) background grid, the percentage of the background cubes covered by more than four cells was about 18.5%, 99.99%, and 86.9% on the hexahedral mesh, tetrahedral mesh, and the polyhedral mesh, respectively. As a result, the CPU times consumed by the PLUG method on tetrahedral and polyhedral grid were much larger than that on the hexahedral mesh.