text:
# Flipturning PolygonsPortions of this work were done at the Workshop on Polygonal Entanglement Theory held February 4–11, 2000 at McGill University’s Bellairs Research Center, Holetown, Barbados. For the most recent version of this paper, see http://www.uiuc.edu/~jeffe/pubs/flipturn.html.

## 1 Introduction

A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such as circular DNA . Most of the research in this area involves computer-intensive Monte-Carlo simulations. To simplify these simulations they are usually restricted to the integer lattices $`\mathrm{𝖹𝖹}^2`$ and $`\mathrm{𝖹𝖹}^3`$, although some work has also been done on the FCC lattice . Like the related algorithmic robotics research on linkages, the problems of interest to physicists and biologists involve closed simple polygons , open simple polygonal chains  and simple polygonal trees , *i.e.*, polygons, chains, and trees that do not intersect themselves; hence the term *self-avoiding walks* for the case of polygons and chains. Generating a random self-avoiding walk from scratch is difficult, especially if it must return to its starting point as in the case of polygons. The waiting time is too long due to attrition; if a random walk crosses itself at any point other than its starting point, it must be discarded and a new walk started. Therefore an efficient method frequently used to generate random chains or polygons is to modify one such object into another using a simple operation called a *pivot*. Unlike the work in linkages, however, here we do not care if intersections happen *during* the pivot as long as when the pivot is complete we end up with a simple polygon or chain. In other words, pivots are seen as instantaneous combinatorial changes, not continuous processes. In general the pivots used are selected from a large variety of transformations such as reflections, rotations, or ‘cut and paste’ operations on certain subchains. We refer the reader to a multitude of such problems and results in . For example, Madras and Sokal  have shown that for all $`d2`$, every simple lattice polygonal chain with $`n`$ edges in $`\mathrm{𝖹𝖹}^d`$ can be straightened by some sequence of at most $`2n1`$ suitable pivots while maintaining simplicity after each pivot. The pivots used here are either reflections through coordinate hyperplanes or rotations by right angles.

In order to prove the ergodicity of their self-avoiding walks, polymer physicists are interested in convexifying polygons (and straightening open polygonal chains). If a polygon can be transformed to some canonical convex configuration, then any simple polygon can be reconfigured to any other via this intermediate position. This theoretical aspect of polymer physics research resembles the algorithmic robotics work on convexification of polygonal linkages. We refer the reader to survey papers of O’Rourke  and Toussaint  for further references in the latter area.

In this paper, we are concerned with one type of pivot of central concern in polymer physics research. This pivot is usually called an *inversion* in the physics literature, but since it seems to have been first proposed in an unpublished 1973 paper of Joss and Shannon , we will follow their terminology and call it a *flipturn*. Flipturns are defined as follows. Any nonconvex polygon has at least one concavity, or *pocket*. Formally, a pocket of a nonconvex polygon $`P`$ is a maximal connected sequence of polygon edges disjoint from the convex hull of $`P`$ except at its endpoints. The line segment joining the endpoints of a pocket is called the *lid* of the pocket. A flipturn rotates a pocket 180 degrees about the midpoint of its lid, or equivalently, reverses the order of the edges of a pocket without changing their lengths or orientations. Figure 1.1 shows the effect of a single flipturn on a nonconvex orthogonal polygon, and Figure 1.2 shows a sequence of flipturns transforming this polygon into a rectangle. We will illustrate such sequences by overlaying the resulting polygons and labeling the area added by each flipturn by its position in the sequence. (The circled numbers will be explained in Section 2.)

### 1.1 Previous and Related Results

Joss and Shannon proved that any simple polygon with $`n`$ sides can be convexified by a sequence of at most $`(n1)!`$ flipturns, by observing that each flipturn produces a new cyclic permutation of the edges. Since each flipturn increases the polygon’s area, each of the $`(n1)!`$ cyclic permutations can occur at most once. We can immediately improve this bound to $`(n1)!/2`$ by observing that at most half of the $`(n1)!`$ cyclic permutations describe a simple polygon with the proper orientation. Although this is the best bound known, it is extremely loose; Joss and Shannon conjectured that $`n^2/4`$ flipturns are always sufficient. Grünbaum and Zaks  showed that even crossing polygons could be convexified with a finite number of flipturns. Biedl  discovered a family of polygons that are convexified only after $`(n2)^2/4`$ badly chosen flipturns, nearly matching Joss and Shannon’s conjectured upper bound. Ahn *et al.*  recently proved that any simple polygon can be convexified by a sequence of at most $`n(n3)/2`$ so-called *modified* flipturns (which we define in Section 2). Better results are known for orthogonal and lattice polygons in the plane. Dubins *et al.*  showed that any simple lattice polygon in the plane can be convexified with $`n4`$ well-chosen flipturns . Until very recently this was the best upper bound known. Ahn *et al.*  show that any polygon with $`s`$ distinct edge slopes can be convexified by $`n(s1)/2s`$ modified flipturns111Ahn *et al.*  omit the ceiling, so their stated bound is off by one when $`n`$ is odd and $`s`$ is even.; in particular, $`n/22`$ modified flipturns suffice to convexify any orthogonal polygon.

There are significant differences between flipturns and another very common pivoting rule, the *Erdős-Nagy flip* , in which a pocket is *reflected* across its lid. As with flipturns, any convex polygon can be convexified using a finite number of flips. Unlike flipturns, however, the number of flips required is not bounded by any function of $`n`$; in particular, Joss and Shannon constructed a family of quadrilaterals that require an unbounded number of flips to convexify . Another important difference is that flipturns preserve the *orientation* of polygon edges, while flips preserve their *order* around the polygon. This implies that starting from the same simple polygon, different sequences of flips can lead to different convex polygons—see Figure 1.3(a) for an example—but different flipturn sequences always lead to the same convex shape. For further results on both flips and flipturns for general polygons, simpler algorithms, and a more complete history of the problem, see .

### 1.2 New Results

Our results depend critically on the behavior of flipturns in degenerate cases. In Section 2, we offer three alternate definitions: *standard*, *extended*, and *modified* flipturns. As our naming suggests, we believe that standard flipturns are closest to the original definition of Joss and Shannon; modified flipturns were introduced by Ahn *et al.* .

In Section 3, we develop a number of new results concerning convexifying flipturn sequences for orthogonal polygons. We show that $`5(n4)/6`$ well-chosen (standard) flipturns are sufficient, and $`3(n4)/4`$ flipturns are sometimes necessary, to convexify any orthogonal polygon. We also show that any orthogonal polygon is convexified after at most $`n5`$ *arbitrary* flipturns, and that some polygons can survive $`5(n4)/6`$ flipturns. Finally, we show that the shortest and longest flipturn sequences for the same orthogonal polygon can differ in length by at least $`(n4)/4`$. Similar results are derived for extended flipturns. All of these bounds improve the previously best known results. Using techniques developed in Section 3, we prove in Section 4 that any polygon can be convexified after at most $`n^24n+2`$ standard or extended flipturns, generalizing the modified flipturn results of Ahn *et al.* . Our new upper and lower bounds are summarized in the first two rows of Tables 1.2 and 1.2; the last row of each table gives the corresponding results of Ahn *et al.*for modified flipturns.

Section 5 describes how to maintain both a simple polygon and its convex hull in $`O(\mathrm{log}^4n)`$ time per flipturn, using a data structure of size $`O(n)`$. Our data structure is a variant of the dynamic convex hull structure of Overmars and van Leeuwen . Together with the results of the previous sections, this implies that we can compute a convexifying sequence of flipturns for any polygon in $`O(n^2\mathrm{log}^4n)`$ time, or for any orthogonal polygon in $`O(n\mathrm{log}^4n)`$ time.

In Section 6, we prove that for any simple polygon, every sequence of flipturns eventually leads to the same convex polygon, and we can compute this convex polygon in $`O(n\mathrm{log}n)`$ time. As we already mentioned, the fact that the *shape* of the final convex polygon is independent of the flipturn sequence is rather obvious, but the independence of the final polygon’s *position* requires considerably more effort.

Finally, in Section 7, we show that finding the longest flipturn sequence for a given simple polygon is NP-hard.

## 2 The Importance of Being Degenerate

The behavior of flipturn sequences depends critically on how flipturns are defined in degenerate cases. In the general case, a lid is an edge of the polygon’s convex hull. However, in degenerate cases where three or more vertices are colinear, a lid can be a proper subset of a convex hull edge according to Joss and Shannon’s original definition . Although there are several different types of degeneracies, only one type will actually affect our results. We call a pocket or flipturn *degenerate* whenever the two edges just outside the pocket lie on the same line. In our illustrations of flipturn sequences such as Figure 1.2, circled numbers indicate degenerate flipturns.

