One line and n points
Bernd Gärtner, Falk Tschirschnitz, Emo Welzl, József Solymosi, Pável Valtr · Random Structures and Algorithms · 2003
Abstract We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the R ANDOM ‐E DGE simplex algorithm on simple polytopes with n facets in dimension n − 2. We obtain a tight O (log 2 n ) bound for the expected number of pivot steps. This is the first nontrivial bound for R ANDOM ‐E DGE , which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2‐variable linear programming problems, and we prove a tight Θ( n ) bound for its expected runtime. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003