Springe direkt zu Inhalt

Nils Goldmann:

Solving ACIT: Using implicit LP-type problems for asymmetric convex polytope intersection testing

Kurzbeschreibung

Asymmetric convex intersection testing (ACIT) describes the problem of determining whether two convex polytopes intersect: One given as the convex hull of n points, the other as an intersection of n halfspaces in R^d. We explore the implicit LP-type approach described by Chan et. al. and adapt it to ACIT. Using this approach, we obtain a randomized algorithm solving ACIT in O(binom(n,d) * (nd + d^3)) expected time. This is worse than most existing algorithms, but enhancing a singular subroutine has potential to significantly improve upon this result, up to O(d^O(d) n) expected time.

Abschluss
Master of Science (M.Sc.)
Abgabedatum
24.09.2026