What are some Examples of Geometry Algorithms ?
The past five decades have seen phenomenal advances in our knowledge about geometry algorithms. The activity has been so great and so original that one might even consider it to be a long overdue revival. But, it is more than just shaking the bones of Greek skeletons in front of us. The massive nature of the problems involved goes as far beyond the Greeks as they went beyond the Egyptians. Some of the most significant achievements are given in a recent report Strategic Directions in Computational Geometry. Notable examples are:
Problem

Best Known Solution

Find the area of an nvertex polygon

O(n)

Find the 2D or 3D convex hull of n points

O(n log n)

Triangulate a simple connected nvertex polygon

O(n)

Triangulate an nvertex polygon with holes

O(n log n)

Partition an nvertex polygon into a minimal number of convex pieces

O(n^{3})

Determine if a point lies inside an nvertex polygon

O(n)

Determine a point's location in a convex planar graph with n edges

Prep O(n log n) Query O(log n)

Construct the Voronoi diagram of a set of n points

O(n log n)

Construct the Delaunay triangulation of a set of n points

O(n log n)

Construct the nearest neighbor graph for a set of n points

O(n log n)

Find the largest empty circle inside a set of n points

O(n log n)

Find the smallest circle enclosing a set of n points

O(n log n)

Construct the minimal spanning tree of a planar graph with n edges

O(n log n)

Determine all k intersection points of a set of n finite line segments in the plane

O(n log n + k)

Determine if an nvertex polygon is simple

O(n log n)

Determine the union or intersection of two polygons with n vertices in total and k edge intersect points

O(n log n + k)

Determine the intersection of two convex polygons with n vertices in total

O(n)

Find an extreme point of an nvertex convex polygon

O(log n)

Find an extreme point of an nvertex convex 3D polyhedron

Prep O(n) Query O(log n)

Find the first point of contact (visibility) between a ray and a simple planar nvertex polygon

Prep O(n) Query O(log n)

Construct the planar exterior visibility map for a set of polygon obstacles with n vertices in total

O(n log n)

Find the shortest planar path for a kvertex polygon (robot) moving (with translations only) past polygon obstacles with n vertices in total

O(kn log kn)

Find the shortest planar path for a line segment (robot) moving (with translation and rotation) past polygon obstacles with n vertices in total

O(n^{2})


