Polynomial stabilization conjecture for iterative convex-hull construction
Polynomial stabilization conjecture for iterative convex-hull construction
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.