# The flip diameter of rectangulations and convex subdivisions.

We study the configuration space of rectangulations and convex subdivisions of n points in the plane. It is shown that a sequence of O(n log n) elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of n points. This bound is the best possible for some point sets, while [THETA](n) operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of n points in the plane.

Keywords: rectangulation, combinatorial geometry

1 Introduction

The study of rectangular subdivisions of rectangles is motivated by VLSI floorplan design  and cartographic visualization [14, 26, 33]. The rich combinatorial structure of rectangular floorplans has also attracted theoretical research [6, 15]. Combinatorial properties lead to efficient algorithms for the recognition and reconstruction of the rectangular graphs induced by the corners of the rectangles in a floorplan [22, 32], the contact graphs of the rectangles [25, 40], and the contact graphs of the horizontal and vertical line segments that separate the rectangles . The number of combinatorially different floorplans with n rectangles is known to be B(n) = [THETA]([8.sup.n]/[n.sup.4]), the nth Baxter number .

Rectangular subdivisions in the presence of points have also been studied in the literature. Given a finite set P of points in the interior of an axis-aligned rectangle R, a rectangulation of (R, P) is a subdivision of R into rectangles by pairwise noncrossing axis-parallel line segments such that every point in P lies in the relative interior of a segment (see Figure 1).

[FIGURE 1 OMITTED]

Finding a rectangulation of minimum total edge length has attracted attention [7, 8, 13, 19, 20, 21, 28, 30] due to its applications in VLSI design and stock cutting in the presence of material defects. This problem is known to be NP-hard , however, its complexity is unknown when the points in P are in general position in the sense that they have distinct x- and y-coordinates, that is, the points are noncorectilinear. It is not hard to see that in this case the minimum edge-length rectangulation must consist of exactly n line segments . For the rest of this paper, we consider only noncorectilinear point sets P, and rectangulations determined by |P| line segments, one containing each point in P.

The space of all the rectangulations of a point set P (within a rectangle R) can be explored using the following two elementary operators introduced in  (refer to Figure 2).

[FIGURE 2 OMITTED]

Definition 1 (Flip) Let r be a rectangulation of P and let p [member of] P be a point such that the segment s that contains p does not contain any endpoints of other segments. The operation FLIP(r, p) changes the orientation of s from vertical to horizontal or vice-versa.

Definition 2 (Rotate) Let r be a rectangulation of P. Let [s.sub.1] = ab be a segment that contains p [member of] P. Let [s.sub.2] = cd be a segment such that c lies in ap [subset] [s.sub.1] and ac does not contain any endpoints of other segments. The operation ROTATE (r, c) shortens [s.sub.1] to cb, and extends [s.sub.2] beyond c until it reaches another segment or the boundary of R.

For a finite set of noncorectilinear points P [subset] R, we denote by G(P) = (V, E) the graph of rectangulations of P, where the vertex set is V = {r : r is a rectangulation of P} and the edge set is E = {([r.sub.1], [r.sub.2]) : a single flip or rotate operation on [r.sub.1] produces [r.sub.2]}. Since both operations are reversible, G(P) is an undirected graph. It is not hard to show that G(P) is connected , and there is a sequence of O([n.sup.2]) flip and rotate operations between any two rectangulations in G(P) when P is a set of n points in R. It is natural to ask for the diameter of G(P), which we call the flip diameter of P for short. For every set of n points in R, the flip diameter is at least [ohm](n), since every point set admits a rectangulation with all horizontal segments and one with all vertical segments, and each operation modifies at most two segments.

Results

In this paper, we show that the flip diameter of P is O(n log n) for every n-element noncorectilinear point set P (Section 2), and it is [ohm](n log n) for some n-element noncorectilinear point sets (Section 3). However, there are n-elements noncorectilinear points sets for which the flip diameter is [THETA](n) (Section 4). That is, the flip diameter is always between O(n log n) and [ohm](n), depending on the point configuration, and both bounds are the best possible.

We extend the flip and rotate operations and the notion of flip diameter to convex subdivisions (Section 5). A convex subdivision of a set P [subset] [R.sup.2] of points is a subdivision of the plane into convex faces by pairwise noncrossing line segments, halflines, and lines, each of which contains exactly one point of P. We show that the flip diameter for the convex subdivisions of n points is always O(n log n) and sometimes [THETA](n).

Related work

Determining the exact number of rectangulations on n noncorectilinear points remains an elusive open problem in enumerative combinatorics [2, 3]. Recently, Felsner  proved that every combinatorial floorplan with n + 1 rooms can be embedded into every set of n noncorectilinear points, hence every set of n noncorectilinear points has at least B(n) = [THETA]([8.sup.n]/[n.sup.4]) rectangulations.

The currently best known upper bound, O([18.sup.n]/[n.sup.4]) by Ackerman , uses the so-called "cross-graph" charging scheme [35, 36], originally developed for counting the number of (geometric) triangulations on n points in the plane. This method is based on elementary "flip" operations that transform one triangulation into another. Lawson  proved that every triangulation on n points in the plane in general position (i.e., no three on a line) can be transformed into the Delaunay triangulation with O([n.sup.2]) flips, and this bound is the best possible by a construction due to Hurtado et al. . However, for n points in convex position, 2n-10 flips are sufficient, due to a bijection with binary trees with n - 2 internal nodes . Hence the flip diameter of every triangulation on n points in the plane is always between [THETA](n) and [THETA]([n.sup.2]) depending on the point configuration. Eppstein et al.  and Buchin et al.  define two elementary flip operations on floorplans, in terms of the directed dual graph, and solve optimization problems on floorplans by traversing the flip graph.

Generalizing simultaneous edge flips in a triangulation, Meijer and Rappaport  considered simultaneous edge flips in convex decompositions of a point set P. A convex decomposition of P is a subdivision of the convex hull of P into convex polygons whose joint vertex set is P; and two convex decompositions of P are related by a simultaneous edge flip if their union contains no crossing edges.

2 An Upper Bound on the Flip Diameter of Rectangulations

In this section, we show that for every set P of n noncorectilinear points in a rectangle R, the diameter of G(P) is O(n log n).

Theorem 1 For every noncorectilinear set P of n points in the plane, the diameter of the graph G(P) is O( n log n).

