术语“几何范围”的详细信息

英译术语:

geometric range

汉语语境:

在几何范围内搜索，算法被认为是下面的问题类型。给定一组n-point P在平面上，构建一个数据结构，给定一个查询三角形R P躺在R点的数量可以很快确定。类似的问题可以在更高的维度，要求点集与三角形取代单形或更复杂的形状。这种类型的算法在计算几何至关重要，因为它们可以作为子程序在解决许多看似无关的问题，通常出于实际应用，例如在计算机图形学中(射线追踪、隐面消除等)。

英语语境:

In geometric range searching, algorithmic problems of the following type are considered. Given an n-point set P in the plane, build a data structure so that, given a query triangle R, the number of points of P lying in R can be determined quickly. Similar questions can be asked for point sets in higher dimensions, with triangles replaced by simplices or by more complicated shapes. Algorithms of this type are of crucial importance in computational geometry, as they can be used as subroutines in solutions to many seemingly unrelated problems, which are often motivated by practical applications, for instance in computer graphics (ray tracing, hidden-surface removal, etc.).