Timeline for Combinatorial distance between simplicial complexes
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 6, 2013 at 3:19 | comment | added | Vidit Nanda | Wlodzimiers, the vertex labels in the drawing are not part of the input data. Basically, you have no idea when one simplex that you would like to remove from $K_1$ is actually isomorphic to another simplex from $K_2$ or not without already knowing the space of all partial simplicial maps $K_1 \to K_2$. To convince yourself that the problem is indeed computationally hard, start with Joseph's picture but remove all the vertex labelings! | |
| Apr 6, 2013 at 2:29 | comment | added | Gerhard Paseman | I think you are crudely off. I am not familiar with simplicial complexes, but I have looked at Boolean minimization in geometric terms, and Joseph's problem strikes me as having some similarity to that. It seems that determining such an edit distance could be NP hard. Gerhard "Could Also Be Crudely Off" Paseman, 2013.04.05 | |
| Apr 6, 2013 at 1:59 | history | answered | Włodzimierz Holsztyński | CC BY-SA 3.0 |