Algoritmos Eficientes para la Búsqueda del Elemento de una Red que Contiene un Punto Dado

Abstract

Given a two-dimensional finite element mesh and a point in the plane, we were interested in finding the element to which the point belongs.
In this work four techniques are described that allow to reduce the order of the search algorithm. They are: the uniform grid technique, the quasi-uniform grid technique, the quad-tree technique, and a combination between the first and third ones.
It was found that, for a wide variety of meshes, the last two methods are computationally cheaper both in CPU time and memory requirements.