We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Approximate shortest paths
- Polyhedral intersection
- Sublinear algorithms