Morphing Rectangular Duals

12/06/2021
by   Steven Chaplick, et al.
0

We consider the problem of morphing between rectangular duals of a plane graph G, that is, contact representations of G by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. If we require that we have a rectangular dual continuously throughout the morph, then a morph only exists if the source and target rectangular duals realize the same REL. Hence, we are less strict and allow intermediate contact representations of non-rectangular polygons of constant complexity (at most 8-gons). We show how to compute a morph consisting of O(n^2) linear morphs in O(n^3) time. We implement the rotations of RELs as linear morphs to traverse the lattice structure of RELs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset