A FAST ALGORITHM FOR POINT-LOCATION IN A FINITE-ELEMENT MESH

An algorithm for the point-location problem in 2D finite element meshe s as a special case of plane straight-line graphs (PSLG) is presented. The element containing a given point P is determined combining a quad tree data structure to generate a quaternary search tree and a local s earch wave using adjacency information. The preprocessing construction of the search tree has a complexity of O(n . log(n)) and requires onl y pointer swap operations. The query time to locate a start element fo r local search is O(log(n)) and the final point search by 'point-in-po lygon' tests is independent of the total number of elements in the mes h and thus determined in constant time. Although the theoretical effic iency estimates are only given for quasi-uniform meshes, it is shown i n numerical examples, that the algorithm performs equally well for mes hes with extreme local refinement.