Solving Assymmetric Convex Intersection Testing with Chan’s Randomized Optimization Technique for implicity defined LP-type problems
This thesis considers assymmetric convex intersection testing (ACIT). We are given two convex polytopes, one as the convex hull of a set of points and the other one as the intersection of a set of halfspaces. The question of interest is then whether they have a common point or not. This problem is a special case of polytope intersection detection and has applications in various fields including data analysis.
The algorithm presented here solves the ACIT problem in O(d^^O(d)(n+m)) expected time. It does so by using the LP-type framework, in particular, it uses a method introduced by Chan for implicitly defined LP-type problems.