Polynomial stabilization conjecture for iterative convex-hull construction

Let PP be a finite point set in a 22D CAT(0) complex with a single vertex OO. Set H0=PH_0=P; for each i1i\geq 1, let HiH_i be obtained from Hi1H_{i-1} by adding all intersections of shortest paths between pairs of points in Hi1H_{i-1} with edges of the complex.

Polynomial stabilization conjecture. The iterative construction stabilizes after a polynomially bounded number of iterations:

Hk=Hk+1H_k=H_{k+1}

for some polynomially bounded kk.

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.

Sources & referencesView supporting material

Primary source

Anna Lubiw, Daniela Maftuleac and Megan Owen, “Shortest Paths and Convex Hulls in 2D Complexes with Non-Positive Curvature”, arXiv:1603.00847 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.