A Method for Solving Mass Point-in-Covering Problems for Arbitrary Coverings Using GPU

摘要

Results of numerical experiments in solving mass problems of determining membership of a set of points in a set of arbitrary shapes covering a domain or intersecting with each other in a space of arbitrary dimension are discussed. The problems are solved using geometrical techniques on graphics processors. The proposed solution can outperform the fastest classical algorithms by a factor from 6 to 700 in terms of speed. As an example, the construction of grids for computations within a geophysical model of the Earth is used. Such problems are typical for all the numerical computations involving geometric modeling where coverings or triangulations are used or rendering problems are solved.