Given a rectangulation r of P, we construct a sequence of O(n log n) operations that transforms r into a rectangulation with all segments vertical (a canonical rectangulation). Our method relies on the concept of independent sets, defined in terms of the bar visibility graph. Let r be a rectangulation of P. The bar visibility graph [12, 38, 42] on the horizontal segments of r is defined as a graph H(r), where the vertices correspond to the horizontal segments in r; and two horizontal segments [s.sub.1] and [s.sub.2] are adjacent in H(r) if and only if there are points a [member of] [s.sub.1] and b [member of] [s.sub.2] such that ab is a vertical segment (not necessarily in r) that does not intersect any other horizontal segment in r. It is clear that the bar visibility graph is planar.

Observe that we can always change the orientation of any line segment s with O(n) operations: successively shorten s using rotate operations until s contains no other segment endpoints, and then flip s. This simple procedure is formulated in the following subroutine.
```Shorten&Flip(r, s). Let s be a segment in a rectangulation r. Assume
s = ab and p [member of] P is in the relative interior of s. While s
contains the endpoint of some other segment, let [c.sub.1] [member of]
s and [c.sub.2] [member of] s be the endpoints of some other segments
closest to a and b, respectively (possibly [c.sub.1] = [c.sub.2]). If
p [??] a[c.sub.1], then apply ROTATE(r, [c.sub.1]) to shorten s = ab
to [c.sub.1]b. Else, apply ROTATE (r, [c.sub.2]) to shorten s to
a[c.sub.2]. When s does not contain the endpoint of any other segment,
apply FLIP(r, p).
```

The proof of Theorem 1 follows from a repeated invocation of the following lemma.

Lemma 1 Let r be a rectangulation of a set of n pairwise noncorectilinear points in a rectangle R. There is a sequence of O(n) flip and rotate operations that turns at least one quarter of the horizontal segments into vertical segments, and keeps vertical segments vertical.

Proof: By the four color theorem , H(r) has an independent set I that contains at least one quarter of the horizontal segments in r. The total number of endpoints of vertical segments that lie on some horizontal segment in I is O(n). Successively call the subroutine Shorten&Flip(r, s) for all horizontal segment s [member of] I.

The horizontal segments in I are shortened and flipped into vertical orientation. All operations maintain the invariants that (1) the segments in I are pairwise disjoint, and (2) the remaining horizontal segments in I form an independent set in the bar visibility graph (of all horizontal segments in the current rectangulation). It follows that each operation either decreases the number of horizontal segments in I (flip), or decreases the number of segment endpoints that lie in the relative interior of a segment in I (rotate). After O(n) operations, all segments in I become vertical. Since only the segments in I are flipped (once each), all vertical segments in r remain vertical, as required.

Proof of Theorem 1.: Let P be a set of n pairwise noncorectilinear points in a rectangle R. Denote by [r.sub.0] the rectangulation that consists of n vertical line segments, one passing through each point in P.

We show that every rectangulation [r.sub.1] of P can be transformed into [r.sub.0] by a sequence of O(n log n) flip and rotate operations. By Lemma 1, a sequence of O(n) operations can decrease the number of horizontal segments by a factor of at least 4/3. After at most log n/ log(4/3) invocations of Lemma 1, the number of horizontal segments drops below 1, that is, all segments become vertical and we obtain [r.sub.0].

Remark. The proof of Theorem 1 is constructive, and provides an algorithm for transforming a rectangulation on n noncorectilinear points to the rectangulation with n vertical segments. If the rectangulations are maintained in a doubly connected edge list (DCEL) data structure, then a flip or rotate operation can be implemented in O(1) time, and the bar-visibility graph can be computed in O(n) time. The bottleneck of the overall running time is the 4-coloring of the bar-visibility graph. The current best algorithm for 4-coloring an m-vertex planar graph runs in O([m.sup.2]) time , and a repeated call to this algorithm to exponentially decaying bar-visibility graphs takes O([n.sup.2]) time. If we use an O(m)-time 5-coloring algorithm [10, 18, 41], up to log n/ log(5/4) times, the overall running time improves to O(n).

3 A Lower Bound on the Flip Diameter of Rectangulations

We show that the diameter of the graph G(P) is [ohm](n log n) when P is an n-element bit-reversal point set (alternatively, Halton-Hammersley point set) [9, Section 2.2]. For every integer k [greater than or equal to] 0, we define a point set [P.sub.k] of size n = [2.sup.k] with integer coordinates lying in the square R = [[-1, n].sup.2]. For an integer m, 0 [less than or equal to] m < [2.sup.k], with binary representation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the bit-reversal gives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The bit-reversal point set of size n = [2.sup.k] is [P.sub.k] = {(m, y(m)) : m = 0, 1,..., n - 1}. By construction, no two points in [P.sub.k] are corectilinear.

[FIGURE 3 OMITTED]

We establish a lower bound of k[2.sup.k-3] for the diameter of G([P.sub.k]) using a charging scheme. We define k[2.sup.k-1] empty rectangles (called boxes) spanned by [P.sub.k], and charge one unit for "saturating" a box with vertical segments (as defined below). We show that when a rectangulation with all horizontal segments is transformed into one with all segments vertical, each box becomes saturated. We also show that each rotate (resp., flip) operation contributes a total of at most 2 (resp., 4) units to the saturation of various boxes in our set. It follows that at least (k[2.sup.k-1])/4 = k[2.sup.k-3] = n log n/8 operations are required to saturate all k[2.sup.k-1] boxes.

Consider the point set [P.sub.k] for some k [member of] [??]. We say that a rectangle B [subset] [[-1, n].sup.2] is spanned by [P.sub.k] if two opposite corners of B are in [P.sub.k]; and B is empty if its interior is disjoint from [P.sub.k].

Let B be the set of closed rectangular boxes spanned by point pairs in [P.sub.k] in which the binary representation of the x-coordinates ([b.sub.1],..., [b.sub.k]) differ in precisely one bit. See Figure 3 for examples. Each point in [P.sub.k] is incident to k boxes in [??], since there are k bits. Every box in [??] is spanned by two points of [P.sub.k], thus |[??]| = k x |[P.sub.k]|/2 = k[2.sup.k-1].