Since flipturning about a proper subset of a convex hull edge may seem unnatural, we offer the following alternative definition. An *extended* pocket of a polygon is a chain of at least two edges joining an adjacent pair of convex hull vertices. An extended flipturn rotates an extended pocket $`180`$ degrees about the midpoint of its lid, which is a complete convex hull edge. An extended pocket or flipturn is *degenerate* if and only if the two edges just *inside* the pocket lie on the same line.

Another alternative is proposed by Ahn *et al.* , who define *modified* pockets as follows. Consider a standard pocket with vertices $`v_i,v_{i+1},\mathrm{},v_j`$ (where index arithmetic is modular). If the nearby vertex $`v_{j+1}`$ lies on the line through $`v_i`$ and $`v_j`$, then the chain of edges from $`v_i`$ to $`v_{j+1}`$ is a modified pocket; otherwise, the standard pocket from $`v_i`$ to $`v_j`$ is a modified pocket. If the standard pocket is degenerate, the modified pocket contains one of the two colinear boundary edges.

Figure 2.1 illustrates a standard flipturn, an extended flipturn, and one of two possible modified flipturn of the ‘same’ degenerate pocket of a polygon. Note that a single extended flipturn can simultaneously invert several standard or modified pockets.

In Section 3, we will focus entirely on *orthogonal* polygons, each of whose edges is either horizontal or vertical. We say that a pocket or flipturn is *orthogonal* if its lid is horizontal or vertical and *diagonal* otherwise. In this context, a pocket is degenerate if and only if it is orthogonal, and so standard, extended, and modified orthogonal flipturns have different behaviors, as Figure 2.1 shows. By any of our three definitions, a diagonal flipturn reduces the number of vertices of the polygon by two; specifically, the endpoints of the flipturned pocket lie in the interior of edges of the new polygon. If the input polygon is in general position, *every* flipturn will be nondegenerate, and therefore diagonal.222We emphasize that ‘general position’ does not mean simply that no three vertices are colinear. In our context, an orthogonal polygon is in general position if an arbitrary infinitesimal perturbation of its edge lengths does not change the set of possible flipturn sequences. These observations immediately imply the following theorem.

###### Theorem 2.1

Exactly $`(n4)/2`$ flipturns are necessary and sufficient to convexify any orthogonal $`n`$-gon in general position, and these flipturns can be chosen arbitrarily.

Thus, any discussion of flipturn sequences on orthogonal polygons only becomes interesting if orthogonal flipturns are possible. Even for degenerate polygons, the fact that every diagonal flipturn removes two vertices immediately implies the following upper and lower bounds.

###### Theorem 2.2

Any orthogonal $`n`$-gon is convexified by any sequence of $`(n4)/2`$ diagonal flipturns.

###### Theorem 2.3

At least $`(n4)/2`$ flipturns are required to convexify any orthogonal $`n`$-gon.

*Every* modified flipturn on an orthogonal polygon removes two vertices. The somewhat convoluted definition of modified pockets seems to have been developed precisely to avoid the ‘interesting’ consequences of degeneracies. We immediately obtain the following result, most of which is a special case of a theorem of Ahn *et al.* .

###### Theorem 2.4

Exactly $`(n4)/2`$ modified flipturns are necessary and sufficient to convexify any orthogonal $`n`$-gon, and these flipturns can be chosen arbitrarily.

## 3 Flipturn Sequences for Orthogonal Polygons

In this section, we derive bounds on the maximum length of either the shortest or longest convexifying flipturn sequences for orthogonal polygons. The bounds for the shortest sequence tell us how quickly we can convexify a polygon if we choose flipturns intelligently; the longest sequence bounds tell us how many flipturns we can perform even if we choose flipturns blindly. Our results are summarized in the first two rows of Table 1.2. Since Theorem 2.4 completely characterizes the lengths of modified flipturn sequences for orthogonal polygons, this section will focus entirely on standard and extended flipturns.

### 3.1 Order Matters

Once we recognize the possibility of orthogonal flipturns, it is easy to construct polygons such as in Figure 3.1 that have flipturn sequences of different lengths. The polygon has two pockets; flipturning one of them first creates an orthogonal pocket, and flipturning the other first does not.

In fact, as the following theorem shows, the shortest and longest flipturn sequences may differ significantly in length.

###### Theorem 3.1

For infinitely many $`n`$, there is an orthogonal $`n`$-gon whose shortest and longest standard or extended flipturn sequences differ in length by at least $`(n4)/4`$.

* Figure 3.2 illustrates the recursive construction of such a polygon, for all $`n`$ of the form $`16k+4`$. The shortest flipturn sequence for the polygon includes only diagonal flipturns and therefore has length $`(n4)/2`$. Another sequence, which we believe to be the longest, requires twelve flipturns to remove every $`16`$ vertices. Figure 3.2 illustrates this long sequence of standard flipturns; the corresponding extended flipturn sequence is essentially equivalent. $`\mathbf{}`$

### 3.2 Well-chosen Flipturns

Here we develop upper and lower bounds on the length of the shortest sequence of flipturns required to convexify an orthogonal polygon. For any polygon $`P`$, let $`\mathrm{}(P)`$ denote its axis-aligned bounding rectangle.

###### Theorem 3.2

For all $`n`$, there is an orthogonal $`n`$-gon that requires $`3(n4)/4`$ standard or extended flipturns to convexify.

* When $`n`$ is a multiple of $`4`$, the polygon consists of a horizontally symmetric rectangular ‘comb’ with $`n/4`$ ‘teeth’; if $`n`$ is not a multiple of $`4`$, we add a small rectangular notch in a bottom corner of the polygon. See Figure 3.3. (We consider a rectangle to be a comb with one tooth.) Both the teeth and the gaps between them decrease in height as they approach the middle of the polygon. Since the polygon is symmetric about its vertical bisecting line, standard and extended flipturns have exactly the same effect. The only way to eliminate the comb is through a sequence of orthogonal flipturns across the top edge of the polygon’s bounding box; each such flipturn eliminates exactly one tooth. It easily follows that *every* flipturn sequence for this polygon has length $`3(n4)/4`$. $`\mathbf{}`$

###### Lemma 3.3

Let $`P`$ be an orthogonal polygon.

1. If some vertex of $`\mathrm{}(P)`$ is not a vertex of $`P`$, then $`P`$ has a diagonal pocket.
2. If two adjacent vertices of $`\mathrm{}(P)`$ are not vertices of $`P`$, then we can perform at least two consecutive diagonal flipturns on $`P`$.

* (a) Suppose some corner of $`\mathrm{}(P)`$ is not a vertex of $`P`$. Some edge of $`\mathrm{conv}(P)`$ lies on a line separating the missing corner from the interior of $`P`$. This edge contains a diagonal lid.

(b) Without loss of generality, suppose $`P`$ does not contain the top left and top right vertices of $`\mathrm{}(P)`$. Part (a) implies that $`P`$ has at least two diagonal pockets. Let $`Q`$ be the result of flipturning one of these pockets. Since the width of the flipturned pocket is less than the width of $`P`$, and thus less than the width of $`Q`$, at least one of the upper corners of $`\mathrm{}(Q)`$ is not a vertex of $`Q`$. (As Figure 3.4 shows, flipturning one pocket can capture the opposite corner.) Thus, by part (a), $`Q`$ still has at least one diagonal pocket. $`\mathbf{}`$

This lemma is a special case of a more general result, whose proof we omit: If any $`k`$ vertices of $`\mathrm{}(P)`$ are not vertices of $`P`$, then we can perform at least $`k`$ consecutive diagonal flipturns on $`P`$.

###### Theorem 3.4

Any orthogonal $`n`$-gon can be convexified by a sequence of at most $`3(n4)/4`$ extended flipturns.

* We achieve the stated upper bound by performing an orthogonal extended flipturn only when no diagonal pockets are available. By Lemma 3.3, we are forced to perform an orthogonal flipturn on a polygon $`P`$ if and only if all four corners of $`\mathrm{}(P)`$ are also vertices of $`P`$.

Let $`P`$ be a nonconvex orthogonal $`n`$-gon with bounding box $`\mathrm{}(P)`$, and suppose $`P`$ has no diagonal pockets. Without loss of generality, suppose $`P`$ has an extended orthogonal pocket whose lid $`lr`$ is the top edge of $`\mathrm{}(P)`$. This pocket obviously lies strictly between the vertical lines through $`l`$ and $`r`$. Let $`P_1`$ be the polygon that results when this extended pocket is flipturned. The highest vertices of $`P_1`$ are vertices of the newly flipturned pocket, and thus must lie strictly between the vertical lines through $`l`$ and $`r`$. Thus, neither of the top vertices of $`\mathrm{}(P_1)`$ is a vertex of $`P_1`$, and by Lemma 3.3, we can perform at least two consecutive diagonal flipturns on $`P_1`$. See Figure 3.5.

