An alternating digital tree (ADT) algorithm for 3D geometric searching and intersection problems

Abstract

Abstract A searching algorithm is presented for determining which members of a set of n points in an N dimensional space lie inside a prescribed space subregion. The algorithm is then extended to handle finite size objects as well as points. In this form it is capable of solving problems such as that of finding the objects from a given set which intersect with a prescribed object. The suitability of the algorithm is demonstrated for the problem of three dimensional unstructured mesh generation using the advancing front method.