Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex.

Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that with such an update one can guarantee that the planarity is preserved at each step (after each point is moved). But could planarity be guaranteed in case whole configuration moves simultaneously?

I understood that once such simultaneous position update converges (in case the positions of the points of the outer convex face are fixed), it can be guaranteed that the new tiling is also planar (Tutte's embedding). My question is: given no fixed positions, what happens if one performs a single simultaneous coordinate update from the initial configuration that is already planar (all faces convex)?

In case no guarantees can be made, are there special cases with which the simultaneous update would preserve planarity, i.e., special kinds of initial configurations, etc?

In mathematical terms: The initial configuration is $Y_0$, and can be written as $Y_0 = T_0Y_0$, where $T_0$ is a transition matrix (each row/column having weight coefficients expressing each coordinate as a convex combination of its neighbors). The update is achieved as $Y_1 = T_bY_0$, where $T_b$ is a transition matrix that moves a configuration to the barycenter (a simultaneous update). Obviously, $Y_1 = T'Y_0$, where $T'$ is also a transition matrix $T' = T_bT_0$. But is that sufficient to guarantee that $Y_1 = T''Y_1$, for some transition matrix $T''$, i.e., each coordinate is a convex combination of its neighbors?

  • $\begingroup$ I do not understand your question: since everything is in 2d, your barycenters are also 2d, thus everything remains planar no ? (Or here is something I did not get). $\endgroup$ – BrunoLevy Aug 2 '18 at 14:08
  • $\begingroup$ @BrunoLevy "planar" means something different here: it is a drawing in which no edges cross. $\endgroup$ – kevin811 Aug 26 '18 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.