In other words, any orthogonal extended flipturn can be followed by at least two diagonal flipturns. Thus, if we perform orthogonal flipturns only when no diagonal flipturn is available, any three consecutive flipturns eliminate at least four vertices. $`\mathbf{}`$

Theorem 3.2 implies that this result is the best possible for extended flipturns. For standard flipturns, we obtain the following slightly weaker upper bound.

###### Theorem 3.5

Any orthogonal $`n`$-gon can be convexified by a sequence of at most $`5(n4)/6`$ standard flipturns.

* As in the previous theorem, we achieve the upper bound by performing orthogonal flipturns only when no diagonal flipturn is available. However, we also choose orthogonal flipturns carefully if more than one is available. Say that an orthogonal flipturn is *good* if it can be followed by at least two diagonal flipturns and *bad* otherwise. We will perform a bad orthogonal flipturn only if no good orthogonal flipturn or diagonal flipturn is available.

Let $`P`$ be an orthogonal polygon. Without loss of generality, consider a forced orthogonal flipturn whose lid $`bc`$ lies on the top edge of $`\mathrm{}(P)`$, and let $`P_1`$ be the polygon resulting from this flipturn. See Figure 3.6(a). The lid endpoints $`b`$ and $`c`$ must lie in two different pockets of $`P_1`$, since the flipturned pocket touches the top of $`\mathrm{}(P_1)`$. The horizontal width of the pocket must be less than the horizontal width of $`P`$, so $`P_1`$ cannot have both the upper left and upper right corners of $`\mathrm{}(P_1)`$ as vertices. Thus, by Lemma 3.3, any forced orthogonal flipturn can be followed first by a diagonal flipturn and then by at least one more (possibly orthogonal) flipturn. In particular, any bad flipturn can be followed by exactly one diagonal flipturn.

Let $`P`$ be a polygon with no diagonal pockets or good orthogonal pockets. Consider a bad orthogonal flipturn whose lid $`bc`$ is a subset of the top edge $`ad`$ of $`\mathrm{}(P)`$, and let $`P_1`$ be the resulting polygon. Exactly one of the top corners of $`\mathrm{}(P_1)`$ is a vertex of $`P_1`$. If this is the top right corner, call pocket $`bc`$ *dexter*; otherwise, call it *sinister*. Without loss of generality, suppose the pocket $`bc`$ is dexter. Let $`P_2`$ be the polygon resulting from the only available diagonal flipturn, whose lid is the upper left edge of $`\mathrm{conv}(P_1)`$. Since $`P_2`$ must have no diagonal pockets, this flipturn moves vertex $`b`$ to the upper left corner of $`\mathrm{}(P_2)`$. See Figure 3.6(c).

If some pocket had a lid in $`ab`$, that pocket would be inverted by the diagonal flipturn on $`P_1`$ and $`P_2`$ would have a diagonal pocket, contradicting our assumption that pocket $`bc`$ is bad. Similarly, if there is a bad pocket with lid in $`cd`$, it cannot be dexter. Suppose there is a sinister pocket with lid $`stcd`$. Let $`l`$ be a leftmost point in pocket $`bc`$, and let $`r`$ be a rightmost point in pocket $`st`$. See Figure 3.6(b). The horizontal distance from $`l`$ to $`b`$ must be equal to $`|cd|`$, and the horizontal distance from $`t`$ to $`r`$ must equal to $`|as|`$, since both pockets are bad. But this is impossible, since $`|cd|+|as|>|ad|`$. We conclude that $`bc`$ must be the *only* lid on the top edge of $`\mathrm{}(P)`$.

Now consider the orthogonal pocket of $`P_2`$ created when pocket $`bc`$ is flipturned. Its lid $`de`$ lies on the right edge of $`\mathrm{}(P_2)`$. We claim that this pocket must be good. Let $`P_3`$ be the resulting polygon when this pocket is flipturned. Since $`cd`$ is the bottommost edge of pocket $`de`$, nothing in $`P_3`$ lies above and to the right of vertex $`e`$, so the upper right vertex of $`\mathrm{}(P_3)`$ is not a vertex of $`P_3`$. Since the height of pocket $`de`$ is less than the height of the original polygon $`P`$, the bottom right vertex of $`\mathrm{}(P_3)`$ is also not a vertex of $`P_3`$. Therefore, by Lemma 3.3, $`P_3`$ can undergo at least two consecutive flipturns.

We have just shown that any forced bad flipturn is immediately followed by a diagonal flipturn, a good orthogonal flipturn, and then two diagonal flipturns. Thus, any sequence of five consecutive flipturns contains at least three diagonal flipturns, which remove at least six vertices from the polygon. $`\mathbf{}`$

We do not believe that this upper bound is tight. In the following section, we will show that the algorithm used to prove the upper bound may not produce the shortest flipturn sequence.

### 3.3 Arbitrary Flipturns

In this section, we consider the length of the *longest* sequence of flipturns that an orthogonal polygon can undergo.

###### Theorem 3.6

For all $`n>4`$, the longest standard or extended flipturn sequence for any orthogonal $`n`$-gon has length at most $`n5`$.

* We call an edge of an orthogonal polygon a *bracket* if both its vertices are convex or both its vertices are concave. An orthogonal $`n`$-gon has at least four brackets (the highest, leftmost, lowest, and rightmost edges) and at most $`n2`$ brackets.

We claim that flipturns do not increase the number of brackets, and that any orthogonal flipturn decreases the number of brackets by two. Let $`P`$ be an orthogonal polygon and let $`Q`$ be the result of one flipturn. Any bracket of $`P`$ that lies completely outside the flipturned pocket is still a bracket in $`Q`$; any bracket completely inside the flipturned pocket is inverted, but remains a bracket. Thus, to prove our claim, it suffices to consider just four edges, namely, the two edges adjacent to each endpoint of the lid. After symmetry considerations, there are only three cases to check for orthogonal pockets and ten cases for diagonal pockets. These cases are illustrated in Figure 3.7.

Since each orthogonal flipturn removes two brackets, and no diagonal flipturn adds brackets, there can be at most $`(n6)/2`$ orthogonal flipturns. Since each diagonal flipturn removes two vertices, and no orthogonal flipturn adds vertices there can be at most $`(n4)/2`$ diagonal flipturns. Thus, there can be at most $`(n6+n4)/2=n5`$ flipturns altogether. $`\mathbf{}`$

We can improve this upper bound slightly in the special case of *lattice* polygons—orthogonal polygons where every edge has unit length (or more generally, where every edge has integer length and $`n`$ denotes the perimeter instead of the number of edges).

###### Theorem 3.7

The longest flipturn sequence for any lattice $`n`$-gon has length at most $`n2\sqrt{n}`$.

* In any convexifying sequence, there are exactly $`n/22`$ diagonal flipturns. Every orthogonal flipturn increases the perimeter of the polygon’s bounding box by at least $`2`$. The initial bounding box has perimeter at least $`4(\sqrt{n}1)`$, and the final rectangle has perimeter exactly $`n`$, so the maximum number of orthogonal flipturns is at most $`n/22\sqrt{n}+2`$. $`\mathbf{}`$

How tight is the $`n5`$ upper bound? As in the case of the shortest flipturn sequence, the answer depends on whether we consider standard or extended flipturns. Unfortunately, we do not obtain an exact answer in either case.

###### Theorem 3.8

For all $`n`$, there is an orthogonal $`n`$-gon that can undergo $`3(n4)/4`$ extended flipturns.

* This follows directly from Theorem 3.2. $`\mathbf{}`$

###### Theorem 3.9

For all $`n`$, there is an orthogonal $`n`$-gon that can undergo $`5(n4)/6`$ standard flipturns.

* We construct an orthogonal $`n`$-gon $`P_n`$ essentially by following the proof of Theorem 3.5. $`P_4`$ is a rectangle. $`P_6`$ is an L-shaped hexagon, which is convexified by one flipturn. $`P_8`$ is a rectangle with a rectangular orthogonal pocket in one side, which requires three flipturns to convexify. For all $`n10`$, $`P_n`$ consists of a rectangle with a single L-shaped pocket, where the tail of the L is an inverted and reflected copy of $`P_{n6}`$. See Figure 3.8. In the language of the proof of Theorem 3.5, $`P_n`$’s only pocket is *bad*—flipturning it creates one diagonal pocket and one orthogonal pocket. If we flipturn diagonal pockets whenever possible, the first five flipturns eliminate six vertices and leave a distorted $`P_{n6}`$. The theorem follows by induction. $`\mathbf{}`$

