Editing Computational geometry (section)

==== Geometric query problems <span class="anchor" id="Query"></span><span class="anchor" id="Search"></span> ====
{{see also|Spatial query}}

In ''geometric query problems'', commonly known as ''geometric search problems'', the input consists of two parts: the search space part and the [[query (complexity)|query]] part, which varies over the problem instances. The search space typically needs to be [[data pre-processing|preprocessed]], in a way that multiple queries can be answered efficiently.

Some fundamental geometric query problems are:
* [[Range searching]]: Preprocess a set of points, in order to efficiently count the number of points inside a query region.
* [[Point location problem]]: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located.
* [[nearest neighbour search|Nearest neighbor]]: Preprocess a set of points, in order to efficiently find which point is closest to a query point.
* [[Ray tracing (graphics)|Ray tracing]]: Given a set of objects in space, produce a data structure that efficiently tells which object a query ray intersects first.

If the search space is fixed, the computational complexity for this class of problems is usually estimated by:
* the time and space required to construct the data structure to be searched in
* the time (and sometimes an extra space) to answer queries.

For the case when the search space is allowed to vary, see ''{{slink|#Dynamic problems}}''.