Logo_iSurf_org

Subscribe
to eAlerts

for Geom Site
Updates

CLICK HERE

 

What are Examples?

by Dan Sunday

 

 

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 n-vertex polygon

O(n)

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

O(n log n)

Triangulate a simple connected n-vertex polygon

O(n)

Triangulate an n-vertex polygon with holes

O(n log n)

Partition an n-vertex polygon into a minimal number of convex pieces

O(n3)

Determine if a point lies inside an n-vertex 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 n-vertex 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 n-vertex convex polygon

O(log n)

Find an extreme point of an n-vertex convex 3D polyhedron

Prep O(n)
Query O(log n)

Find the first point of contact (visibility) between a ray and a simple planar n-vertex 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 k-vertex 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(n2)

 

 

© Copyright 2012 Dan Sunday, 2001 softSurfer