One Line and n Points in 3D

Falk Tschirschnitz
Institute for Theoretical Computer Science
ETH Zürich

We analyze a randomized pivoting process involving one line and n points in 3-space. The process models the behavior of the RANDOM-EDGE simplex algorithm on simple polytopes with n facets in dimension n-3. We obtain $\Omega(\log^3 n)$ as a lower bound for the expected number of pivot steps.