Each point is incident to k boxes of sizes [2.sup.i-1] X [2.sup.k-i] for i = 0,..., k - 1, since changing the ith bit [b.sub.i] incurs an [2.sup.i-1] change in the x-coordinate and an [2.sup.k-i] change in the y-coordinate. However, if we change several bits successively, then either the x-coordinate changes by more than [2.sup.i-1] or the y-coordinate changes by more than [2.sup.k-i], and so every box in [??] is empty. Note also that the boxes of the same size are pairwise disjoint.

We now define the "saturation" of each box B [member of] [??] with respect to a rectangulation of [P.sub.k]. Let B [member of] [??] and let r be a rectangulation of [P.sub.k]. The vertical extent of B is the orthogonal projection of B into the y-axis. Consider the vertical segments of r clipped in B (i.e., the segments s [??] B for all vertical segments s in r). The saturation of B with respect to r is the percentage of the vertical extent of B covered by projections of vertical segments of r clipped in B. See Figure 4 for examples. By definition, the

[FIGURE 4 OMITTED]

saturation of B is a real number in [0, 1]. For every B [member of] [??], we have that the saturation of B is 0 when r is a rectangulation with all horizontal segments, and it is 1 when r consists of all segments vertical. If we transform an all-horizontal rectangulation into an all-vertical one by a sequence of operations, the total saturation of all k[2.sup.k-1] boxes in [??] increases from 0 to k[2.sup.k-1]. The key observation is that a single operation increases the total saturation of all boxes in [??] by at most a constant.

It remains to bound the impact of a single operation on the saturation of a box in [??]. Consider first an operation ROTATE (r, c) that increases the saturation of some box B [member of] [??]. A rotate operation shortens a segment [s.sub.1] and extends an orthogonal segment [s.sub.2]. The saturation of a box B can increase only if a vertical segment grows, so we may assume that [s.sub.1] is horizontal and [s.sub.2] is vertical. Denote by s the newly inserted portion of [s.sub.2]. Note that s lies in a single face of the rectangulation r. Similarly, if an operation FLIP(r, p) increases the saturation of a box in B, then it replaces a horizontal segment by a vertical segment passing through p. The new vertical segment lies in two adjacent faces of r, separated by the original horizontal segment through p. We represent the new vertical segment as the union of two collinear vertical segments s [??] s' that meet at point p. In summary, an operation ROTATE(r, c) inserts one vertical segment s that lies in the interior of a face of r, and an operation FLIP(r, p) inserts two such segments. We show now that if such a new vertical segment s increases the saturation of some box in B [member of] [??], then s must lie in B.

Lemma 2 Suppose that an operation inserts a vertical segment s that lies in a face f of the rectangulation r. If the insertion of s increases the saturation of a box B [member of] [??], then s [subset] B.

Proof: Suppose, to the contrary, that s [??] B. Let p, q [member of] [P.sub.k] denote the two opposite corners of points that span B, such that p is the upper left or upper right corner of B, and q is the opposite corner of B. Since s increases the saturation of B, it must intersect B. Hence f [??] B [not equal to] [??]. Since s [??] B, at least one of the endpoints of s lies in the exterior of B. Assume, without loss of generality, that the upper endpoint of s lies outside B, and p is the upper left corner of B. Then, the top side of f is strictly above the top side of B. Since point p cannot be in the interior of f, the left side of the face f intersects the top side of B. Note that s and the left side of f have the same orthogonal projection on the y-axis. Therefore, the insertion of s cannot increase the saturation of B, contradicting our assumption. We conclude that both endpoints of s lie in B, and s [subset] B.

Lemma 3 A rotate (resp., flip) operation increases the total saturation of all boxes in [??] by at most 2 (resp., 4).

Proof: Suppose that an operation ROTATE(r, c) inserts a vertical segment s, or an operation FLIP(r, p) inserts two collinear vertical segments s [??] s' that meet at p. By Lemma 2, the insertion of s increases the saturation of a box B [member of] [??] of height h by |s|/h if h [greater than or equal to] |s|, and does not affect the saturation of boxes of height h < |s|. Recall that the boxes in [??] have only k different sizes, [2.sup.i-1] X [2.sup.k-i] for i = 1,..., k, and the boxes of the same size are pairwise disjoint. Let j [member of] {1, 2,..., k} be the largest index such that |s| [less than or equal to] [2.sup.k-j]. For i = 1,..., j, segment s increases the saturation of at most one box of height h = [2.sup.k-i], and the increase is at most |s|/h = |s| x [2.sup.i-k]. So s increases the total saturation of all boxes in [??] by at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], as required.

Theorem 2 For every n [member of] [??], there is an n-element point set P [subset] [[-1, n].sup.2] such that the diameter of G(P) is [ohm](n log n).

Proof: First assume that n = [2.sup.k] for some k [member of] [??]. We have defined a set [P.sub.k] of n = [2.sup.k] points and a set [??] of k[2.sup.k-1] = n log n/2 boxes spanned by [P.sub.k]. The total saturation of all boxes in [??] is 0 in the rectangulation with horizontal segments, and |[??]| = n log n/2 in the one with all segments vertical. By Lemma 3, a single flip or rotate operation increases the total saturation by at most 4. Therefore, at least n log n/8 operations are required to transform the horizontal rectangulation to the vertical one, and the diameter of G([P.sub.k]) is at least n log n/8.

If n is not a power of two, then put k = [??]lo[g.sub.2] n[??] and let P [subset] [[-1, n].sup.2] be the union of [P.sub.k] and n-[2.sup.k] arbitrary (noncorectilinear) points in [[[2.sup.k], n].sup.2]. All axis-parallel segments containing the points in P \ [P.sub.k] are in the exterior of [[-1, [2.sup.k]].sup.2]. Therefore k[2.sup.k-3] = [ohm](n log n) operations are required when all segments containing the points in [P.sub.k] [subset] P change from horizontal to vertical.

4 The Flip Diameter for Diagonal Point Sets

We say that a point set P is diagonal if all points in P lie on the graph of a strictly increasing function (e.g., f (x) = x). In this section we show that the flip diameter is O(n) for any n-element diagonal set. We denote by [begin strikethrough][p.sub.i][end strikethrough] the segment that contains [p.sub.i].

Theorem 3 For every n [member of] [??], the diameter of G(P) is at most 11n when P is a diagonal set of n points.

