in the plane in time complexity of and space complexity of .

Since then, this approach has been used to design efficient algorithms for a number of problems in computational geometry, such as the construction of the Voronoi diagram (Fortune's algorithm) and the Delaunay triangulation or boolean operations on polygons.

Generalizations and extensions