To prove Theorem 3.5, we used an algorithm that always prefers diagonal flipturns to orthogonal flipturns and good orthogonal flipturns to bad orthogonal flipturns. We can use the polygon $`P_n`$ from the previous proof to show that this algorithm is not optimal, by demonstrating a shorter convexifying flipturn sequence. Figure 3.9 shows the first sixteen flipturns performed by a modified algorithm, which ignores diagonal ‘notches’ in the upper and lower right corners of the polygon. Figure 3.9(b) is distorted to reveal relevant but otherwise invisible details; the distortion does not change which flipturns we can perform at any time. These $`16`$ flipturns remove $`24`$ vertices, thereby transforming $`P_n`$ into $`P_{n24}`$. Thus, by induction, we can convexify $`P_n`$ in only $`2(n4)/3`$ flipturns whenever $`n4`$ is a multiple of $`24`$.

The ignored ‘notches’ are precisely the diagonal flipturns that do not remove brackets; see Theorem 3.6. Perhaps a modified algorithm that tries to reduce the number of brackets as fast as possible, as well as the number of vertices, would improve Theorem 3.5. We leave the development of such an algorithm as an intriguing open problem.

Finally, we observe that $`P_n`$ can be convexified using exactly $`2(n3)/3`$ extended flipturns. We leave the proof as an easy exercise of the reader.

## 4 Flipturn Sequences for Arbitrary Polygons

In this section, we derive upper bounds for the longest flipturn sequences of arbitrary polygons, generalizing both our earlier results for orthogonal polygons and the modified flipturn results of Ahn *et al.* .

Consider an arbitrary polygon $`P`$ whose boundary is oriented counterclockwise. Let $`\stackrel{}{e}`$ denote the direction of any (oriented) edge $`e`$ in $`P`$, let $`S`$ be the set of all such edge directions and their edge reversals. We clearly have $`s|S|2s`$, where $`s`$ is the number of distinct edge slopes. Ahn *et al.* define the *discrete angle* at a vertex $`v=ee^{}`$ to be one more than the number of elements of $`S`$ inside the angle between $`\stackrel{}{e}`$ and $`\stackrel{}{e}^{}`$. The *total discrete angle* $`D(P)`$ is the sum of the discrete angles at the vertices of $`P`$.

Ahn *et al.* prove the following lemma . (Only the first half of this lemma is stated explicitly, but their proof implies the second half as well.)

###### Lemma 4.1

Every non-degenerate flipturn decreases $`D(P)`$ by at least two, and every degenerate flipturn leaves $`D(P)`$ unchanged.

Ahn *et al.* also prove that $`D(P)n(s1)`$ in general and $`D(P)=2s`$ if $`P`$ is convex. Thus, Lemma 4.1 immediately implies that $`(nsn2s)/2n(n3)/2`$ nondegenerate flipturns suffice to convexify any polygon. However, since no bound was previously known for the number of degenerate flipturns, this bound does not apply to degenerate polygons. To avoid this problem, Ahn *et al.* introduce modified flipturns, for which degeneracies do not exist. To account for degenerate flipturns under the standard definition, we study the change in the number of *brackets*, here denoted $`B(P)`$, as in Section 3.3.

###### Lemma 4.2

Every non-degenerate standard or extended flipturn increases $`B(P)`$ by at most two, and every degenerate standard or extended flipturn decreases $`B(P)`$ by at least two.

* Let $`P`$ be a simple polygon and let $`P^{}`$ be the result of one flipturn. As we argued in the proof of Theorem 3.6, it suffices to focus on brackets touching the endpoints of the lid. Let $`b`$ and $`b^{}`$ denote the number of boundary brackets in $`P`$ and $`P^{}`$, respectively, so that $`B(P^{})=B(P)b+b^{}`$.

For nondegenerate flipturns, it suffices to consider only flipturns with $`b1`$, since $`b^{}`$ is never more than $`4`$. There are three cases to consider: no boundary brackets, one outer boundary bracket, and one inner boundary bracket. For each of these, there are nine subcases, depending on whether each lid endpoint becomes a convex vertex, becomes a concave vertex, or disappears after the flipturn. These cases are illustrated in Figure 4.1.

Standard degenerate flipturns always have two outer brackets, and both lid endpoints always become concave vertices. Thus, there are only three cases to consider, depending on the number of inner brackets, exactly as in Theorem 3.6. Similar arguments apply to extended flipturns. $`\mathbf{}`$

###### Theorem 4.3

Every $`s`$-oriented polygon is convexified after any sequence of $`ns(n+5s)/21`$ standard or extended flipturns.

* We define the *potential* $`\mathrm{\Phi }`$ of a polygon to be its discrete angle plus half the number of brackets, that is, $`\mathrm{\Phi }=D+B/2`$. For the initial polygon $`P`$, we have $`Dn(s1)`$ and $`Bn2`$, so the initial potential $`\mathrm{\Phi }`$ is at most $`nsn/21`$. For the final convex polygon, we have $`D=2s`$ and $`Bs`$, so the final potential $`\mathrm{\Phi }^{}`$ is at least $`5s/2`$. By Lemmas 4.1 and 4.2, every flipturn reduces the potential by at least one. Thus, after any sequence of $`\mathrm{\Phi }^{}\mathrm{\Phi }=nsn/25s/21`$ flipturns, the polygon must be convex. $`\mathbf{}`$

If we set $`s=n`$, we obtain the upper bound $`n^23n1`$ for arbitrary simple polygons. However, if $`s=n`$, there can be no degenerate flipturns, so the discrete angle results from Ahn *et al.* apply directly, giving us the upper bound $`n(n3)/2`$. Hence, the actual worst case arises when $`s=n1`$.

###### Corollary 4.4

Every simple polygon is convexified after any sequence of $`n^24n+2`$ standard or extended flipturns.

This upper bound is almost certainly not tight. Intuitively, if $`s`$ large, only a few pairs of edges can have the same slope, so the maximum number of degenerate flipturns should be small.

We can improve our results in some cases using a different definition of discrete angle. Let $`T`$ denote the set of edge directions (*without* their reversals), let $`t=|T|`$, and let $`ht1`$ be the maximum number of edge directions that fit in an open half-circle. The discrete angle at any vertex is at most $`h1`$, so $`D(P)n(h1)n(t2)`$ for any polygon $`P`$; if $`P`$ is convex, then $`D(P)=t`$. Lemma 4.1 still holds under this new definition. Thus, we obtain the following upper bounds.

###### Theorem 4.5

Every simple polygon is convexified after any sequence of $`(nhnt)/2t(n1)/2n`$ modified flipturns or $`nh(n+3t)/21nt3(n+t)/21`$ standard or extended flipturns.

This theorem improves all earlier results whenever $`h`$ is significantly smaller than $`t`$. For general polygons, setting $`h=t1=n1`$ gives us the same $`n(n3)/2`$ upper bound for modified flipturns. For standard or extended flipturns, however, we obtain a very slight improvement by setting $`h=t1=n2`$.

###### Corollary 4.6

Every simple polygon is convexified after any sequence of $`n^24n+1`$ standard or extended flipturns.

We close this section with some obvious open questions. Asymptotically, our bounds agree with Joss and Shannon’s conjecture —any polygon can indeed be convexified by $`O(n^2)`$ flipturns—but there is still a significant gap between our upper bounds and the $`(n2)^2/4`$ lower bound construction of Biedl . We, like Joss and Shannon, conjecture that the correct answer is closer to $`n^2/4`$.

A more interesting open question concerns the length of *shortest* flipturn sequences for general polygons. The best lower bounds are those derived for orthogonal polygons in Section 3, but not subquadratic upper bounds are known. Can arbitrary polygons be convexified with only $`O(n)`$ flipturns, or does some polygon require a super-linear number of flipturns to convexify?

## 5 Data Structures for Flipturns

In this section, we describe efficient data structures for executing a sequence of flipturns on any simple (not necessarily orthogonal) polygon. We first describe a simpler data structure that maintains an implicit description of a polygon $`P`$ as flipturns are performed, without worrying about how the flipturns are chosen. Then we will describe how to maintain the convex hull of $`P`$ as we perform flipturns, so that we can determine which flipturns are available at any time.

###### Lemma 5.1

After $`O(n)`$ preprocessing time, we can maintain an implicit description of a simple $`n`$-gon in $`O(\mathrm{log}n)`$ time per flipturn, using a data structure of size $`O(n)`$.

* It suffices to store only the slopes and lengths of the edges in the proper order, without explicitly storing the vertex coordinates. Any flipturn reverses a contiguous chain of edges, namely, the edges of the flipturned pocket. Our goal, therefore, is to maintain a circular list of items subject to the operation $`\text{Reverse}(s,t)`$, which reverses the sublist starting with item $`s`$ and ending with item $`t`$. For example, if the initial list is $`(a,b,c,d,e,f,g,h)`$, then $`\text{Reverse}(c,f)`$ produces the list $`(a,b,f,e,d,c,g,h)`$, after which $`\text{Reverse}(d,a)`$ produces $`(h,g,c,d,b,f,e,a)`$.

