We present simpler algorithms for two closely related morphing problems, both based on the barycentric interpolation paradigm introduced by Floater and Gotsman, which is in turn based on Floater's asymmetric extension of Tutte's classical spring-embedding theorem. First, we give a much simpler algorithm to construct piecewise-linear morphs between planar straight-line graphs. Specifically, given isomorphic straight-line drawings $\Gamma_0$ and $\Gamma_1$ of the same 3-connected planar graph $G$, with the same convex outer face, we construct a morph from $\Gamma_0$ to $\Gamma_1$ that consists of $O(n)$ unidirectional morphing steps, in $O(n^{1+\omega/2})$ time. Our algorithm entirely avoids the classical edge-collapsing strategy dating back to Cairns; instead, in each morphing step, we interpolate the pair of weights associated with a single edge. Second, we describe a natural extension of barycentric interpolation to geodesic graphs on the flat torus. Barycentric interpolation cannot be applied directly in this setting, because the linear systems defining intermediate vertex positions are not necessarily solvable. We describe a simple scaling strategy that circumvents this issue. Computing the appropriate scaling requires $O(n^{\omega/2})$ time, after which we can can compute the drawing at any point in the morph in $O(n^{\omega/2})$ time. Our algorithm is considerably simpler than the recent algorithm of Chambers et al. (arXiv:2007.07927) and produces more natural morphs. Our techniques also yield a simple proof of a conjecture of Connelly et al. for geodesic torus triangulations.
翻译:我们为两个密切相关的变形问题提供了更简单的算法, 其依据是Floater 和 Gotsman 推出的2007年以巴中心为中心的内推范式, 后者基于Floater 对Tutte 古典春装饰理论的不对称扩展。 首先, 我们给出一个更简单的算法, 以在平面直线图之间构建小线- 线性变形。 具体地说, 给出的是, 直线图的经典边线图$\Gamma_ 0美元和 $\Gamma_ 1美元, 同一三连接平面的平面的2007年平面图中的 $G$, 我们建造了一个从$Gamma_ 0美元到$Gamma_ 1美元的变形变形。 第二, 我们描述单平面的平面的平面变形变形变形法, 直径直到直流的直线系统。 我们的自然变形变形变形法, 也无法在平面的平面上直线性变法, 。 我们的平面变平面的平面的变法将一个自然变的变法 直向向直向直向, 。