Fast point location algorithm on triangular meshes

This paper is a study of application of persistent data structures to the planar and, in part, also spatial point location. In practice, a simplified method of building persistent red-black binary search tree is considered. It corresponds to the structure of a two-dimensional cell complex. Subsequent use of the structure for searching a certain point in space is shown. The computational mesh consists of triangular (in two dimensions) or tetrahedral (in three dimensions) cells. This fact allows significant simplifications to both implementation of the total order necessary to build the search tree as well as construction of the red-black binary search tree itself. The performance of the algorithm is verified for various meshes (consisting of up to 1846197 cells). Finally, certain further directions of the research are shown.