Editing Computational geometry (section)

==== Static problem ====
In the problems of this category, some input is given and the corresponding output needs to be constructed or found. Some fundamental problems of this type are:
* [[Convex hull]]: Given a set of points, find the smallest convex polyhedron/polygon containing all the points.
* [[Line segment intersection]]: Find the intersections between a given set of line segments.
* [[Delaunay triangulation]]
* [[Voronoi diagram]]: Given a set of points, partition the space according to which points are closest to the given points.
* [[Linear programming]]
* [[Closest pair of points]]: Given a set of points, find the two with the smallest distance from each other.
* Farthest pair of points
* [[Largest empty circle]]: Given a set of points, find a largest circle with its center inside of their convex hull and enclosing none of them. 
* [[Euclidean shortest path]]: Connect two points in a Euclidean space (with polyhedral obstacles) by a shortest path.
* [[Polygon triangulation]]: Given a polygon, partition its interior into triangles
* [[Mesh generation]]
* [[Boolean operations on polygons]]

The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance.