Adaptive-radius homology computation conjecture for intersections of balls

About 7 years old · traced to

Let X⊂Rn+1\mathcal{X} \subset R^{n+1} be a finite set, let A>0A>0, and let ϵ(x)\epsilon(x) be a positive AA-Lipschitz continuous function. For each x\binXx\bin\mathcal{X}, write B(x,ϵ(x))B(x,\epsilon(x)) for the corresponding ball.

Adaptive-radius homology computation conjecture. One can compute the homology of

∩x∈XB(x,ϵ(x))\cap_{x\in \mathcal{X}}B(x,\epsilon(x))

with XO(n)\mathcal{X}^{O(n)} operations.

This conjecture proposes that the complexity bound known for unions of equal-radius balls extends to intersections of balls with radii varying according to a positive Lipschitz function. The source gives no resolution or further evidence for the conjecture.

References

Primary source

Han Jiadong, “An Adaptive Grid Algorithm for Computing the Homology Group of Semialgebraic Set”, arXiv:1903.02388 (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.