We store the edges in the leaves of a balanced binary search tree, initially in counterclockwise order around the polygon. Rather than explicitly reversing chains of edges, we will store a *reversal bit* $`r_v`$ at every node $`v`$, indicating whether that subtree should be considered reversed, relative to the orientation of the subtree rooted at $`v`$’s parent. Initially, all reversal bits are set to $`0`$.

Our algorithm for $`\text{Reverse}(s,t)`$ is illustrated in Figure 5.1. Without loss of generality, we assume that $`s`$ appears before $`t`$ in the linear order stored in the tree; otherwise, we simply toggle the reversal bit at the root and call $`\text{Reverse}(t,s)`$. First, we split the tree into three subtrees, containing the items to the left of $`s`$, items between $`s`$ and $`t`$, and the items to the right of $`t`$. Second, we toggle the reversal bit at the root of the middle tree. Finally, we merge the three trees back together. Each split or merge can be performed using $`O(\mathrm{log}n)`$ rotations (using red-black trees , splay trees , or treaps , for example), and we can easily propagate the reversal bits correctly at each rotation. $`\mathbf{}`$

To maintain the convex hull of a polygon under flipturns, we use a variant of the dynamic convex hull data structure of Overmars and van Leeuwen , which maintains the convex hull of a dynamically changing set of points in $`O(\mathrm{log}^2n)`$ time per insertion or deletion. Their data structure consists of a balanced binary tree that allows insertions, deletions, splits, and merges in $`O(\mathrm{log}n)`$ time. The points are stored at the leaves of this tree, ordered by their $`x`$-coordinates. Each node in the tree stores the convex hull of the points in its subtree; we call this the node’s *subhull*. Except at the root, these subhulls are not stored explicitly; rather, each node stores only the chain of edges of its subhull that are not in its parent’s subhull. Overmars and van Leeuwen show that any node’s subhull can be computed in $`O(\mathrm{log}n)`$ time from its children’s subhulls, by finding the outer common tangent lines.

There are several differences between our problem and the standard dynamic convex hull problem. The most significant difference is that we need to support an operation similar to Reverse in polylogarithmic time. This requires us to store the vertices in their order of appearance around the polygon, rather than in any coordinate order. Moreover, since a linear number of vertices could be affected by a flipturn, our data structure must implicitly represent both the order and the locations of the vertices. A second significant difference lies in the structure of the subhulls. In Overmars and van Leeuwen’s data structure, the subhulls of any two siblings in the tree are separated by a known vertical line. In our case, sibling subhulls are *pseudo-disks*: either they have disjoint interiors, or they have nested closures, or their boundaries intersect transversely at exactly two points. Distinguishing these three cases and merging the subhulls in each case requires considerably more effort. Finally, one minor difference is that for standard flipturns, we must maintain the complete sequence of polygon vertices on the boundary of the convex hull, not just the convex hull vertices. This requires only trivial modifications, which do not deserve further mention.

###### Lemma 5.2

After $`O(n\mathrm{log}n)`$ preprocessing time, we can maintain an implicit description of the convex hull of a simple $`n`$-gon in $`O(\mathrm{log}^4n)`$ time per flipturn, using a data structure of size $`O(n)`$.

* We maintain the polygon vertices in a balanced binary tree, similarly to the proof of Lemma 5.1. The coordinates of the points are represented implicitly by storing a triple $`(r_v,x_v,y_v)`$ at each internal node $`v`$, encoding an affine transformation to be applied to all edges in the subtree of $`v`$. Specifically, $`(x_v,y_v)`$ is a translation vector for all edges in $`v`$’s subtree if $`r_v=0`$ and a point of reflection if $`r_v=1`$. Initially, $`r_v=x_v=y_v=0`$ for all nodes $`v`$. The actual position of any vertex can be recovered in $`O(\mathrm{log}n)`$ time by composing the transformations along the path up to the root. We can easily maintain these triples under rotations, splits, and merges, similarly to the Reverse algorithm described earlier. We omit the unenlightening details.

Each node in this tree also stores the portion of its subhull not included in its parent’s subhull. Specifically, we store the vertices of this convex chain in a secondary balanced binary tree. Instead of explicitly storing the coordinates of the vertices of this chain, however, we store only pointers to the appropriate leaves in the primary binary tree. The coordinates of any point can be recovered in $`O(\mathrm{log}n)`$ time by composing the linear transformations stored on the path up from the point’s leaf.

It remains only to show that we can merge any two sibling subhulls quickly. If we can merge two sibling subhulls in time $`T(n)`$ when all vertex coordinates are given explicitly, then we can update the convex hull of $`P`$ in time $`O(T(n)\mathrm{log}^2n)`$ per flipturn. One logarithmic factor is the number of merges we must perform for each flipturn; the other is the cost of accessing the implicitly-stored vertex coordinates.

Let $`C`$ be the chain of polygon edges associated with some node $`v`$ in the primary binary tree, and let $`A`$ and $`B`$ be the subchains associated with the left and right children of $`v`$, respectively. Since $`C`$ has no self-intersections, the boundaries of the convex hulls $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$ can intersect in at most two points. If the hull boundaries do not intersect, then the hulls can be either disjoint or nested. See Figure 5.2.

If $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$ are nested, then one of them is the convex hull of $`C`$. In general, deciding whether to given convex polygons are nested requires $`\mathrm{\Omega }(n)`$ time, but the special structure of our problem allows a faster solution. We define the *entrance* and *exit* of a polygonal chain $`C`$ as follows. The entrance of $`C`$ is a pair of rays whose common basepoint is the first vertex of $`C`$ that is also a vertex of $`\mathrm{conv}(C)`$; the rays contain the convex hull edges on either side of this vertex. The exit of $`C`$ is a similar pair of rays based at the last vertex of $`C`$ that is also a vertex of $`\mathrm{conv}(C)`$. See Figure 5.3.

Let $`a`$ be the last vertex of $`A`$, and let $`b`$ be the first vertex of $`B`$. The segment $`ab`$ does not intersect $`B`$, so if $`a`$ is outside the convex hull of $`B`$, then $`a`$ must be outside the entrance of $`B`$ (*i.e.*, on the opposite side of the entrance from $`B`$). More generally, $`\mathrm{conv}(A)\mathrm{conv}(B)`$ if and only if $`\mathrm{conv}(A)`$ lies completely inside the entrance of $`B`$.333If $`b`$ is not a vertex of $`\mathrm{conv}(B)`$, we can simplify the entrance of $`B`$ to a line through just one convex hull edge. While this modification simplifies our algorithm somewhat, it does not significantly improve the running time. Similarly, $`\mathrm{conv}(B)\mathrm{conv}(A)`$ if and only if $`\mathrm{conv}(B)`$ lies completely inside the exit of $`A`$. We can test in $`O(\mathrm{log}n)`$ time whether a convex polygon (represented as an array of vertices in counterclockwise order) lies inside a wedge. Thus, if we can compute the entrance and exit of any chain given those of its children, then we can test for nested sibling subhulls in $`O(\mathrm{log}n)`$ time. Fortunately, this is quite easy. If both edges of $`\mathrm{conv}(A)`$ defining the entrance of $`B`$ are also edges of $`\mathrm{conv}(C)`$, then the entrance of $`C`$ is just the entrance of $`A`$. Otherwise, the entrance of $`C`$ contains one of the two outer common tangents between $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$.

Now suppose $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$ are not nested. Using an algorithm of Chazelle and Dobkin , we can decide in $`O(\mathrm{log}n)`$ time whether $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$ intersect. If the two convex hulls have disjoint interiors, their algorithm also returns a separating line $`\mathrm{}`$.444Chazelle and Dobkin’s algorithm returns a pair of parallel separating lines, one tangent to each polygon, but this is unnecessary for our result. See also . If we use $`\mathrm{}`$ as a local vertical direction, we can divide $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$ into separate upper and lower hulls, such that one outer common tangent joins the two upper hulls and the other joins to two lower hulls. This is precisely the setup required by the algorithm of Overmars and van Leeuwen, which finds these two common tangents in $`O(\mathrm{log}n)`$ time .

Finally, suppose the boundaries of $`\mathrm{conv}(A)`$ and $`\mathrm{conv}(B)`$ intersect at two points. In this case, we can find the two outer common tangent lines between them, and thus compute $`\mathrm{conv}(C)`$, in $`O(\mathrm{log}^2n)`$ time. To find (say) the upper common tangent of $`A`$ and $`B`$, we perform a modified binary search over the vertices of $`\mathrm{conv}(A)`$. At each step of this binary search, we find the upper tangent line $`\mathrm{}`$ to $`\mathrm{conv}(B)`$ (if any) passing through a vertex $`a\mathrm{conv}(A)`$ in $`O(\mathrm{log}n)`$ time, using a second-level binary search.