Proof of Theorem 3: Without loss of generality, we may assume that the diagonal set is P = {[p.sub.j] : i = 1,..., n}, where [p.sub.j] = (i, i). Given a rectangulation r for P, we construct a sequence of at most 5.5n flip and rotate operations that transforms r into a rectangulation with all segments vertical. Our algorithm consists of the following four phases.

Phase 1: No three consecutive segments are parallel. We describe an algorithm that, given a rectangulation r of P, applies less than 3n operations and returns a rectangulation in which no three consecutive points are contained in parallel segments.
```NoThreeParallel(r). While there are three consecutive points in P
contained in parallel segments, let [p.sub.i-1], [p.sub.j],[p.sub.i+1]
[member of] P be arbitrary points such that the segments
[begin strikethrough][p.sub.i-1][end strikethrough],
[begin strikethrough][p.sub.i][end strikethrough], and
[begin strikethrough][p.sub.i+1][end strikethrough] are parallel, and
call Shorten&Flip(r, [begin strikethrough][p.sub.i][end strikethrough]).
```

Note that Shorten&Flip(r, [begin strikethrough][p.sub.i][end strikethrough]) changes the orientation of the middle segment [begin strikethrough][p.sub.i][end strikethrough] only. Hence, after one invocation of Shorten&Flip(r, [begin strikethrough][p.sub.i][end strikethrough]), segments [begin strikethrough][p.sub.i-1][end strikethrough], [begin strikethrough][p.sub.i][end strikethrough], and [begin strikethrough][p.sub.i+1][end strikethrough] have alternating orientations, and will never be in the middle of a consecutive parallel triple. This implies that NoThreeParallel(r) terminates after changing the orientation of at most n/2 segments, and no three consecutive points are in parallel segments in the resulting rectangulation.

It remains to bound the number of flip and rotation operations: we have already seen that there are at most n/2 flip operations, and we shall charge each rotation operation to the segment extended by that operation. Note that after an invocation of Shorten&Flip(r, [begin strikethrough][p.sub.i][end strikethrough]), the two endpoints of [begin strikethrough][p.sub.i][end strikethrough] lie on [begin strikethrough][p.sub.i-1][end strikethrough] and [begin strikethrough][p.sub.i+1][end strikethrough], respectively, and so segment [begin strikethrough][p.sub.i][end strikethrough] is not extended after a flip in Phase 1. Thus, each segment can be extended in two possible directions (left/right or up/down). We claim that each segment is extended at most once in each direction. Suppose to the contrary that a segment [begin strikethrough][p.sub.k][end strikethrough] is extended twice in the same direction (refer to Figure 5, right). By symmetry, we may assume that [begin strikethrough][p.sub.k][end strikethrough] is vertical, and

[FIGURE 5 OMITTED]

it is extended upward in two rotate operations involving some horizontal segments [begin strikethrough][p.sub.i][end strikethrough] and [begin strikethrough][p.sub.j][end strikethrough] (each of which is sandwiched between two horizontal segments). In the first rotation, [begin strikethrough][p.sub.k][end strikethrough] is extended from its intersection with [begin strikethrough][p.sub.i][end strikethrough] to an intersection with [begin strikethrough][p.sub.j][end strikethrough]. Hence, the order of the corresponding three points is k < i < j. This step creates a rectangle bounded by [begin strikethrough][p.sub.i][end strikethrough] on the top, [begin strikethrough][p.sub.j][end strikethrough] on the bottom, and [begin strikethrough][p.sub.k][end strikethrough] on the left. The right boundary of this rectangle cannot be [begin strikethrough][p.sub.i+1][end strikethrough], since it is horizontal; and it cannot be any segment [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], otherwise the rectangle would contain [p.sub.i+1]. The contradiction confirms the claim. We conclude that this phase involves at most 2n rotations and at most n/2 flip operations.

Phase 2: Creating a staircase. We define a staircase in a rectangulation of P as a monotone increasing path along the segments that does not skip two or more consecutive points (refer to Figure 6). In the second

[FIGURE 6 OMITTED]

phase of our algorithm, we transform a rectangulation r with no three consecutive parallel segments into a rectangulation r that contains a staircase from the lower left to the upper right corner of R.

We construct a staircase [pi] incrementally, starting from the lower left corner. In each step we successively extend [pi] with one horizontal and one vertical segment to a point of P or to the upper right corner of R. Let [pi] be a current staircase from the lower left corner to a point a [member of] P. Denote by b and c the next two points of the diagonal set P. If there is a monotone path from a to b or from a to c, then append this path to [pi] to obtain a longer staircase. Suppose there is no such path. Then the segments [begin strikethrough]a[end strikethrough] and [begin strikethrough]b[end strikethrough] must be parallel, otherwise there would be a monotone path from a to b. The segment [begin strikethrough]e[end strikethrough] must be perpendicular to the segment [begin strikethrough]a[end strikethrough] since there are no three consecutive parallel segments.

We would like to perform a rotation at the intersection of segments [begin strikethrough]b[end strikethrough] and [begin strikethrough]e[end strikethrough], and then we can extend [pi] from a to c (along [begin strikethrough]a[end strikethrough] and [begin strikethrough]e[end strikethrough]). However, other operations may be necessary before we can rotate at [begin strikethrough]b[end strikethrough] [??] [begin strikethrough]e[end strikethrough]. Successively rotate all intersection points of [begin strikethrough]b[end strikethrough] with other segments that are to the right of b if [begin strikethrough]b[end strikethrough] is horizontal, and that are above b if [begin strikethrough]b[end strikethrough] is vertical (rotating at [begin strikethrough]b[end strikethrough] [??] [begin strikethrough]e[end strikethrough] eventually).

We claim that this phase requires at most n rotations. Let a, b, and c be defined as before, such that there is no path from a to either b or c. Assume, by symmetry, that a and b are horizontal and c is vertical. Let [d.sub.1],..., [d.sub.k] be segment endpoints on [begin strikethrough]b[end strikethrough] to the right of b. The bottom endpoints of the vertical segments through [d.sub.1] ... [d.sub.k] are now below b, and so these endpoints will never be involved in another rotation in our incremental procedure. Similarly, we perform a rotation at the left endpoint of each horizontal segment at most once. Therefore, the total number of rotations is bounded by the number of segments, which is n.

