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. Subse-quent 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 sim-plifications 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 me-shes (consisting of up to 1846197 cells). Finally, certain further directions of the research are shown. Key words:mesh generation, Chimera mathod, point location algorithms 1