Thus, we can compute the convex hull, entrance, and exit of $`C`$ from the convex hulls, entrances, and exits of $`A`$ and $`B`$ in $`O(\mathrm{log}^2n)`$ time. By our earlier argument, it follows that we can maintain the convex hull of $`P`$ in $`O(\mathrm{log}^4n)`$ time per flipturn. We can build the original data structure in $`O(n\mathrm{log}n)`$ time by explicitly computing the convex hulls of each subchain, each in linear time. $`\mathbf{}`$

###### Theorem 5.3

Given a simple $`n`$-gon $`P`$, a convexifying sequence of flipturns can be computed in $`O(L\mathrm{log}^4n)`$ time, where $`L`$ is the length of the computed sequence.

* We can construct the data structures to maintain the polygon and its convex hull in $`O(n\mathrm{log}n)`$ time. In addition to the convex hull itself, we maintain a separate list of the lids of $`P`$, which requires only trivial additions to our data structures. This allows us to choose a legal flipturn in constant time. By Lemma 5.2, we can maintain both the polygon and its convex hull in $`O(\mathrm{log}^4n)`$ time per flipturn. $`\mathbf{}`$

This theorem has an immediate corollary, using the results of Ahn *et al.*  and our Theorems 3.6 and 4.3.

###### Corollary 5.4

Given an $`s`$-oriented $`n`$-gon, a convexifying sequence of flipturns can be computed in $`O(sn\mathrm{log}^4n)`$ time. In particular, for orthogonal polygons, a convexifying flipturn sequence can be computed in $`O(n\mathrm{log}^4n)`$ time.

For orthogonal polygons, we can modify our algorithm to find a flipturn sequence satisfying Theorem 3.5, still in $`O(n\mathrm{log}^4n)`$ time. We maintain the diagonal pockets and orthogonal lids of $`P`$ in separate lists. If there is a diagonal pocket, we flipturn it. Otherwise, if some edge of the bounding box contains more than one lid, we flipturn one of those pockets. If each edge of the bounding box has at most one lid, we can check whether any of these pockets is bad in $`O(\mathrm{log}^4n)`$ time. To check one pocket, we flipturn it and count diagonal pockets; if there is only one, we flipturn that and count again. If the pocket is bad and the original polygon has any unchecked pockets, we undo the flipturn(s) and try the next pocket. Each bad flipturn requires at most seven flipturns and six anti-flipturns. The proof of Theorem 3.5 ensures that we perform at most $`(n4)/6`$ bad flipturns, so the total number of data structure updates is at most $`17(n4)/6=O(n)`$.

It seems quite likely that our data structure can be improved. One obvious bottleneck in our algorithm is finding common tangents between intersecting convex pseudo-disks, which currently takes $`O(\mathrm{log}^2n)`$ time. The more recent dynamic convex hull results of Chan  and Brodal and Jakob  may also be useful here. On the other hand, we are unable to prove even an $`\mathrm{\Omega }(n\mathrm{log}n)`$ lower bound, even for arbitrary polygons. What is the true complexity of computing flipturn sequences?

## 6 Order Doesn’t Matter

Joss and Shannon showed that any simple polygon $`P`$ can be transformed into a convex polygon by a sufficiently long sequence of flipturns. If we always direct polygon edges so that they form a counterclockwise cycle, then flipturns do not change the direction of any edge. Since flipturns also do not change edge lengths, the final convex shape of $`P`$ is the same for any convexifying flipturn sequence. We can easily compute this shape in $`O(n\mathrm{log}n)`$ time by sorting the edges of $`P`$ by their orientation. For $`s`$-oriented polygons, this requires only $`O(n\mathrm{log}s)`$ time.

In this section, we show that the *position* of the final convex polygon is also independent of the flipturn sequence. To prove this result, it suffices to show that we can predict the $`y`$-coordinate of the top edge of the final convex polygon’s bounding box. The position of the left edge follows from a symmetric argument, and these two edges determine the polygon’s final position.

We prove our theorem by induction on the number of flipturns.555The results in this section actually hold for a wider class of pivots called *generalized flipturns*. A generalized flipturn rotates a chain of edges 180 degrees around the midpoint of its endpoints without introducing self-intersections. Generalized flipturns include standard, extended, and modified flipturns as special cases. Let $`P`$ be a non-convex polygon, let $`ab`$ be a lid of some pocket in $`P`$, and let $`c`$ be the midpoint of $`ab`$. We subdivide the plane into horizontal strips using the horizontal line $`\mathrm{}_0`$ through $`c`$, the horizontal lines $`L`$ passing through every vertex of $`P`$, and the reflection $`L^{}`$ of $`L`$ across $`\mathrm{}_0`$. Number the strips $`1,2,3,\mathrm{}`$ counting upwards from $`\mathrm{}_0`$ and $`1,2,3,\mathrm{}`$ counting downwards from $`\mathrm{}_0`$. With this numbering, any strip $`i`$ is the reflection of strip $`i`$ across $`\mathrm{}_0`$. In particular, strips $`i`$ and $`i`$ have the same width, which we denote $`w_i`$. There are at most $`2n+2`$ strips altogether.

These strips subdivide the exterior of $`P`$ into trapezoidal regions. We classify these trapezoids into several groups. If a region is unbounded, we call it an *outer region*; otherwise, we call it an *inner region*. We further classify outer regions into the infinite *strips* above or below $`P`$ (including the top and bottom halfplanes), and the semi-infinite *side regions* to the left or right of $`P`$. We also classify inner regions as *up-regions* and *down-regions* as follows. Consider the shortest path through the exterior of $`P`$ starting at a point in the interior of some inner region $`\rho `$ and ending at a point in some outer region. If the first segment of this path goes up from the starting point, $`\rho `$ is an up-region; otherwise, $`\rho `$ is a down-region. We emphasize that this classification is independent of the starting point within $`\rho `$. We show below that the total height of the up regions is precisely the distance between the top of the current polygon’s bounding box and the top of the final convex polygon’s bounding box.

For each $`i>0`$, let $`u_i`$ denote the number of up-regions in strips $`i`$ and $`i`$, and let $`x_i`$ be the indicator variable equal to $`1`$ if strip $`i`$ intersects $`P`$ and $`0`$ otherwise. See Figure 6.1(a).

Let $`P^{}`$ be the result of flipturning the pocket $`ab`$. This flipturn moves any point on the boundary of the pocket from some strip $`i`$ to the corresponding strip $`i`$. The strips subdivide the exterior of $`P^{}`$ into regions exactly as the exterior of $`P`$, and we define the corresponding variables $`u_j^{}`$ and $`x_j^{}`$ mutatis mutandis. See Figure 6.1(b).

Our core lemma is the following.

###### Lemma 6.1

For all $`i>0`$, $`u_i+x_i=u_i^{}+x_i^{}`$.

* Fix an index $`i>0`$. We prove the theorem by induction on the number of inner regions in the flipturned pocket. If the pocket contains no inner regions, it must be $`y`$-monotone, and we easily observe that $`u_i=u_i^{}`$ and $`x_i=x_i^{}`$.

The inner regions of $`P`$ have a natural forest structure, defined by connecting each region to the next region encountered on a shortest path to infinity. The roots of this forest are inner regions directly adjacent to outer regions, and its leaves are inner regions adjacent to only one other region. Let $`\rho `$ be some leaf region inside pocket $`ab`$, let $`\stackrel{~}{P}=P\rho `$, and define $`\stackrel{~}{u}_i`$ and $`\stackrel{~}{x}_i`$ analogously to $`u_i`$ and $`x_i`$ for this new polygon. Finally, let $`\stackrel{~}{P}^{}`$ be the result of flipturning the now-simpler pocket $`ab`$, let $`\rho ^{}`$ be the image of $`\rho `$ under this flipturn (so $`\stackrel{~}{P}^{}=P^{}\rho ^{}`$), and define $`\stackrel{~}{u}_i^{}`$ and $`\stackrel{~}{x}_i^{}`$ analogously. Since $`\stackrel{~}{P}`$ has one less inner region than $`P`$, the inductive hypothesis implies that $`\stackrel{~}{u}_i+\stackrel{~}{x}_i=\stackrel{~}{u}_i^{}+\stackrel{~}{x}_i^{}`$.

It suffices to consider the case where $`\rho `$ lies either in strip $`i`$ or in strip $`i`$, since otherwise we have $`\stackrel{~}{u}_i=u_i`$, $`\stackrel{~}{x}_i=x_i`$, $`\stackrel{~}{u}_i^{}=u_i^{}`$, and $`\stackrel{~}{x}_i^{}=x_i^{}`$, and so there is nothing to prove. Moreover, if $`\rho `$ is in strip $`i`$, then $`x_i=\stackrel{~}{x}_i=x_i^{}=\stackrel{~}{x}_i^{}=1`$.

