Sublinear Geometric Algorithms

2022/01/26 by Chazelle, Bernard, Liu, Ding, Magen, Avner
#Sublinear algorithms #computational geometry

paper · doi:10.4230/dagsemproc.05291.4

Abstract

We present sublinear algorithms to such problems as Detecting of Polytope intersection, Shortest Path on 3D convex Polytopes and volume approximation.

Related

• Computational Geometry Column 35
• Some Algorithmic Problems in Polytope Theory
• On the Verification of the Correctness of a Subgraph Construction Algorithm
• Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
• A Note on Testing Intersection of Convex Sets in Sublinear Time