Open Problem: The \delta-distance Game Sophie Huiberts We say that a full-dimensional simplex conv(a1 , .
Statement
Open Problem: The \delta-distance Game Sophie Huiberts We say that a full-dimensional simplex conv(a1 , . . . , ad+1 ) \subset Rd has the \delta-distance property if for each i = 1, . . . , d + 1 the Euclidean distance between vertex ai and the supporting hyperplane of the opposite face affhull(a1 , . . . , ai−1 , ai+1 , . . . , ad+1 ) is at least \delta. Does Peter have a finite strategy? We say that a full-dimensional simplex conv(a1 , . . . , ad+1 ) \subset Rd has the \delta-distance property if for each i = 1, . . . , d + 1 the Euclidean distance between vertex ai and the supporting hyperplane of the opposite face affhull(a1 , . . . , ai−1 , ai+1 , . . . , ad+1 ) is at least \delta. The \delta-distance game is played between two players, Peter Pivot and Ronald Ratio. We start with a set of points in the unit ball A0 \subset Bd , |A| = d + 1, whose convex hull satisfies the \delta-distance property. In round k \in N Peter will first pick some leaving point l \in A0 , after which Ronald may pick some entering point e \in Bd and set Ak+1 = Ak \cup {e} \ {l}. In his choice, Roland must satisfy two rules: (1) the convex hull of Ak+1 must once again satisfy the \delta-distance property, and (2) e and l must be on opposite sides of the remaining face, i.e., conv(Ak ) \cap conv(Ak+1 ) = conv(Ak \ {l}). The game ends as soon as the simplex contains the origin 0 \in conv(Ak+1 ). Peter wants to finish as soon as possible, while Roland aims to delay this. Does Peter have a finite strategy? And if so, does Peter have a strategy that finishes in poly(d, \delta −1 ) rounds? The \delta-distance game is a model for the simplex method, where Pete
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.