Suppose $`\rho `$ is an up-region, so $`\stackrel{~}{u}_i=u_i1`$. Some region $`\stackrel{~}{\sigma }^{}`$ of $`\stackrel{~}{P}^{}`$ is split into two regions by $`\rho ^{}`$. If we imagine a continuous transformation from $`\stackrel{~}{P}^{}`$ to $`P^{}`$, the trapezoid $`\rho ^{}`$ grows upward from the bottom edge of $`\stackrel{~}{\sigma }^{}`$. We have four cases to consider, illustrated in the first two rows of Figure 6.2. (The last row shows the corresponding cases when $`\rho `$ is a down-region.)

In this case $`\rho ^{}`$ splits $`\stackrel{~}{\sigma }^{}`$ into two up-regions, so $`u_i^{}=\stackrel{~}{u}_i^{}+1`$. If $`\rho `$ is in strip $`i`$, then $`\rho ^{}`$ is in strip $`i`$, so $`\stackrel{~}{x}_i^{}=x_i^{}=1`$ and $`x_i=\stackrel{~}{x}_i`$ (but these might be either $`0`$ or $`1`$).

In this case $`\rho ^{}`$ splits $`\stackrel{~}{\sigma }^{}`$ into an up-region and a down-region, so $`u_i^{}=\stackrel{~}{u}_i^{}+1`$. If $`\rho `$ is in strip $`i`$, then $`\stackrel{~}{x}_i^{}=x_i^{}=1`$ and $`\stackrel{~}{x}_i=x_i`$.

In this case $`\rho ^{}`$ splits $`\stackrel{~}{\sigma }^{}`$ into an up-region and a side region, so $`u_i^{}=\stackrel{~}{u}_i^{}+1`$. If $`\rho `$ is in strip $`i`$, then $`\stackrel{~}{x}_i^{}=x_i^{}=1`$ and $`\stackrel{~}{x}_i=x_i`$.

Since $`\rho `$ is an up-region, $`\stackrel{~}{P}^{}`$ must touch the bottom edge of $`\rho ^{}`$, which means that $`\rho ^{}`$ must lie above $`\stackrel{~}{P}`$. In this case $`\rho ^{}`$ splits $`\stackrel{~}{\sigma }^{}`$ into two side regions, so $`u_i^{}=\stackrel{~}{u}_i^{}`$. Since $`\rho ^{}`$ is in strip $`i`$, we have $`x_i=\stackrel{~}{x}_i=\stackrel{~}{x}_i^{}=0`$ but $`x_i^{}=1`$.

The lemma holds in every case. Four similar cases arise when $`\rho `$ is a down-region and $`\stackrel{~}{u}_i=u_i`$. In each case, we have $`\stackrel{~}{u}_i^{}=u_i^{}`$, $`\stackrel{~}{x}_i=x_i`$, and $`\stackrel{~}{x}_i^{}=x_i^{}`$. We omit further details. $`\mathbf{}`$

###### Theorem 6.2

The final convexified position of a polygon is independent of the convexifying flipturn sequence and can be determined in $`O(n)`$ time.

* Let $`w_i`$ denote the vertical width of strip $`i`$ (and strip $`i`$). Lemma 6.1 implies that

$$\underset{i>0}{}(u_i+x_i)w_i=\underset{i>0}{}(u_i^{}+x_i^{})w_i.$$
(1)
Let $`\widehat{y}`$ and $`\widehat{y}^{}`$ denote the $`y`$-coordinates of the top of $`P`$ and $`P^{}`$, respectively, and let $`y_0`$ be the $`y`$-coordinate of the lid midpoint $`c`$. We easily observe that

$$\underset{i>0}{}x_iw_i=\widehat{y}y_0\text{and}\underset{i>0}{}x_i^{}w_i=\widehat{y}^{}y_0.$$
(2)
Finally, define $`U=_{i>0}u_iw_i`$ and $`U=_{i>0}u_i^{}w_i`$. Combining equations (1) and (2), we obtain the identity $`U+\widehat{y}=U^{}+\widehat{y}^{}`$. In other words, the total height of all the up-regions plus the maximum $`y`$-coordinate of the polygon is an invariant preserved by any flipturn.

Let $`P^{}`$ be the convex polygon produced by some sequence of flipturns starting from $`P`$, and define $`U^{}`$ and $`\widehat{y}^{}`$ analogously to $`U`$ and $`\widehat{y}`$. Obviously, $`P^{}`$ has no up-regions, so $`U^{}=0`$. Thus, by induction on the number of flipturns, we have the identity $`\widehat{y}^{}=U+\widehat{y}`$. Since $`U+\widehat{y}`$ is independent of the convexifying flipturn sequence, so is the vertical position of $`P^{}`$.

We can compute $`U`$ in linear time by computing a horizontal trapezoidal decomposition of $`P`$, using Chazelle’s algorithm  or its recent randomized variant by Amato, Goodrich, and Ramos , and then performing a depth-first search of its dual graph.

The argument for the horizontal position of $`P^{}`$ is symmetric. $`\mathbf{}`$

## 7 The Worst Order Is Hard to Find

###### Theorem 7.1

Computing the longest standard or extended flipturn sequence for a simple polygon is NP-hard.

* It suffices to consider the special case of orthogonal polygons. A flipturn sequence for an orthogonal polygon has length greater than $`(n4)/2`$ if and only if it contains an orthogonal flipturn. Thus, to prove the theorem, we only need to show the NP-hardness of the decision problem Orthogonal Flipturn: Given an orthogonal polygon, does *any* flipturn sequence contain an orthogonal flipturn? We prove this problem is NP-complete by a reduction from Subset Sum: Given a set of positive integers $`A=\{a_1,a_2,\mathrm{},a_n\}`$ and another integer $`T`$, does any subset of $`A`$ sum to $`T`$? The reduction algorithm is given in Figure 7.1. The algorithm constructs a polygon in linear time by walking along its edges in clockwise order, starting and ending at the top of the first step. (The algorithm assumes without loss of generality that $`n`$ is even.) Figure 7.2 shows an example of the reduction.

The basic structure of the polygon is a staircase, with one square step for each of the $`a_i`$, plus one long step of height $`T`$ splitting the other steps in half. Just below each of the upper steps is an an inward horizontal spike; just above each of the lower steps is an outward horizontal spike; and just behind the long step is a vertical *test spike* of length exactly $`T`$. The horizontal spikes all have length greater than $`T`$, and they increase in length as they get closer to the top and bottom of the polygon.

At any point during the flipturning process, the polygon has one main pocket containing the test spike and several secondary pockets containing one or more smaller steps, each of whose heights is some $`a_i`$. Initially, there is just one secondary pocket, of height and width $`a_1`$. The $`i`$th step (*i.e.*, the one with height $`a_i`$) is exposed the $`(i1)`$th time the main pocket is flipturned. No matter which flipturns we perform before flipturning the test spike, the vertical distance $`\mathrm{\Delta }`$ between the top endpoint of the main pocket’s lid and the top edge of the polygon’s bounding box is always the sum of elements of $`A`$. Specifically, if we flipturn every step whose size is an element of some subset $`BA`$ as soon as it becomes available, then just before the test spike is flipped, $`\mathrm{\Delta }`$ is the sum of the elements of $`AB`$; see Figure 7.2(b). Thus, since the test spike has length $`T`$, flipturning it can create an orthogonal pocket if and only if some subset of $`A`$ sums to $`T`$. $`\mathbf{}`$

Note that the polygon produced by our reduction never has more than one orthogonal pocket; the longest flipturn sequence has either $`(n4)/2`$ or $`(n2)/2`$ flipturns. Thus, even approximating the maximum number of orthogonal flipturns is NP-hard.

Our reduction only proves that finding the longest flipturn sequence is *weakly* NP-hard. In particular, it says nothing about *lattice* polygons in their standard representation as a cycle of unit-length orthogonal segments. We conjecture that for such polygons, there is a polynomial time dynamic programming algorithm, similar to the $`O(nT)`$ algorithm for SubsetSum.

Finally, how hard is it to find the *shortest* sequence of flipturns that convexifies a given simple polygon? It seems unlikely that the question “Does *every* flipturn sequence have an orthogonal flipturn?” is NP-hard.

### Acknowledgments

All but one of the authors thank Godfried Toussaint for organizing the Barbados workshop where most of this work was done. Thanks also to David Bremner, Ferran Hurtado, Vera Sacristán, and Mike Soss for sharing coffee, rum, and ideas.


format: text

text:
# Comparing Giant Molecular Clouds in M31, M33 & the Milky Way

## 1 Introduction

