Polynomial stabilization conjecture for iterative convex-hull construction
Statement
Let be a finite point set in a D CAT(0) complex with a single vertex . Set ; for each , let be obtained from by adding all intersections of shortest paths between pairs of points in with edges of the complex.
Polynomial stabilization conjecture. The iterative construction stabilizes after a polynomially bounded number of iterations:
for some polynomially bounded .
The preceding discussion establishes that the convex hull is closed, so the procedure is finite; the conjecture asks for a polynomial bound on the number of iterations needed for stabilization.
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.