ProbXiv
Explorersign in
Problem archiveProblem record

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.