Phase 3: Extending all vertical segments of the staircase to full length. The third phase of our algorithm returns a rectangulation in which every vertical segment of the staircase extends to the top and bottom sides of the bounding box R. The staircase subdivides R into two regions, one above and one below (see Figure 7). We handle the two regions independently without modifying the staircase. To handle the region above, we sweep from top to bottom and successively shorten each horizontal segment we encounter until further shortening is impossible or would modify the staircase. If we encounter a horizontal segment s that is not part of the staircase, we use subroutine Shorten&Flip(r, s) to shorten it as much as possible and then flip it to vertical position. Similarly, we sweep the region below the staircase bottom-up.

Each flip or rotate operation in Phase 3 increases the number of segment endpoints lying on the top or bottom side of R. Therefore, the number of operations is bounded by the total number of segment endpoints, which is 2n.

[FIGURE 7 OMITTED]

Phase 4: Final steps. The vertical segments of the staircase extend to the top and bottom of the bounding box and partition it into vertical strips (Figure 7, right). Each strip contains a horizontal segment of the staircase, including a point in P. Because the staircase does not skip two or more consecutive points, there are at most three points in each strip. The total number of points in all strips combined is less than n.

If there is just one point in a strip, then we flip the horizontal segment that contains it. If there are two points in a strip, then one lies on a horizontal and one on a vertical segment. In this case, perform a rotation so the vertical segment reaches maximum length, and then flip the horizontal segment. If there are three points in a strip, then the middle point lies on a horizontal segment and the other two lie on vertical segments above and below the staircase, respectively. In this case, we perform two rotations so that both vertical segments reach full length, and then flip the horizontal segment. Similarly to Phase 3, each operation in this phase increases the number of segment endpoints lying on the top or bottom side of R. Therefore, 2n is an upper bound on the number of operations in Phases 3 and 4 combined.

Remark. Felsner et al.  showed that the rectangulations of a diagonal point set are in bijection with twin pairs of binary trees. Visually, the part of the boundaries of the rectangles lying above (resp., below) the points in P form a binary tree whose vertices are the points in P and the top-right (resp., bottom-left) corners of R. This observation allows determining the number of rectangulations for diagonal point sets in terms of Baxter permutations (cf. ). Theorem 3 implies the following.

Corollary 1 For any two pairs of twin binary trees with n leaves, there is a sequence of twin binary trees ([t.sub.1],[t'.sub.1]),..., ([t.sub.k], [t'.sub.k]) of size k = O(n) that starts with the first pair, ends with the second pair, and for every i (1 [less than or equal to] i < k), either [t.sub.i] = [t.sub.i+1] or [t.sub.i+1] is obtained from [t.sub.i] by a single tree-rotate operation (the same for [t'.sub.j] and [t'.sub.i+1]).

5 Generalization to Convex Subdivisions

Given a set P of n points in the plane, a convex subdivision for P is a subdivision of the plane into convexcells by n pairwise noncrossing line segments (possibly lines or half-lines), such that each segment contains exactly one point of P and no three segments have a point in common.

The flip and rotate operations can be interpreted for convex subdivisions of a point set P, as well (see Figure 8). The definition of the operation ROTATE(r, c) is identical to the rectilinear version. The operation FLIP(r, p) requires more attention, since a segment may have infinitely many possible orientations.

[FIGURE 8 OMITTED]

Definition 3 (Flip) Let r be a convex subdivision of P, let p [member of] P be a point such that the segment s containing p does not contain any endpoints of other segments, and let [sigma] [member of] [??] be a unit vector. The operation FLIP(r, p, [sigma]) replaces s by a segment of direction a containing p.

Similarly to the graph of rectangulations G(P), we define the graph of convex subdivisions of P, G(P) = (V, E), where the vertex set is V = {r : r is a convex subdivision of P} and the edge set is E = {([r.sub.1], [r.sub.2]) : a single flip or rotate operation on [r.sub.1] produces [r.sub.2]}. Our main result in this section is that even though G(P) is an infinite graph, its diameter is O(n log n), where n = |V|.

Theorem 4 For set P of n points, the graph G(P) is connected and its diameter is O(n log n).

We show that any convex subdivision can be transformed into a subdivision with all segments vertical through a sequence of O(n log n) operations. Subroutine Shorten&Flip(r, s) from Section 2 can be adapted almost verbatim: for a unit vector [sigma] [member of] [??], subroutine Shorten&Flip(r, s, [sigma]) shortens segment s maximally by rotate operations, and then flips it to direction [sigma].

Lemma 4 Let r be a convex subdivision of a set of n points in the plane with distinct x-coordinates. There is a sequence of O(n) flip and rotate operations that turns at least a 1/36 fraction of the nonvertical segments vertical, and keeps all vertical segments vertical.

