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$ If all points lie in the same plane then all barycenters lie in that plane too. How could the resulting configuration be non-planar? $\endgroup$ – Aretino Jul 27 '18 at 16:56
  • $\begingroup$ @Aretino Your argument is not enough for a guarantee (or do we have different understandings of the word "planar"?). Suppose the initial configuration is random, i.e., with intersections; does the update guarantee an intersection-free drawing? $\endgroup$ – kevin811 Jul 29 '18 at 18:32
  • $\begingroup$ Sorry, I thought planar meant "all in a plane" but I see now that the real meaning is more complex. $\endgroup$ – Aretino Jul 29 '18 at 19:55

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.