Editing Computational geometry (section)

==== Variations ====

Some problems may be treated as belonging to either of the categories, depending on the context. For example, consider the following problem.
* [[Point in polygon]]: Decide whether a point is inside or outside a given polygon.

In many applications this problem is treated as a single-shot one, i.e., belonging to the first class. For example, in many applications of [[computer graphics]] a common problem is to find which area on the screen is clicked by a [[pointer (graphical user interfaces)|pointer]]. However, in some applications, the polygon in question is invariant, while the point represents a query. For example, the input polygon may represent a border of a country and a point is a position of an aircraft, and the problem is to determine whether the aircraft violated the border. Finally, in the previously mentioned example of computer graphics, in [[Computer-aided design|CAD]] applications the changing input data are often stored in dynamic data structures, which may be exploited to speed-up the point-in-polygon queries.

In some contexts of query problems there are reasonable expectations on the sequence of the queries, which may be exploited either for efficient data structures or for tighter computational complexity estimates. For example, in some cases it is important to know the worst case for the total time for the whole sequence of ''N'' queries, rather than for a single query. See also ''[[Amortized analysis]]''.