Before proving Lemma 4, we need to introduce a few technical terms. Consider a convex subdivision r of a set of n points with distinct x-coordinates. We say that a segment [s.sub.1] hits another segment [s.sub.2] if an endpoint of [s.sub.1] lies in the relative interior of [s.sub.2]. An extension of [s.sub.1] beyond [s.sub.2] hits [s.sub.3] if [s.sub.1] hits [s.sub.2] and [s.sub.1] is contained in a segment [s'.sub.1], such that [s'.sub.1] hits [s.sub.3] and [s'.sub.1] crosses at most one segment (namely, [s.sub.2]). Note that the operation ROTATE (r, [s.sub.1] [??] [s.sub.2]), if applicable, would extend [s.sub.1] beyond [s.sub.2] to hit segment [s.sub.3]. We define the extension visibility digraph H(r) on all segments in r, where the vertices correspond to the segments in r, and we have a directed edge ([s.sub.2], [s.sub.3]) if [s.sub.2] hits [s.sub.3] or there is a segment [s.sub.1] such that an extension of [s.sub.1] beyond [s.sub.2] hits [s.sub.3].

The graph H(r) is not necessarily planar: it is not difficult to construct a convex subdivision r for a set of O([t.sup.2]) points where H(r) contains a subgraph isomorphic to the complete graph [K.sub.t] (Figure 9). It is enough to describe the segments of such a construction (the points may lie anywhere in the interior of the segments). Start with the sides of a convex t-gon, and extend the sides in counterclockwise direction to obtain a convex subdivision. The extension visibility digraph of these t segments contains a cycle ([s.sub.1],..., [s.sub.t]). Add short segments in the exterior of the initial t-gon: If a segment hits [s.sub.i] and its supporting line passes though [s.sub.j], it generates an edge ([s.sub.i], [s.sub.j]) in the extension visibility digraph.

[FIGURE 9 OMITTED]

Note that the number of edges in H(r) is at most 4n, since each segment hits at most two other segments, but some segments extend to infinity; and the extension of each segment beyond each of its endpoints hits at most one other segment. If P contains n points, the average degree in H(r) is less than 8. Therefore, H(r) has an independent set of size at least n/9 (obtained by successively choosing minimum-degree vertices [23, 39]).

Proof of Lemma 4.: Let r be a convex subdivision of a set of n points with distinct x-coordinates. Let [I.sub.0] be an independent set in the extension visibility graph H(r) induced by all nonvertical segments. As noted above, [I.sub.0] contains at least 1/9 of the nonvertical segments in r. Let [I.sub.1] [??] [I.sub.0] be an independent set in the bar visibility graph of the segments in [I.sub.0] (two nonvertical segments in [I.sub.0] are mutually visible if there is a vertical segment between them that does not cross any segment of the subdivision). Since the bar visibility graph is planar, we have |[I.sub.1]| [greater than or equal to] |[I.sub.0]|/4, and so [I.sub.1] contains at least a 1/36 fraction of the nonvertical segments in r. The total number of segment endpoints that lie in the relative interior of segments in [I.sub.1] is O(n). An invocation of subroutine Shorten&Flip(r, s, (0, 1)) for each segment s [member of] [I.sub.1] changes their orientation to vertical.

The operations maintain the invariants that (1) the segments in [I.sub.1] are pairwise disjoint; and (2) the nonvertical segments in [I.sub.1] form an independent set in both H and the bar visibility graph of all segments in [I.sub.0]. It follows that each operation either decreases the number of nonvertical segments in [I.sub.1] (flip), or decreases the number of segment endpoints that lie in the relative interior of a nonvertical segment in [I.sub.1] (rotate). After performing O(n) operations, all segments in [I.sub.1] become vertical. Since only the segments in [I.sub.1] change orientation (each of them is flipped to become vertical), all vertical segments in r remain vertical, as required.

Proof of Theorem 4.: Let P be a set of n points in a bounding box. We may assume, by rotating the point set if necessary, that the points in P have distinct x-coordinates. Denote by [r.sub.0] the convex subdivision given by n vertical line segments, one passing through each point in P.

Consider a convex subdivision [r.sub.1] of P. By Lemma 4, O(n) operations can decrease the number of nonhorizontal segments by a factor of at least 36/35. After at most log n/ log(36/35) invocations of Lemma 4, the number of nonvertical segments drops below 1, that is, all segments become vertical and we obtain [r.sub.0], as claimed.

A linear upper bound for collinear points

We show that the bound O(n log n) on the diameter of the flip graph G(P) from Theorem 4 can be improved to O(n) for some simple point configurations.

Theorem 5 For every n [member of] [??], the diameter of G(P) is O(n) when P is a set of n collinear points.

Proof: We may assume that P = {[p.sub.i] : i = 1,..., n}, [p.sub.i] = (i, 0). Let r be a convex subdivision of P. No segment in r is horizontal, since each segment contains a unique point. We show that there is a sequence of O(n) operations that transforms r into a convex subdivision with all segments vertical. Suppose that not all segments in r are vertical, and let m > 0 be the minimum absolute value of the slope of a nonvertical segment. Our algorithm proceeds in two phases.

Phase 1: Building a staircase. In this phase, we transform r into a convex subdivision in which every [begin strikethrough][p.sub.i][end strikethrough] is a nonvertical ray with a left endpoint at infinity, and has slope m/n when i is odd and -m/n when i is even. We process the points [p.sub.1],..., [p.sub.n] successively in this order. We maintain the following invariant (refer to Figure 10): When we start processing [p.sub.i], segments [begin strikethrough][p.sub.1][end strikethrough],..., [begin strikethrough][p.sub.i-1][end strikethrough] are already rays with

[FIGURE 10 OMITTED]

the desired properties, and they do not contain the endpoints of any segment [begin strikethrough][p.sub.i][end strikethrough],..., [begin strikethrough][p.sub.n][end strikethrough] in their relative interiors.

Suppose that points [p.sub.j], for all 1 [less than or equal to] j < i, have already been processed. We use the subroutine Shorten&Flip(r, [begin strikethrough][p.sub.i][end strikethrough], [sigma]) to shorten [begin strikethrough][p.sub.i][end strikethrough] and flip it into the desired orientation (of slope m/n or -m/n depending on the parity of i). For i = 1, this already guarantees that segment [begin strikethrough][p.sub.1][end strikethrough] is a ray with a left endpoint at infinity. If i > 1, however, the left endpoint of [begin strikethrough][p.sub.i][end strikethrough] lies on the ray [begin strikethrough][p.sub.i-1][end strikethrough], whose slope is different from that of [begin strikethrough][p.sub.i][end strikethrough]. Due to the invariant, [begin strikethrough][p.sub.i-1][end strikethrough] contains no segment endpoints to the right of the intersection point [begin strikethrough][p.sub.i-1][end strikethrough] [??] [begin strikethrough][p.sub.i][end strikethrough]. We can now apply a rotation at [begin strikethrough][p.sub.i-1][end strikethrough] [??] [begin strikethrough][p.sub.i][end strikethrough]. Since the slopes of all segments are at least m/n in absolute value, [begin strikethrough][p.sub.i][end strikethrough] extends to infinity, and our invariant is established for segments [begin strikethrough][p.sub.1][end strikethrough],..., [begin strikethrough][p.sub.i][end strikethrough].

We argue that Phase 1 uses O(n) operations. For each point [p.sub.i], we invoke Shorten&Flip(r, [begin strikethrough][p.sub.i][end strikethrough], [sigma]), which performs only one flip operation, followed by at most one rotation. It is enough to bound the number of rotations performed in the invocations of subroutines Shorten&Flip. We claim that these invocations extend each segment at most once in each direction. Suppose, to the contrary, that a segment [begin strikethrough][p.sub.k][end strikethrough] is extended in the same direction twice (when processing points [begin strikethrough][p.sub.i][end strikethrough] and [begin strikethrough][p.sub.j][end strikethrough]). Since the points are processed from left to right, we have i < j < k. Consider the step in which a rotation extends [begin strikethrough][p.sub.k][end strikethrough] from its intersection with [begin strikethrough][p.sub.i][end strikethrough] to an intersection with [begin strikethrough][p.sub.j][end strikethrough]. Then, the x-axis and segment [begin strikethrough][p.sub.k][end strikethrough] intersect [begin strikethrough][p.sub.i][end strikethrough] and [begin strikethrough][p.sub.j][end strikethrough] in different orders. Hence, [begin strikethrough][p.sub.i][end strikethrough] and [begin strikethrough][p.sub.j][end strikethrough] must cross each other, contradicting the fact that they are part of a convex subdivision. This proves our claim. It follows that Phase 1 uses at most 5n operations.

Phase 2: Orienting all lines to be vertical. Refer to Figure 11. We are given a convex subdivision in

[FIGURE 11 OMITTED]

which every [begin strikethrough][p.sub.i][end strikethrough] is a ray with a left endpoint at infinity, and has slope m/n when i is odd and -m/n when i is even. Note that only consecutive segments intersect. (This is still not a "canonical" subdivision, as m depends on the initial convex subdivision.) In Phase 2, we transform all segments into vertical lines. We make five passes over the odd or even points: (1) For every odd point [begin strikethrough][p.sub.i][end strikethrough] from right to left, rotate ray [begin strikethrough][p.sub.i][end strikethrough] into a line of slope m/n. As a result, the lines through the odd points separate the even points. (2) We can now flip the segments through the even points independently into vertical segments. (3) For every even point [begin strikethrough][p.sub.i][end strikethrough] from left to right, rotate the top endpoints to infinity. (4) For every even point from right to left, rotate the bottom endpoint to infinity. We obtain vertical lines through the even points, that separate the odd points. (5) Finally, flip the segments through the odd points independently into vertical lines. We made three passes over even segments and two passes over odd segments, so the total number of operations in Phase 2 is 2n + <n/2> [less than or equal to] 3n. The two phases combined use at most 8n operations.

6 Conclusions

We have shown that the diameter of the flip graph G(P) is between [ohm](n) and O(n log n) for every n-element point set P, and these bounds cannot be improved. The diameter is [THETA](n) for diagonal point sets, and [THETA](n log n) for the bit-reversal point set. The flip graph G(P) of a noncorectilinear set P is uniquely determined by the permutation of the x- and y-coordinates of the points  (e.g., diagonal point sets correspond to the identity permutation). It is an open problem to find the average diameter of G(P) over all n-element permutations. It would already be of interest to find broader families of point sets with linear diameter: Is the diameter of G( P) linear if P is in convex position, unimodal, or corresponds to a separable permutation (see )?

We have shown that the diameter of the flip graph is also O(n log n) for the convex subdivisions of n points in the plane. We do not know whether this bound is tight. It is possible that the flip diameter is [ohm](n log n) for the bit-reversal point set defined in Section 3, but our proof of Theorem 2 heavily relies on axis-aligned boxes and does not seem to extend to convex subdivisions.

Given a convex subdivision r of a point set P, the flip and rotate operations can be thought of as a continuous deformation; refer to Figure 12: FLIP(r, p, [sigma]) rotates the segment containing p continuously to position [sigma]; and ROTATE(r, c) rotates continuously a portion of the segment containing c into the extension of the segment that currently ends at c. The weight of an operation can be defined as the number of vertices swept during this continuous deformation. By Theorem 4, a sequence of O(n log n) operations can transform any convex subdivision to any other convex subdivision on n points. A single operation, however, may have [ohm](n) weight. We conjecture that the weighted diameter of the graph G(P) is also O(n log n) for every n-elements point set P.

[FIGURE 12 OMITTED]

Acknowledgments. Research on this paper was initiated at the Workshop on Counting and Enumerating of Plane Graphs held in March 2013 at Schloss Dagstuhl. We thank Sonia Chauhan, Michael Hoffmann, and Andre Schulz for insightful comments and stimulating conversations about the problems discussed in this paper.

References

 E. Ackerman, Counting Problems for Geometric Structures: Rectangulations, Floorplans, and Quasi-Planar Graphs, Ph.D. Thesis, Dept. of Computer Science, Technion--Israel Inst. of Technology, Haifa, Israel, 2006.

 E. Ackerman, G. Barequet, and R.Y. Pinter, On the number of rectangulations of a planar point set, J. Combinatorial Theory, Series A, 113:6 (2006), 1072-1091.

 A. Asinowski, G. Barequet, M. Bousquet-Melou, T. Mansour, and R.Y. Pinter, Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations, Electronic J. Combinatorics, 20 (2), 35 pp., 2013.

 P. Bose, J. Buss, and A. Lubiw, Pattern matching for permutations, Information Processing Letters, 65 (1998), 277-283.

 K. Buchin, D. Eppstein, M. Loffler, M. Nollenburg, and R.I. Silveira, Adjacency-preserving spatial treemaps, Proc. 12th Workshop on Algorithms and Data Structures (WADS), vol. 6844 of Lecture Notes in Computer Science, 2011 Springer, pp. 159-170.

 A.L. Buchsbaum, E.R. Gansner, C.M. Procopiuc, and S. Venkatasubramanian, Rectangular layouts and contact graphs, ACM Trans. on Algorithms, 4 (2008), #8, 28 pp.

 F.C. Calheiros, A. Lucena, and C.C. de Souza, Optimal rectangular partitions, Networks, 41 (2003), 51-67.

 M. Cardei, X. Cheng, X. Cheng, and D.Z. Du, A tale on guillotine cut, in: Novel Approaches to Hard Discrete Optimization (P.M. Pardalos and H. Wolkowicz, eds.), vol. 37 of Field Institute Communications, 2003, AMS, pp. 41-54.

 B. Chazelle, The Discrepancy Method, Cambridge University Press, 2000.

 N. Chiba, T. Nishizeki, and N. Saito, A linear 5-coloring algorithm of planar graphs, J. Algorithms 2 (1981), 317-327.

 H. de Fraysseix, P.O. de Mendez, and J. Pach, A left-first search algorithm for planar graphs, Discrete & Computational Geometry, 13 (1995), 459-468.

 P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel, Representing a planar graph by vertical lines joining different levels, Discrete Mathematics, 46 (1983), 319-321.

 D.Z. Du, L.Q. Pan, and M.T. Shing, Minimum edge length guillotine rectangular partition, Technical Report MSRI 02418-86, University of California, Berkeley, CA, 1986.

 D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek, Area-universal and constrained rectangular layouts, SIAM J. Computing, 41 (2012), 537-564.

 S. Felsner, Rectangle and square representations of planar graphs, in: Thirty Essays in Geometric Graph Theory (J. Pach, ed.), 2013, Springer, New York, pp. 213-248.

 S. Felsner, Exploiting air-pressure to map floorplans on point sets, J. Graph Algorithms and Applications, 18 (2014), 233-252.

 S. Felsner, E. Fusy, M. Noy, and D. Orden, Bijections for Baxter families and related objects, J. Combinatorial Theory, Series A, 118 (2011), 993-1020.

 Greg N. Frederickson, On linear-time algorithms for five-coloring planar graphs, Inf. Proc. Lett.,19 (1984), 219-224.

 T.F. Gonzalez and S.-Q. Zheng, Bounds for partitioning rectilinear polygons, Proc. 1st Sympos. on Computational Geometry, 1985, ACM Press, pp. 281-287.

 T.F. Gonzalez and S.-Q. Zheng, Improved bounds for rectangular and guillotine partitions, J. Symbolic Computation, 7 (1989), 591-610.

 T F. Gonzalez and S.-Q. Zheng, Approximation algorithms for partitioning a rectangle with interior points, Algorithmica, 5 (1990), 11-42.

 M. Hasan, M. Rahman, and M. Karim, Box-rectangular drawings of planar graphs, J. Graph Algorithms and Applications, 17 (2013), 629-646.

 D.S. Hochbaum, Efficient bounds for the stable set, vertex cover, and set packing problems, Discrete Applied Mathematics, 6 (1983), 243-254.

 F. Hurtado, M. Noy, and J. Urrutia, Flipping edges in triangulations, Discrete & Computational Geometry, 22 (1999), 333-346.

 K. Koziminski and E. Kinnen, Rectangular duals of planar graphs, Networks, 15 (1985), 145-157.

 M. van Kreveld and B. Speckmann, On rectangular cartograms, Computational Geometry: Theory and Applications, 37 (2007), 175-187.

 C. Lawson, Software for [c.sub.1] surface interpolation, in: Mathematical Software III (J. Rice, ed.), 1977, Academic Press, New York, pp. 161-194.

 C. Levcopoulos, Fast heuristics for minimum length rectangular partitions of polygons, Proc. 2nd Sympos. on Computational Geometry, 1986, ACM Press, pp. 100-108.

 C.C. Liao, H.I. Lu, and H.C. Yen, Compact floor-planning via orderly spanning trees, J. Algorithms, 48 (2003), 441-451.

 A. Lingas, R.Y. Pinter, R.L. Rivest, and A. Shamir, Minimum edge length rectilinear decompositions of rectilinear figures, Proc. 20th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, 1982, pp. 53-63.

 H. Meijer and D. Rappaport, Simultaneous edge flips for convex subdivisions, Proc. 16th Canadian Conference on Computational Geometry, Montreal, Quebec, Canada, 2004, pp. 57-59.

 M. Rahman, T. Nishizeki, and S. Ghosh, Rectangular drawings of planar graphs, J. Algorithms, 50 (2004), 62-78.

 E. Raisz, The rectangular statistical cartogram, Geographical Review, 24 (1934), 292-296.

 N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, The four-colour theorem, J. Combinatorial Theory, Series B, 70 (1997), 2-44.

 F. Santos and R. Seidel, A better upper bound on the number of triangulations of a planar point set, J. Combinatorial Theory, Series A, 102 (2003), 186-193.

 M. Sharir and E. Welzl, Random triangulations of planar point sets, Proc. 22nd Sympos. on Computational Geometry, 2006, ACM Press, pp. 273-281.

 D. Sleator, R. Tarjan, And W. Thurston, Rotations distance, triangulations and hyperbolic geometry, J. AMS, 1 (1988), 647-682.

 R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Dicrete & Computational Geometry, 1 (1986), 321-341.

 P. Turan, On an extremal problem in graph theory (in Hungarian), Math. Fiz. Lapok, 48 (1941), 436-452.

 P. Ungar, On diagrams representing graphs, J. London Math. Soc., 28 (1953), 336-342.

 M. H. Williams, A linear algorithm for colouring planar graphs with five colours, Computer Journal, 28 (1985), 78-81.

 S.K. Wismath, Characterizing bar line-of-sight graphs, in Proc. 1st Sympos. on Computational Geometry, 1985, ACM Press, pp. 147-152.

 B. Yao, H. Chen, C.K. Cheng, and R. Graham, Floorplan representations: Complexity and connections, ACM Trans. on Design Automation of Electronic Systems, 8 (2003), 55-80.

Eyal Ackerman (1)

Michelle M. Allen (2)

Gill Barequet (3)

Maarten Loffler (4)

Joshua Mermelstein (2)

Diane L. Souvaine (2)

Csaba D. Toth (2,5)

(1) Department of Mathematics, Physics, and Computer Science, University of Haifa at Oranim, Tivon, Israel

(2) Department of Computer Science, Tufts University, Medford, MA, USA

(3) Department of Computer Science, Technion--Israel Inst. of Technology, Haifa 32000, Israel

(4) Department of Computing and Information Sciences, Utrecht University, The Netherlands

(5) Department of Mathematics, California State University Northridge, Los Angeles, CA, USA

received 19th May 2015, revised 30th Jan. 2016, accepted 7th Mar. 2016.

(*) A preliminary version of this work appeared in the Proceedings of the 11th Latin American Theoretical INformatics Symposium (LATIN 2014), LNCS 8392, Springer, 2014, pp. 478-489. Research on this paper was partially supported by the NSF grant CCF-0830734 and Netherlands Organization for Scientific Research (NWO) under grant 639.021.123.