Molecular gas is a major constituent of the interstellar medium in the inner disks of spiral galaxies. It is organized into discrete entities (clouds and cloud complexes) and virtually all star formation is associated with them (see reviews by Scoville 1990; Combes 1991; Blitz 1993). However, the molecular cloud populations and properties in external galaxies are not well known because of the difficulty in obtaining the high resolution, high sensitivity data required for spatially resolving individual complexes. For instance, in the nearest spiral M31, a typical molecular cloud ($``$40 pc) has an angular size of 12′′, comparable to the beam of the world’s largest single dish millimeter-wavelength telescope in the CO(1-0) line.

Interferometric observations can achieve the higher resolution necessary, and with improved receiver technology and other advances, several molecular clouds have been detected in both M31 (Vogel, Boulanger & Ball 1987; Wilson & Rudolph 1993) and M33 (Wilson & Scoville 1990, 1992). With forthcoming arrays like CARMA and ALMA, it will be possible to study molecular clouds over the entire disks of galaxies as far away as the Virgo cluster. In order to compare such interferometric observations with Milky Way studies, we must understand the effects of spatial filtering of interferometers. In addition, we must understand which if any of the various methods of identifying molecular clouds are appropriate for comparing clouds in different galaxies. In this contribution, we address these issues by comparing molecular clouds using new and existing data for M31, M33 and the Milky Way.

## 2 Data: New M31 Observations & Existing Data

In Figure 1, we show a velocity-integrated CO(J=1–0) BIMA (Berkeley-Illinois-Maryland Association) map in contours overlaid on a grey-scale optical image. Most of the CO emission lies in the two dust lanes which are separated by a distance of 2 kpc (assuming $`i`$=77o). Our mass sensitivity limit for these data is 5$`\times `$104$`M_{}`$. We also obtained the interferometric OVRO data for M33 (Wilson & Scoville 1990) and parts of the 1.2m Columbia Survey (Dame et al. 1987) for four large ($``$105-106$`M_{}`$) Milky Way complexes: Gem OB1 (Stacy & Thaddeus 1991), W3 (Digel et al. 1996), Cas A (Dame et al. 1987), and a complex in the outer Carina arm (Grabelsky et al. 1987).

## 3 Comparing GMCs in M31, M33 and the Milky Way

### 3.1 Spatial Filtering Experiments: Milky Way Clouds Moved to M31

For both interferometers and single dish telescopes, the observed brightness distribution is the convolution of true brightness with the instrument response function. This response is qualitatively different for the two types of telescopes. In general, interferometers are better at mapping small, compact structures than smooth, large angular-size structures. To evaluate the effect of the observational method on determination of cloud properties, we simulated interferometric observations of the Milky Way complexes at the distance of M31. Our simulations found that Gem OB1, W3 and Cas A complexes were recovered completely by the interferometer; their sizes, shapes and velocity widths were identical before and after the interferometric observations (see left panel in Fig. 2). In contrast, the complex in the outer Carina Arm suffered from a significant loss of flux (as much as $``$50%) but the complex itself did not change shape, size or velocity width (see right panel in Fig. 2).

The difference between the three complexes recovered completely and the Carina complex is that the Carina complex is $``$ 4$`\times `$ further away. At this distance, the 8$`.^{}`$8 beam of the 1.2m telescope is not able to provide a sufficiently high resolution map to mimic the true distribution of the molecular gas; the complex is smoothed by the coarse beam and consequently the flux is resolved out by the interferometer. To test whether this was indeed the case, we smoothed the Cas A complex and projected it to the distance of M31 and observed it with the interferometer; the result was the same as for the Carina complex: as much as 50% of the flux was resolved out. Thus we conclude that interferometers are excellent instruments for recovering typical Milky Way GMCs and interferometric M31 and M33 data may be compared to the single dish MW data.

### 3.2 Cloud Identification Experiments: What is a Molecular Cloud?

The techniques for identifying clouds can be divided broadly into two main methods with opposite philosophies. The first method defines clouds using an integrated intensity contour, ignoring all substructure (e.g., Dame et al. 1986; Sanders et al. 1985). The second method identifies as clouds all resolved intensity peaks which emphasizes the substructure in molecular emission (e.g, Gaussclump by Stutzki & Güsten 1990 or Clumpfind by Williams et al. 1994). The difference between these methods is illustrated in Figure 3. The advantage of the first method is that the results can be directly compared to several previous Galactic studies of GMCs. However this method is time consuming and subjective. In contrast, the second method can be automated, but it has a severe drawback in that it never identifies clouds larger than one or two resolution elements. This resolution dependence, while useful for studying the substructure in the molecular ISM, makes comparative studies of GMCs in different galaxies difficult. We applied both methods to the simulated Milky Way data, and the M31 and M33 datasets.

Method I. Using an integrated intensity contour: We defined M31 complexes using the integrated intensity contour method. These are the complexes A-F in Fig.1. Comparing these to those found in the Milky Way by Dame et al. (1987) using a similar technique111As a test, we also applied the same technique to the simulated Milky Way clouds to check that the derived properties of these complexes were consistent with GMCs in the Dame et al. survey, we find that the M31 complexes are very similar to the Milky Way complexes. In our data, M31 complexes range in sizes from 40–75 pc and have velocity widths 4.7–7.8 km s-1(FWHM), compared to the Milky Way complexes which ranged from 20–250 pc and 4-15 km s-1. The M31 clouds appear to be virialized, i.e. their virial masses are equal to their molecular masses within a factor of 2 (calculated with N(H2)/WCO= 3$`\times `$1020 cm-2 K-1 km-1 s). The M31 complexes have masses ranging from 0.8–5$`\times `$105$`M_{}`$. We find that the M31 complexes follow the same linewidth-size relationship as the Milky Way complexes (see Figure 4). Applying this method to the M33 data, we find that the Wilson & Scoville (1990) clouds increase in size because neighbouring clumps are now identified as a single complex; complexes thus defined have properties similar to those seen in M31 and Milky Way complexes.

Method II. Using Gaussclump: Since the simulated Milky Way data has similar resolution and noise characteristics as the M31 and M33 datasets, we compared all three using Gaussclump222We found that Gaussclump was better than Clumpfind in recovering clouds especially for low dynamic range data. We found that the derived properties (amplitude, velocity widths and sizes) of all three datasets were similar (figure not shown). But as noted earlier, these methods measure the substructure in molecular clouds rather than their overall properties, and therefore cannot be used to characterize global populations and properties of GMCs in a galaxy. Nonetheless, applying both methods leads to the same conclusion: the GMCs in all three galaxies are fairly similar.

SUMMARY: By simulating interferometric observations of Milky Way GMCs at Andromeda, we concluded that interferometers are excellent at recovering GMCs in M31 and M33. Then by using common cloud identification techniques, we found that GMCs in all three galaxies are similar to each other. Surveys much larger than ours will be necessary for determining global properties (e.g., mass distribution functions) of GMC populations.

## References

Blitz, L. (1993) in Protostars and Planets III, ed. Levy, E.H. & Lunine, J.I. p. 125-161

Combes, F. (1991) Annu. Rev. Astron. Astrophys. 29, 195

Dame, T.M., Elmegreen, B.G., Cohen, R.S., & Thaddeus, P. (1986) , Astrophys. J., 305892.

Dame, T.M., Ungerechts, H., Cohen, R.S., de Geus, E.J., Grenier, I.A., May, J., Murphy, D.C., Nyman, L.-A., Thaddeus, P. (1987) Astrophys. J. 322, 706.

Digel, S.W., Lyder, D.A., Philbrick, A.J., Puche, D., & Thaddeus, P. (1996) Astrophys. J. 458, 561.

Grabelsky, D.A., Cohen, R.S., Bronfman, L., Thaddeus, P., & May, J. (1987) Astrophys. J. 315, 122.

Sanders, D.B., Scoville, N.Z., Solomon,P.M. (1985) Astrophys. J. 289, 373.

Scoville, N.Z. (1990) in The Evolution of the Interstellar Medium, ed. L. Blitz, PASP, p. 49.

Stacy, J.A., Thaddeus, P. (1991) in ASP Conf. Ser. 16, Atoms, Ions, and Molecules: New Results in Spectral Line Astrophysics, eds. A. D. Haschick & P.T.P. Ho, ASP, p. 197

Stutzki, J., & Güsten, R. (1990) Astrophys. J. 356, 513.

Vogel, S.N., Boulanger, F., & Ball, R. (1987) Astrophys. J. 321, 145

Williams, J.P., de Geus, E.J., & Blitz, L. (1994) Astrophys. J. 428, 693.

Wilson, C.D., & Rudolph, A.L. (1993) Astrophys. J. 406, 477

Wilson, C.D., & Scoville, N. (1990) Astrophys. J. 363, 435.

Wilson, C.D., & Scoville, N. (1990) Astrophys. J. 385, 512.