%0 Journal Article %1 citeulike:14335804 %A Krause, R. %A Rank, E. %D 1996 %I Springer %J Computing %K 68u05-computer-graphics-computational-geometry 65n30-pdes-bvps-finite-elements 65d18-computer-graphics-computational-geometry 68p05-data-structures 68p10-searching-and-sorting 05c05-trees %N 1 %P 49--62 %R 10.1007/bf02238357 %T A Fast Algorithm for Point-Location in a Finite Element Mesh %U http://dx.doi.org/10.1007/bf02238357 %V 57 %X An algorithm for the point-location problem in 2D finite element meshes as a special case of plane straight-line graphs (PSLG) is presented. The element containing a given point P is determined combining a quadtree data structure to generate a quaternary search tree and a local search wave using adjacency information. The preprocessing construction of the search tree has a complexity ofO(n·log(n)) and requires only pointer swap operations. The query time to locate a start element for local search isO(log(n)) and the final point search by 'point-in-polygon' tests is independent of the total number of elements in the mesh and thus determined in constant time. Although the theoretical efficiency estimates are only given for quasi-uniform meshes, it is shown in numerical examples, that the algorithm performs equally well for meshes with extreme local refenement.

@article{citeulike:14335804, abstract = {{An algorithm for the point-location problem in 2D finite element meshes as a special case of plane straight-line graphs (PSLG) is presented. The element containing a given point P is determined combining a quadtree data structure to generate a quaternary search tree and a local search wave using adjacency information. The preprocessing construction of the search tree has a complexity ofO(n·log(n)) and requires only pointer swap operations. The query time to locate a start element for local search isO(log(n)) and the final point search by 'point-in-polygon' tests is independent of the total number of elements in the mesh and thus determined in constant time. Although the theoretical efficiency estimates are only given for quasi-uniform meshes, it is shown in numerical examples, that the algorithm performs equally well for meshes with extreme local refenement.}}, added-at = {2017-06-29T07:13:07.000+0200}, author = {Krause, R. and Rank, E.}, biburl = {https://www.bibsonomy.org/bibtex/29cdd853df0ce9eb2d8c444720322999c/gdmcbain}, citeulike-article-id = {14335804}, citeulike-attachment-1 = {krause_96_fast.pdf; /pdf/user/gdmcbain/article/14335804/1107149/krause_96_fast.pdf; 1634b1ec4bb3cc50cedbac10f1fdad41f609e403}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/bf02238357}, citeulike-linkout-1 = {http://link.springer.com/article/10.1007/BF02238357}, doi = {10.1007/bf02238357}, file = {krause_96_fast.pdf}, interhash = {0557db87d928785b23c432fc8c9dd8c5}, intrahash = {9cdd853df0ce9eb2d8c444720322999c}, journal = {Computing}, keywords = {68u05-computer-graphics-computational-geometry 65n30-pdes-bvps-finite-elements 65d18-computer-graphics-computational-geometry 68p05-data-structures 68p10-searching-and-sorting 05c05-trees}, number = 1, pages = {49--62}, posted-at = {2017-04-12 01:02:10}, priority = {2}, publisher = {Springer}, timestamp = {2022-10-10T01:31:39.000+0200}, title = {{A Fast Algorithm for Point-Location in a Finite Element Mesh}}, url = {http://dx.doi.org/10.1007/bf02238357}, volume = 57, year = 1996 }