Rollercoasters and Caterpillars
Therese Biedl Ahmad Biniaz Robert Cummings Anna Lubiw Florin Manea Dirk Nowotka Jeffrey Shallit
cs.CG cs.DM cs.DS

	Structural behaviour of supercritical fluids under confinement
    C.V.Krishnamurthy
    
==============================================================


		A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence, that is increasing or decreasing, has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as a polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three points. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ⌈ n/2⌉ for n>7, while the best known lower bound is Ω(n/log n). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(nlog n)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,…,n} can be computed in O(n loglog n) time.
		
		
		The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of
		the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-node top-view caterpillar on every set of 25/3n points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(n log n). We also show that such a drawing can be obtained in linear time, provided that the points are given in sorted order.
	
	
	

§ INTRODUCTION

	A run in a sequence of real numbers is a maximal contiguous subsequence that is increasing or decreasing. A rollercoaster is a sequence of real numbers such that every run has length at least three. For example the sequence (8,5,1,3,4,7,6,2) is
	a rollercoaster with runs (8,5,1), (1,3,4,7), (7,6,2), which have lengths 3, 4, 3, respectively. The sequence (8,5,1,7,6,2,3,4) is not a rollercoaster because its run (1,7) has length 2. 
	Given a sequence S=(s_1,s_2,…,s_n) of n distinct real numbers, the rollercoaster problem is to find a maximum-size set of indices i_1<i_2<… <i_k such that (s_i_1,s_i_2, …,s_i_k) is a rollercoaster. In other words, this problem asks for a longest rollercoaster in S, i.e., a longest subsequence of S that is a rollercoaster. 
	
	
	One can interpret S as a set P of points in the plane by translating each number s_i∈ S to a point p_i=(i,s_i). With this translation, a rollercoaster in S translates to a “rollercoaster” in P, which is a polygonal path whose vertices are points of P and such that every maximal sub-path, with positive- or negative-slope edges, has at least three points. See Figure <ref>(a). Conversely, for any point set in the plane, the y-coordinates of the points, ordered by their x-coordinates, forms a sequence of numbers. Therefore, any rollercoaster in P translates to a rollercoaster of the same length in S.
	
	
	
	The best known lower bound on the length of a longest rollercoaster is Ω(n/log n) due to Biedl  <cit.>. They conjectured that 
	
	
		
		Every sequence of n>7 distinct real numbers contains a rollercoaster of length at least ⌈ n/2 ⌉.
	
	
	Conjecture <ref> can be viewed as a statement about patterns in permutations,
	a topic with a long history, and the subject of much current research.  
	For example, the Eulerian polynomials, introduced by Euler in 1749,
	are the generating function for the number of descents in permutations.
	For surveys of recent work, see, for example,
	Linton et al. <cit.> and Kitaev <cit.>.  
	Specifically, Conjecture <ref> is related to the following seminal result of Erdős and Szekeres <cit.> in the sense that they prove the existence of an increasing or a decreasing subsequence of length at least √(n)+1 for n=ab+1, which is essentially a rollercoaster with one run.
	
		
		Every sequence of ab+1 distinct real numbers contains an increasing subsequence of length at least a+1 or a decreasing subsequence of length at least b+1.
	
	
	Hammersley <cit.> gave an elegant proof of the Erdős-Szekeres theorem that is short, simple, and based on the pigeonhole principle. The Erdős-Szekeres theorem also follows from the well-known decomposition of Dilworth (see <cit.>). The following is a restatement of Dilworth's decomposition for sequences of numbers.
	
	
		
		Any finite sequence S of distinct real numbers can be partitioned into k ascending sequences where k is the maximum length of a descending sequence in S.
	
	
	Besides its inherent interest, the study of rollercoasters is motivated by point-set embedding of caterpillars <cit.>. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. An ordered caterpillar is a caterpillar in which the cyclic order of edges incident to each vertex is specified. A top-view caterpillar is an ordered caterpillar where all vertices have degree 4 or 1 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. Planar orthogonal drawings of trees on a fixed set of points in the plane have been explored recently, see e.g., <cit.>; in these drawings every edge is drawn as an orthogonal path between two points, and the edges are non-intersecting. 
	A planar L-shaped drawing is a simple type of planar orthogonal drawing in which every edge is an orthogonal path of exactly two segments. Such a path is called an L-shaped edge. For example see the top-view caterpillar in Figure <ref>(b) together with a planar L-shaped drawing on a given point set.
	Biedl  <cit.> proved that every top-view caterpillar on n vertices has a planar L-shaped drawing on every set of O(n log n) points in the plane that is in general orthogonal position, meaning that no two points have the same x- or y-coordinate.
	
	

 §.§ Our Contributions

	In Section <ref> we study rollercoasters and prove Conjecture <ref>. In fact we prove something stronger: every sequence of n distinct numbers contains two rollercoasters of total length n. Our proof is constructive and yields a linear-time algorithm for computing such rollercoasters. We also extend our result to rollercoasters whose runs are of length at least k, for k>3. Then we present an O(n log n)-time algorithm for computing a longest rollercoaster, extending the classical algorithm for computing a longest increasing subsequence. This algorithm can be implemented in O(nloglog n) time if each number in the input sequence is an integer that fits in a constant number of memory words. Then we give an estimate on the number of permutations of {1,…,n} that are rollercoasters. In Section <ref> we prove, by using Conjecture <ref>, that every n-node top-view caterpillar has a planar L-shaped drawing on every set of 25/3n points in the plane in general orthogonal position.
	
	

§ ROLLERCOASTERS

	
	
	In this section we investigate lower bounds for the length of a longest rollercoaster in a sequence of numbers. We also study algorithmic aspects of computing such rollercoasters. First we prove Conjecture <ref>: any sequence of n distinct real numbers contains a rollercoaster of length at least ⌈ n/2⌉. Observe that the length 4 sequence (3,4,1,2) has no rollercoaster, so we will restrict to n⩾ 5 in the remainder of this section. Also, due to the following proposition we assume that n⩾ 8. 
	
	
		Every sequence of n∈{5,6,7} distinct real numbers contains a rollercoaster of length at least 3. This bound is tight in the worst case.
	
	
	r1.5in 
		
 
		
    < g r a p h i c s >
 
		
 
	
	 Proof. By applying Theorem <ref> with a=b=2 we get that every sequence of at least ab+1=5 distinct numbers contains an increasing or a decreasing subsequence of length at least a+1=3. This subsequence is a rollercoaster of length at least 3.
	For the tightness of this bound, consider the sequence (5, 2, 6, 3, 7, 1, 4), depicted in the adjacent figure. It has length 7 and its longest rollercoaster has length 3.
	

	
	
	We refer to a polygonal path as a chain. We define an ascent (resp., a descent) as an increasing (resp., a decreasing) sequence. We define a k-ascent (resp., a k-descent) as an ascent (resp., a descent) with at least k elements. We also use k-ascent and k-descent to refer to increasing and decreasing chains with at least k points, respectively. With this definition, a rollercoaster is a sequence in which every run is either a 3-ascent or a 3-descent. We refer to the rightmost run of a rollercoaster as its last run. 
	
	
	

 §.§ A Proof of Conjecture <ref>

	
	
	In this section we prove the following theorem, which is a restatement of Conjecture <ref>. Our proof is constructive, and yields a linear-time algorithm for finding such a rollercoaster.
	
	
		
		Every sequence of n⩾ 8 distinct real numbers contains a rollercoaster of length at least ⌈ n/2⌉; such a rollercoaster can be computed in linear time. The lower bound of ⌈ n/2⌉ is tight in the worst case.
	
	
	Consider a sequence with n ⩾ 8 distinct real numbers, and let P be its point-set translation with points p_1,…,p_n that are ordered from left to right. We define a pseudo-rollercoaster as a sequence in which every run is a 3-ascent or a 3-descent, except possibly the first run. We present an algorithm that computes two pseudo-rollercoasters R_1 and R_2 in P such that |R_1|+|R_2|⩾ n; the length of the longer one is at least  ⌈ n/2⌉. Then with a more involved proof we show how to extend this longer pseudo-rollercoaster to obtain a rollercoaster of length at least ⌈ n/2⌉; this will prove the lower bound.
	

  §.§.§ An Algorithm

	
	First we provide a high-level description of our algorithm as depicted in Figure <ref>. Our algorithm is iterative, and proceeds by sweeping the plane by a vertical line ℓ from left to right. We maintain the following invariant: 
	
	
	
		At the beginning of every iteration we have two pseudo-rollercoasters whose union is the set of all points to the left of ℓ and such that the last run of one of them is an ascent and the last run of the other one is a descent.
		Furthermore, these two last runs have a point in common.
	
	
	
	
	During every iteration we move ℓ forward and try to extend the current pseudo-rollercoas­ters. If this is not immediately possible with the next point, then we move ℓ farther and stop as soon as we are able to split all the new points into two chains that can be appended to the current pseudo-rollercoasters to obtain two new pseudo-rollercoasters that satisfy the invariant. See Figure <ref>. 
	
	Now we present our iterative algorithm in detail. 
	
	

	The First Iteration: 
	We take the leftmost point p_1, and initialize each of the two pseudo-rollercoasters by p_1 alone. We may consider one of the pseudo-rollercoasters to end in an ascent and the other pseudo-rollercoaster to end in a descent. 
	The two runs have a point in common.
	
	

	An Intermediate Iteration: 
	By the above invariant we have two pseudo-rollercoasters R_A and R_D whose union is the set of all points to the left of ℓ and such that the last run of one of them, say R_A, is an ascent and the last run of R_D is a descent. 
	Furthermore, the last run of R_A and the last run of R_D have a point in common.
	During the current iteration we make sure that every swept point will be added to R_A or R_D or both. We also make sure that at the end of this iteration the invariant will hold for the next iteration. Let a and d denote the rightmost points of R_A and R_D, respectively; see Figure <ref>. 
	Let p_i be the first point to the right of ℓ. If p_i is above a, we add p_i to R_A to complete this iteration. Similarly, if p_i is below d, we add p_i to R_D to complete this iteration. In either case we get two pseudo-rollercoasters that satisfy the invariant for the next iteration. Thus we may assume that p_i lies below a and above d. In particular, this means that a lies above d.  
	
	Consider the next point p_i+1. 
	(If there is no such point, go to the last iteration.)
	Suppose without loss of generality that p_i+1 lies above p_i as depicted in Figure <ref>. Then d, p_i, p_i+1 forms a 3-ascent. Continue considering points p_i+2, …, p_k until for the first time, there is a 3-descent in a, p_i, …, p_k. 
	In other words, k is the smallest index for which a, p_i, …, p_k contains a descending chain of length 3.
	(If we run out of points before finding a 3-descent, then go to the last iteration.) 
	
	
		Let this descending chain be p_k”, p_k', p_k with p_k' as far to the right as possible, i.e., k' as large as possible, and subject to that, with k” as large as possible. 
		Observe that k” i since i+1 would be a better choice. It may happen that a = p_k” and i = k'.
	
	
	
	
	Without p_k there is no descending chain of length 3. Thus the longest descending chain has two points, and by Theorem <ref>, the sequence P'=a, p_i, p_i+1, …, p_k-1 is the union of two ascending chains. 
	We give an algorithm to find two such chains A_1 and A_2 with A_1 starting at a and A_2 starting at p_i.   
		The algorithm also finds the 3-descent ending with p_k.  For every point q∈ A_2 we define its A_1-predecessor to be the rightmost point of A_1 that is to the left of q. We denote the A_1-predecessor of q by qA_1.
		
		The algorithm is as follows: While moving ℓ forward, we denote by r_1 and r_2 the rightmost points of A_1 and A_2, respectively; at the beginning r_1=a, r_2=p_i, and p_iA_1=a. Let p be the next point to be considered. If p is above r_1 then we add p to A_1. If p is below r_1 and above r_2, then we add p to A_2 and set pA_1=r_1. If p is below r_2, then we find our desired first 3-descent formed by (in backwards order) p_k=p, p_k'=r_2, and p_k”=r_2A_1.  See Figure <ref>.
		This algorithm runs in time O(k-i), which is proportional to the number of swept points.
		
		We add point d to the start of chain A_2.  
		The resulting chains A_1 and A_2 are shaded in Figure <ref>.
		Observe that A_2 ends at p_k'. 
		Also, all points of P' that are to the right of p_k' (if there are any) belong to A_1, and  lie to the right of p_k”, and form an ascending chain. Let A”_1 be this ascending chain. Let A'_1 be the sub-chain of A_1 up to p_k”; see Figure <ref>. 
		Now we form one pseudo-rollercoaster (shown in red) consisting of  R_A followed by A'_1 and then by the descending chain p_k”,p_k',p_k.  
		We form another pseudo-rollercoaster (shown in blue) consisting of R_D followed by A_2 and then by A”_1. 
		We need to verify that the ascending chain added after d has length at least 3.  
		This chain contains d, p_i and p_k'. This gives a chain of length at least 3 unless k' = i, but in this case p_k” = a, so p_i+1 is part of A”_1 and consequently part of this ascending chain.
		Thus we have constructed two longer pseudo-rollercoasters whose union is the set of all points up to point p_k, one ending with a 3-ascent and one with a 3-descent and such that the last two runs share the point p_k'.
		Figure <ref>(a) shows an intermediate iteration.
	
	
	
		Of necessity, one of these starts with a and the other with p_i. Let A_1 denote the chain that contains a and A_2 denote the other one. We can add d to the beginning of A_2. These chains are shaded in Figure <ref>. For every point q∈ A_2 we define its A_1-predecessor to be the rightmost point of A_1 that is to the left of q. We denote the A_1-predecessor of q by qA_1.
		
		
		First we show how to compute A_1 and A_2 in O(k-i) time, which is proportional to the number of swept points. 
		Within the same time we compute the A_1-predecessor of every point q∈ A_2. While moving ℓ forward, we denote by r_1 and r_2 the rightmost points of A_1 and A_2, respectively; at the beginning r_1=a, r_2=p_i, and p_iA_1=a. Let p be the next point to be considered. If p is above r_1 then we add p to A_1. If p is below r_1 and above r_2, then we add p to A_2 and set pA_1=r_1. If p is below r_2, then we find our desired first 3-descent with p_k=p, p_k'=r_2, and p_k”=r_2A_1. 
		
		In the above construction, A_2 ends at p_k'. Also, all points of P' that are to the right of p_k' (if there are any) belong to A_1, also lie to the right of p_k”, and form an ascending chain. Let A”_1 be this ascending chain. Let A'_1 be the sub-chain of A_1 up to p_k”; see Figure <ref>. Now we form one pseudo-rollercoaster by R_A followed by A'_1 and then by the descending chain p_k”,p_k',p_k. We obtain another pseudo-rollercoaster by R_D followed by A_2 and then by A”_1. We need to verify that the ascending chain added after d has length at least 3.  
		This chain contains d, p_i and p_k” or p_k'. Since k” i, this gives a chain of length at least 3 unless k' = i, but in this case p_i+1 is part of A”_1 and consequently part of this ascending chain.
		Thus we have constructed two longer pseudo-rollercoasters whose union is the set of all points up to point p_k, one ending with a 3-ascent and one with a 3-descent.
		Observe that these two pseudo-rollercoasters intersect in p_k'. Figure <ref>(a) shows an intermediate iteration.
	
	
	
	

	The Last Iteration: 
	If there are no points left, then we terminate the algorithm. Otherwise, let p_i be the first point to the right of ℓ. Let a and d be the endpoints of the two pseudo-rollercoasters obtained so far, such that a is the endpoint of an ascent and d is the endpoint of a descent.  
	Notice that p_i is below a and above d, because otherwise this iteration would be an intermediate one. For the same reason, the remaining points p_i,…, p_n do not contain a 3-ascent together with a 3-descent. If p_i is the last point, i.e., i=n, then we discard this point and terminate this iteration. Assume that i≠ n, and suppose without loss of generality that the next point p_i+1 lies above p_i. In this setting, by Theorem <ref> and as described in an intermediate iteration, with the remaining points, we can get two ascending chains A_1 and A_2 such that A_2 contains at least two points. By connecting A_1 to a and A_2 to d we get two pseudo-rollercoasters whose union is all the points (in this iteration we do not need to maintain the invariant).  
	
	
	
	
	

	Final Refinement: 
	At the end of algorithm, we obtain two pseudo-rollercoasters R_1 and R_2 that share p_1 and such that their union contains all points of P, except possibly p_n. Thus, |R_1|+|R_2|⩾ n, and the length of the longer one is at least ⌈n/2⌉. 
	
	Recall that every run of pseudo-rollercoasters R_1 and R_2 is a 3-ascent or a 3-descent, except possibly the first run. If the first run of R_1 (resp., R_2) contains only two points, then we remove p_1 to obtain a rollercoaster ℛ_1 (resp., ℛ_2). Therefore, we obtain two rollercoasters whose union contains all points, except possibly p_1 and p_n. 
	

		Let R_1 be the pseudo-rollercoaster that—in the first iteration—was assumed to have an ascent ending in p_1, and let R_2 be the one that was assumed to have a descent ending in p_1.
		Notice that if the first run of R_1 is decreasing, then as described in an intermediate iteration, this run contains at least three points p_k”, p_k', and p_k (with p_k”=a=p_1). In this case we do not remove p_1 from R_1. Also if the first run of R_2 is increasing, then it contains at least three points p_1=d, p_i, and p_k' or p_k” or p_i+1. In this case we do not remove p_1 from R_2. Therefore, p_1 will be removed from both R_1 and R_2 if and only if the first run of R_1 is an increasing chain with two points and the first run of R_2 is a decreasing chain with two points. This configuration is depicted in Figure <ref>(b).
	
	
	This is the end of our algorithm. In the next section we analyze the length of the resulting rollercoaster, the tightness of the claimed lower bound, and the running time of the algorithm. 
	
	

  §.§.§ Length and Running-Time Analysis

	
	Our algorithm computes two rollercoasters ℛ_1 and ℛ_2 consisting of all points of P, except possibly p_1 and p_n. Thus, the total length of these rollercoasters is at least n-2, and the length of the longer one is at least ⌈n-2/2⌉. In Appendix <ref> we improve this bound to ⌈n/2⌉ by revisiting the first and last iterations of our algorithm with some case analysis. 
	
	We note that there are point sets, with n points, for which every rollercoaster of length at least n/4+3 does not contain any of p_1 and p_n; see e.g., the point set in Figure <ref>(b). This example shows also the tightness of the ⌈ n/2 ⌉ lower bound on the length of a longest rollercoaster; the blue rollercoaster is a longest possible and contains ⌈ n/2⌉ points. By removing the point p_n-1 an example for odd n is obtained.
	
	To verify the running time, notice that the first iteration and final refinement take constant time, and the last iteration is essentially similar to an intermediate iteration. As described in an intermediate iteration the time complexity to find a 3-ascent and a 3-descent for the first time together with the time complexity to compute chains A'_1, A”_1, and A_2 is O(k-i), which is linear in the number of swept points p_i,…,p_k. Based on this and the fact that every point is considered only in one iteration, our algorithm runs in O(n) time.
	
	

 §.§ An Extension

	
	In this section we extend our result to k-rollercoasters. A k-rollercoaster is a sequence of real numbers in which every run is either a k-ascent or a k-descent. 
	
	
		
		Let k⩾ 4 be an integer. Then every sequence of n⩾ (k-1)^2+1 distinct real numbers contains a k-rollercoaster of length at least n/2(k-1)-3k/2.
	
	
		Our proof follows the same iterative approach of the proof of Theorem <ref>. Consider a sequence of n distinct real numbers and its point-set translation p_1,…,p_n.
		We sweep the plane by a line ℓ, and maintain two k-rollercoasters R_A and R_D to the left of ℓ such that the last run of R_A is an ascent and the last run of R_D is descent. In each iteration we move ℓ forward and stop as soon as we see a k-ascent A and a k-descent D. Then we attach D to R_A, and A to R_D. To achieve the claimed lower bound, we make sure that the total length of A and D is at least 1/(k-1) times the number of swept points. 
		
		Consider an intermediate iteration. Let m be the number of swept points in this iteration and let P'=(p_i,p_i+1…,p_i+m-2, p_i+m-1) be the sequence of these points. Our strategy for stopping ℓ ensures that P' contains a k-ascent and a k-descent, while P”=(p_i,…,p_i+m-2) may contain only one of them but not both. Without loss of generality assume that P” does not contain a k-descent. Let α be the integer for which
		
    (α-1)(k-1)<m-1⩽α (k-1).

		
		The left-hand side of Inequality (<ref>) implies that P” has at least (α-1)(k-1)+1 points. Having this and our assumption that P” does not contain a k-descent, Theorem <ref> implies that P” contains an increasing subsequence of length at least α. We take the longest increasing and the longest decreasing subsequences in P' as A and D, respectively. Observe that |A|⩾max{k,α} and |D|=k. This and the right-hand side of Inequality (<ref>) imply that 
		
    |A|+|D|⩾α+k⩾m-1/k-1+k> m/k-1,

		which means that the total length of A and D is at least 1/(k-1) times the number of swept points. 
		In the last iteration if we sweep at most (k-1)^2 points then we discard all of them. But if we sweep more than (k-1)^2 points then by an argument similar to the one above there exists an integer α, with α⩾ m/(k-1), for which we get either an α-ascent or an α-descent, which contains at least 1/(k-1) fraction of the swept points.
		
		The first iteration is similar to the one in the proof of Theorem <ref>: we assume the existence of an ascent and a descent that end at the first point. At the end of algorithm if the first run of any of R_A and R_D contains k' points, for some k'<k, then by removing k'-1(⩽ k-2) points from its first run we get a valid k-rollercoaster. The total length of the resulting two k-rollercoasters is
		
    |R_A|+|R_D|⩾n-(k-1)^2/k-1 - 2(k-2),

		where the length of the longer one is at least 
    n-(k-1)^2/2(k-1) - (k-2)>n/2(k-1)-3(k-1)/2.

	
	
	

 §.§ Algorithms for a Longest Rollercoaster

	
	
	r2in 
		
 
		
    < g r a p h i c s >
 
		ℛ_1 and ℛ_2 are the two rollercoaster returned by our algorithm while the longest rollercoaster is ℛ.
		
 
	
	In this section we study algorithmic aspects of computing a longest rollercoaster in a given sequence S of n distinct real numbers. By Theorem <ref> we can compute a rollercoaster of length at least ⌈ n/2 ⌉ in O(n) time. However this rollercoaster may not necessarily be a longest one. If we run our algorithm of Section <ref> on the point set in the figure to the right, then it returns two rollercoasters ℛ_1 and ℛ_2 each of length at most ⌈n/2⌉ while the longest rollercoaster ℛ has length n. In this section, first we adapt the existing O(nlog n)-time algorithm for computing a longest increasing subsequence in S to compute a longest rollercoaster in S within the same time bound. Then we show that if S is a permutation of {1,…,n}, then we can compute a longest rollercoaster in O(nloglog n) time.  
	
	First we recall Fredman's version of the O(nlog n)-time algorithm for computing a longest increasing subsequence <cit.>; for more information about longest increasing subsequence, see Romik <cit.>. We maintain an array R[i], which initially has R[1]=S[1] and is empty otherwise. Then as i proceeds from 2 to n, we find the largest l for which R[l]<S[i], and set R[l+1]=S[i]. This insertion ensures that every element R[l] stores the smallest element of S[1..i] in which an increasing subsequence of length l ends. After all elements of S have been processed, the index of the last non-empty element of R is the largest length of an increasing sequence; the corresponding sequence can also be retrieved from R. Notice that R is always sorted during the above process. So, the proper location of S[i] in R can be computed in O(log n) time by a predecessor search, which can be implemented as a binary search. Therefore, this algorithm runs in O(nlog n) time.  
	
	To compute a longest rollercoaster we need to extend this approach. We maintain six arrays R(w,h) with w∈{,} and h∈{2,3_+, 3_+^'} where  stands for “increasing”,  stands for “decreasing”, and 3_+ stands for any integer that is at least 3. We define a w-h-rollercoaster to be a rollercoaster whose last run has h points and is increasing if w= and decreasing if w=. We insert S[i] into arrays R(,h) such that after this insertion the following hold:
	
	
		
  * R(,2)[l] stores the smallest element of S[1..i] in which an -2-rollercoaster of length l ends. R(,2)[l] stores the largest element of S[1..i] in which a -2-rollercoaster of length l ends.
		
  * R(,3_+)[l] stores the smallest element of S[1..i] in which an -3_+-rollercoaster of length l ends. R(,3_+)[l] stores the largest element of S[1..i] in which an -3_+-rollercoaster of length l ends.
		
  * R(,3_+^')[l] stores the largest element of S[1..i] in which an -3_+-rollercoaster of length l ends. R(,3_+^')[l] stores the smallest element of S[1..i] in which a -3_+-rollercoaster of length l ends. These arrays will be used when the last run of the current rollercoaster changes from an ascent to a descent, and vice versa. 
	
	
	We insert S[i] into arrays R(,h) so that analogous constraints hold. To achieve these constraints we insert S[i] as follows:
	
	
		
  * R(,2): Find the largest index l such that R(,3_+^')[l]<S[i]. If S[i]<R(,2)[l+1] then update R(,2)[l+1]=S[i].
		
		
  * R(,3_+): Find the largest indices l_1 and l_2 such that R(,2)[l_1]<S[i] and R(,3_+)[l_2] <S[i]. Let l=max{l_1,l_2}. If S[i]<R(,3_+)[l+1] then update R(,3_+)[l+1]=S[i].
		
		
  * R(,3_+^'): Find the largest index l_1 and l_2 such that R(,2)[l_1] <S[i] and R(,3_+^')[l_2] <S[i]. Let l=max{l_1,l_2}. If S[i]>R(,3_+^')[l+1] then update R(,3_+^')[l+1]=S[i].
		
		
  * The arrays R(,h) are updated in a similar fashion.
	
	
	Since our arrays R(w,h) are not necessarily sorted, we cannot perform a predecessor search to find proper locations of S[i]. To insert S[i] we need to find the largest index l such that R(w,h)[l] is smaller (or, alternatively, larger) than S[i] for some w and h, and also need to update contents of these arrays. Thereby, if A is an R(w,h) array, we need to perform the following two operations on A:
	
	
		
  * (A,S[i]): Find the largest index l such that A[l]>S[i] (or A[l]<S[i]). 
		
  * (A,l,S[i]): Set A[l]=S[i].
	
	
	We implement each R(w,h) as a Fenwick tree <cit.>, which supports  and  in O(log n) time. Thus, the total running time of our algorithm is O(n log n). After all elements of S have been processed, the largest length of a rollercoaster is the largest value l for which R(w,3_+)[l] or R(w,3_+^')[l] is not empty; the corresponding rollercoaster can also be retrieved from arrays R(w,h), by keeping the history of the way the elements of these arrays were computed, and then rolling back the computation. 
	

	
	A Longest Rollercoaster in Permutations:
	Here we consider a special case where our input sequence S consists of n distinct integers, each of which can be represented using at most c memory words for some constant c⩾ 1, in a RAM model with logarithmic word size. In linear time, we can sort S, using Radix Sort, and then hash it to a permutation of {1,…,n}. This reduces the problem to finding a longest rollercoaster in a permutation of {1,…,n}. The longest increasing subsequence of such a sequence can be computed in O(n loglog n) time by using a van Emde Boas tree <cit.>, which supports predecessor search and updates in O(loglog n) time.[We note that a longest increasing subsequence of a permutation can also be computed in O(nloglog k) time (see <cit.>) where k is the largest length of an increasing sequence, which is Ω(√(n)). However, in our case, the largest length of a rollercoaster is Ω(n).] To compute a longest rollercoaster in the same time, we need a data structures that supports  and  in permutations in O(loglog n) time. In Appendix <ref> we show how to obtain such a data structure by using van Emde Boas trees combined with some other structures.
	
	
		Let A be an array with n elements from the set {0,1,…,n} such that each non-zero number occurs at most once in A. We can construct, in linear time, a data structure that performs  and  operations in O(loglog n) amortized time.
	
	
	With Lemma <ref> in hand, we can compute a longest rollercoaster in S in O(n loglog n) time. We note that this algorithm can also compute a longest increasing subsequence by maintaining only the array R(,3_+). 
	
	

 §.§ Counting Rollercoaster Permutations

	
	In this section we estimate the number r(n) of permutations of
	{ 1,2, …, n } that are rollercoasters.  A brief table
	follows:
	
	

		
		
			n     1     2     3     4     5     6     7     8     9     10     11     12     13     14 

			r(n)     1     0     2     2     14     42     244     1208     7930     52710     40580     3310702    29742388     285103536 
		
	

	
	This is sequence A277556 in the On-Line Encyclopedia
		of Integer Sequences <cit.>.
	
	The first step is to rephrase the condition that a permutation is a 
	rollercoaster in the language of ascents and descents.  Given a
	length-n permutation π = π_1 π_2 ⋯π_n, its 
	descent word u(π) is defined to be u_1 u_2 ⋯ u_n-1
	where u_i =  a if π_i < π_i+1 and b otherwise.
	The set of all descent words for rollercoaster permutations is
	therefore given by the expression
	
    ( bbb^* + ϵ)( aaa^*   bbb^*)( aaa^* + ϵ),

	which specifies that every increasing run and every decreasing run must contains at least three elements. Since this description is a regular expression,
	one can, in principle,
	obtain the asymptotic behavior of r(n) using the techniques
	of <cit.>, but the calculations appear to be formidable.
	
	Instead, 
	we follow the approach of Ehrenborg and Jung <cit.>.
	This is based on specifying sets of permutations through pattern avoidance.
	We say a word w avoids a set of
	words S if no contiguous subword of w
	belongs to S.
	Although rollercoasters are not specifiable in terms of a finite
	set of avoidable patterns, they “almost are”.  Consider the
	patterns { aba,  bab}.   Every descent word of a
	rollercoaster must avoid both these patterns, and every word avoiding
	these patterns that also
	begins and ends with either aa or bb
	is the descent word of some rollercoaster.   Let s(n) be the number
	of permutations of length n whose descent word avoids 
	{ aba,  bab}.  Then r(n) = Θ(s(n)).
	From <cit.> we know that
	s(n)∼ c · n! ·λ^n-3
	where λ≐ 0.6869765032⋯ is the root of a
	certain equation.  It follows that
	r(n) ∼ c' · n! ·λ^n-3
	where c' is a constant, approximately 0.204.
	
	


§ CATERPILLARS



In this section we study the problem of drawing a top-view caterpillar, with L-shaped edges, on a set of points in the plane that is in general orthogonal position. Recall that a top-view caterpillar is an ordered caterpillar of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine; see Figure <ref>(b) for an example.
The best known upper bound on the number of required points for a planar L-shaped drawing of every n-vertex top-view caterpillar is O(nlog n); this bound is due to Biedl  <cit.>. 
We use Theorem <ref> and improve this bound to 25/3n+O(1).

In every planar L-shaped drawing of a top-view caterpillar, every node of the spine, except for the two endpoints, must have its two incident spine edges aligned either horizontally or vertically. Such a drawing of the spine (which is essentially a path) is called a straight-through drawing. It has been proved in <cit.> that every n-vertex path has an x-monotone straight-through drawing on any set of at least c· n log n points, for some constant c. The following theorem improves this bound. 


	
	Any path of n vertices has an x-monotone straight-through drawing on any set of at least 5/2n points in the plane that is in general orthogonal position.


	Observe that any n-vertex path has an x-monotone straight-through drawing on an n-vertex rollercoaster in which every run has odd length, except possibly the first and last runs; see e.g., the black path in Figure <ref> that is drawn on the rollercoaster consisting of black vertices. Therefore, to prove this theorem it suffices to show the existence of an n-vertex rollercoaster in which every run has odd length. By Theorem <ref>, every set of 5n/2 points contains a rollercoaster R of length at least 5n/4. To obtain a rollercoaster with odd-length runs, we traverse R from left to right and iterate the following process. In every iteration we take two consecutive runs of R, say r_1 and r_2. If both r_1 and r_2 have odd lengths, we do nothing. If both have even lengths, then we remove the point that is shared between them. If one of them, say r_1, has even length and r_2 has odd length, then we remove a point from the middle of r_1. After the last iteration we obtain a rollercoaster R' in which every run has odd length. Since every odd-length run has at least three points, every even-length run has at least four points, and every two consecutive runs share a point, it turns out that, in the worst case, we remove one point from every five points of R. Thus, in total we remove at most one-fifth of points of R. Therefore, the length of R' is at least 5n/4-1/5·5n/4=n. 


We use Theorem <ref> in the proof of our main result in this section:


	
	Any top-view caterpillar of n vertices has a planar L-shaped drawing on any set of 25/3n+O(1) points in the plane that is in general orthogonal position.


r2.5in 
	
 
	
    < g r a p h i c s >
 
		
 
	An x-monotone straight-through drawing of an n'-vertex path; red points are reserved.
	
	
 

Proof.
We describe an algorithm that obtains such a drawing on any given set P with 25n/3 points in general orthogonal position (the O(1) term is used to deal with the first an last points of the spine and will mostly be ignored during this argument). 
Partition P, by vertical lines, into 5n/3 sets each of them containing five points. We call every such set a 5-set. Take the mid-point (with respect to their y-coordinates) of every 5-set, and let P' be the set of these 5n/3 points. We call the untaken four points of a 5-set reserved points. Set n'=2n/3. As in the proof of Theorem <ref>, we obtain an x-monotone straight-through drawing of an n'-vertex path on points of P'; let δ denote this drawing. Let s_1,…,s_n' denote the points of δ ordered from left to right; see Figure <ref>. 
For every i∈{1,…,n'} we denote the reserved points of the 5-set containing s_i by a_i,b_i,c_i,d_i from top to bottom.

We use δ for the spine of our caterpillar, and use reserved points to draw its leaves. We draw the leaves iteratively by traversing the vertices of δ from left to right. In each iteration we attach four leaves to δ by L-Shaped edges. Every iteration starts at a point s_i on a vertical segment of δ. We maintain this invariant that “at the beginning of every iteration, the drawing of the portion of the caterpillar that is to the left of the vertical line through s_i is a valid planar L-shaped drawing”. Since the first run of (the rollercoaster corresponding to) δ has an odd number of points, the edge of the spine incident to s_1 is aligned horizontally. Thus, s_2 is on a vertical segment of δ. By a suitable reflection assume that s_2 is above s_1. We connect s_2 by an L-shaped edge to one of a_1 and b_1; see Figure <ref>. Notice that the invariant holds at s_2. Now we describe, in detail, one iteration of our algorithm with starting point s_i for which the invariant holds. 	
By a suitable reflection assume that the next point s_i+1 is above s_i. We consider two cases depending on whether or not s_i+2 is below s_i+1.


	
  * s_i+2 is below s_i+1:		
	This case is depicted in Figure <ref>(a). We update δ by replacing s_i+1 with b_i+1 and then connecting both s_i and s_i+2 to b_i+1. Then we connect a_i+1 and s_i+1, as two leaves, to this new spine vertex b_i+1. Recall that c_i+1 and d_i+1 are below s_i+1. Finally, we connect the leftmost of c_i+1 and d_i+1 to s_i and the other one to s_i+2. Then we proceed to the next iteration, starting with s_i+2, for which the invariant holds.
	
	
	
	
  * s_i+2 is above s_i+1:		
	In this case s_i+3 lies above s_i+2. Now we consider s_i+4 and depending on whether or not it is below s_i+3 we have two cases.
	
		
  * s_i+4 is below s_i+3:			
		As depicted in Figure <ref>(b) we remove s_i+1 and s_i+2 from δ and connect s_i to s_i+3. Now, we handle this case as in the previous case where s_i+3 and s_i+4 play the roles of s_i+1 and s_i+2, respectively. Notice that among four spine vertices s_i+1, s_i+2, s_i+3, s_i+4, we used s_i+3, s_i+4.
		
		
  * s_i+4 is above s_i+3:			
		This case is depicted in Figure <ref>. We remove s_i+1 and s_i+3 from δ, and then connect s_i and s_i+4 to s_i+2. Then we connect, as leaves, s_i+1 to s_i, and s_i+3 to s_i+4. Recall from the initial partitioning that b_i+2 and c_i+2 are in the vertical strip that contains s_i+2; this strip is to the right of s_i+1 and to the left of s_i+3. Thus, by connecting b_i+2 and c_i+2 to s_i+2 we obtain a valid planar L-shaped drawing. Then we proceed to the next iteration, starting with s_i+4, for which the invariant holds. Notice that among four spine vertices s_i+1, s_i+2, s_i+3, s_i+4, we used s_i+2, s_i+4.
	
	
	
	


This is the end of iteration. In every iteration we used at least half of the scanned vertices of δ. Since δ has n' vertices at the beginning, at the end of this algorithm we obtain a planar L-shaped drawing of a top-view caterpillar with n'/2=n/3 vertices on its spine. Since the spine of every n-vertex top-view caterpillar has n/3+O(1) vertices, our claim follows.





	
	Any path of n vertices has an x-monotone straight-through drawing on any set of at least 3n-3 points in the plane that is in general orthogonal position.


	Fix an arbitrary set of 3n-3 points.
	As in the proof of Theorem <ref>, 
	find two pseudo-rollercoasters that together cover all but the last point
	and that both contain the first point.
	Append the last point to both sets; we hence obtain two subsequences 
	R_1,R_2 with |R_1|+|R_2|≥ 3n-1 and for which all but the first and
	last run have length at least 3.  
	
	We may assume |R_1|≥32n-12, and will find the 
	straight-through
	drawing within it.  To do so, consider any run r of R_1 that is neither the
	first nor the last run, and that has even length (hence length at least 4).
	By removing from r one point that is not shared with an adjacent run,
	we turn it into a run of odd length.  Let R' be the subsequence
	that results after applying this to every such run of R_1; then R'
	satisfies that every run except the first and last one has odd length.  
	Observe that we can find an x-monotone straight-through drawing of length 
	|R'| on this, see e.g. the black path in Figure <ref> that is 
	drawn on the black points. 
	
	It remains to argue that |R'|≥ n.  Let r_1,…,r_ℓ be the
	runs of R_1, and assign to each run r_i all but the last point of r_i
	(the last point of r_i is counted with r_i+1, or not counted at all
	if i=ℓ).  Therefore
	|r_1|+…+|r_ℓ|=|R_1|-1≥32n-32. 
	For each r_i with 2≤ i≤ℓ-1, we remove a point
	only if |r_i|≥ 3, hence we keep at least 23|r_i| points.
	Therefore |R'|≥ |r_1|+|r_ℓ|+∑_2≤ i≤ℓ-123|r_i|
	≥∑_1≤ i≤ℓ23|r_i|
	+ 13(|r_1|+|r_ℓ|) ≥23· (32n-32)+ 13(2+1)=n as desired.
	
	Therefore, to prove this theorem it suffices to show the existence of an n-vertex rollercoaster in which every run has odd length. By 
	Theorem <ref>, 
	every set of 52n points contains a rollercoaster R of length at least 5n4. To obtain a rollercoaster with odd-length runs, we traverse R from left to right and iterate the following process. In every iteration we take two consecutive runs of R, say r_1 and r_2. If both r_1 and r_2 have odd lengths, we do nothing. If both have even lengths, then we remove the point that is shared between them. If one of them, say r_1, has even length and r_2 has odd length, then we remove a point from the middle of r_1. After the last iteration we obtain a rollercoaster R' in which every run has odd length. Since every odd-length run has at least three points, every even-length run has at least four points, and every two consecutive runs share a point, it turns out that, in the worst case, we remove one point from every five points of R. Thus, in total we remove at most one-fifth of points of R. Therefore, the length of R' is at least 5n4-15·5n4=n. 
	

To draw top-view caterpillars, we essentially use 
Theorem <ref> and place the spine on
the resulting straight-through x-monotone path. 
But we will get a slightly better factor
if we analyze the number of points directly. 


	
	
	Any top-view caterpillar of n vertices has a planar L-shaped drawing on any set of 253(n+4) points in the plane that is in general orthogonal position.


r2.5in 
	
 
	
    < g r a p h i c s >
 
	An x-monotone straight-through drawing of an n'-vertex path. Red (lighter shade) points are reserved.
	
	
 

Proof.
Fix any 253(n+4) points P in general orthogonal position. 
Partition P, by vertical lines, 
into 53(n+4) sets, each of them containing five points. We call every such set a 5-set. Let P' be the set of the mid-points (with respect to 
y-coordinates) of every 5-set.  
We have |P'|≥53(n+4),
so by Theorem <ref> it 
contains a rollercoaster R of length at least 56(n+4). 

Let s_1,…,s_N  (for N≥56(n+4)) be the points of R, 
ordered from left to right.
For every i∈{1,…,N}, consider the 5-set containing s_i
and let its other points be
a_i,b_i,c_i,d_i from top to bottom; we call these the reserved points.
The main idea is to draw the spine of the caterpillar along R and the leaves at reserved points, though we will deviate from this
occasionally.
Let the spine consist of vertices v_1,v_2,…,v_ℓ, where v_1 and v_ℓ are leaves while v_2,v_3,… are vertices of degree 4.  
We process the vertices in order along the spine, and maintain the following invariant:


	At time k≥ 1, vertex v_2k is drawn on a point s_i that is in the middle of a run of R.  Edge (v_2k,v_2k-1)
	attaches vertically at v_2k.  All vertices v_1,…,v_2k-1, all their incident leaves, and one incident leaf of v_2k are
	drawn on points to the left of s_i.


To initiate this process, we draw v_1 on s_1, v_2 on s_2, and one leaf incident to s_2 on b_1.  See 
Figure <ref>. Clearly the invariant holds for v_2.   Now assume that vertex v_2k has been placed
at s_i, and we want to place v_2k+1 and v_2k+2 next.  We know that s_i is in the middle of some run of
R; up to symmetry we may assume that it is an ascending run.  Let s_j be the last point of this run of R;
by the invariant j>i.  We distinguish cases:


Case 1: j≤ i+4.
See Figure <ref>(a).   
We will completely ignore the 5-sets containing s_i+1,…,s_j-1. 
Recall that there are two reserved points a_j and b_j above s_j.  We place v_2k+1 at b_j and v_2k+2
at s_j+1.  We connect leaves as follows:  The leaves incident to v_2k+1 are placed at a_j and s_j.
To place one leaf each incident to v_2k and v_2k+2, we use the two points c_j and d_j, using the one
farther left for v_2k.  Clearly the invariant holds.

Observe that there are at most five 5-sets (corresponding to s_i+1,…,s_j+1) that were parsed, and we have used two for placing spine-vertices.
Therefore, we have used at least 25th of the parsed 5-sets. 



Case 2: j> i+4.
See Figure <ref>(b). 
We ignore the reserved points corresponding to s_i+1 and s_i+3. 
We place v_2k+1 at s_i+2 and v_2k+2 at s_i+4.  Note that by case-assumption s_i+4 is not
the end of the run, so this satisfies the invariant. 
We connect, as leaves, s_i+1 to v_2k (at s_i), and s_i+3 to v_2k+2 (at s_i+4). 
The two leaves of v_2k+1 can be placed in the 5-set of s_i+2.
We have used four 5-sets and placed two spine-vertices, and have therefore used half of the parsed 5-sets.




This is the end of one iteration. In every iteration, we have used at least 25th of the parsed 5-sets.
Since there were 56(n+4) 5-sets, we hence can place 13(n+4) spine-vertices.
Since the spine of every n-vertex top-view caterpillar has 13(n+4) vertices, our claim follows.




The algorithm in the proof of Theorem <ref> runs in linear time, provided that the input points are given in sorted order, since we can find the rollercoaster in linear time and then do one scan of the points.





abbrv






§ DETAILED LENGTH ANALYSIS


Let ℛ_1 and ℛ_2 be the two rollercoasters computed by our algorithm. Recall that ℛ_1∪ℛ_2 contains all points of P, except possibly p_1 and p_n which might be discarded in the first and last iterations, respectively. Thus the total length of ℛ_1 and ℛ_2 is at least n-2, and the length of the longer one is at least ⌈n-2/2⌉. 
To get the length ⌈n/2⌉ we revisit the first and last iterations; this includes some case analysis. For brevity, we call a rollercoaster of length at least ⌈n/2⌉ a suitable rollercoaster. 

If one of ℛ_1 and ℛ_2 is empty, then the other one is suitable. Assume that none of them is empty, and thus, each contains at least three points (because they are valid rollercoasters). 
Observations <ref> and <ref> follow from the intermediate and last iterations.









	
		
		If p_1 is not in ℛ_1∪ℛ_2, then we removed p_1 from R_1 and R_2 in the final refinement at the end of the algorithm.  Thus the first run of R_1 is an increasing chain with two points, say p_1, p_2 without loss of generality, and the first run of R_2 is a decreasing chain with two points, say p_1, p_3.  This means that point p_4 must lie between p_2 and p_3 and must start the main case of the intermediate iteration, and this iteration must complete by finding a 3-ascent and 3-descent that share a common point. 
		(In particular, we cannot go directly to the final iteration otherwise one of R_1, R_2 would be longer.)
		
			Let R_1 be the pseudo-rollercoaster that—in the first iteration—was assumed to have an ascent ending in p_1, and let R_2 be the one that was assumed to have a descent ending in p_1.
			Notice that if the first run of R_1 is decreasing, then as described in an intermediate iteration, this run contains at least three points p_k”, p_k', and p_k (with p_k”=a=p_1). In this case we do not remove p_1 from R_1. Also if the first run of R_2 is increasing, then it contains at least three points p_1=d, p_i, and p_k' or p_k” or p_i+1. In this case we do not remove p_1 from R_2. Therefore, p_1 will be removed from both R_1 and R_2 if and only if the first run of R_1 is an increasing chain with two points and the first run of R_2 is a decreasing chain with two points. This configuration is depicted in Figure <ref>(b).
		
	




	
	If p_n is not in ℛ_1 ∪ℛ_2, then the last run of one of them is an ascent ending at a point u and the last run of the other one is a descent ending at a point v such that u lies above v, and p_n lies between them.  
		
		
	
	
		If p_n does not belong to any of ℛ_1 and ℛ_2 then the last run of one of them is an ascent ending at a point u and the last run of the other one is a descent ending at a point v such that u lies above v, and p_n lies between them. 


Depending on whether p_1 is missing from ℛ_1∪ℛ_2 or p_n is missing from ℛ_1∪ℛ_2, or both, we consider three cases.
	
	
		
  * p_1 ∉ℛ_1∪ℛ_2, p_n ∈ℛ_1∪ℛ_2.
		By Observation <ref> there is a common point in ℛ_1 and ℛ_2.  
		Then |ℛ_1|+|ℛ_2|⩾ n and we are done.
		
		
  * p_1 ∈ℛ_1∪ℛ_2, p_n ∉ℛ_1∪ℛ_2.
		We apply Observation <ref>.  Suppose the last run of  ℛ_1 is a descent and the last run of ℛ_2 is an ascent.  Then at the end of the algorithm the last run of R_1 is a descent and the last run of R_2 is an ascent and, by the invariant,  they must have a common point.  If that common point is not p_1 then |ℛ_1|+|ℛ_2|⩾ n and we are done.  So suppose the common point is p_1.   The only danger is that we might remove p_1 from one of them, say R_1.  But this would imply that the last and only run of ℛ_1 has length less than 3, which is impossible.
		Thus p_1 is common to ℛ_1 and ℛ_2, so |ℛ_1|+|ℛ_2|⩾ n and we are done. 
		
		
  * p_1 ∉ℛ_1∪ℛ_2, p_n ∉ℛ_1∪ℛ_2.
		By Observation <ref> there is a common point p in ℛ_1 and ℛ_2. 
		If there were two or more common points then  |ℛ_1|+|ℛ_2|⩾ n and we would be done.
		Thus we may assume that there is only one common point p, which means that the main case of the intermediate iteration only happened once.  
		By Observation <ref> the last run of ℛ_1, say,  is a descent ending below p_n and the last run of ℛ_2 is an ascent ending above p_n.  Because there is only one common point, these must be the only runs in ℛ_1 and ℛ_2 and we have the situation depicted in Figure <ref>.
		
		We have |ℛ_1|+|ℛ_2|⩾ n-1, and thus the length of the longer rollercoaster is at least ⌈n-1/2⌉, which is ⌈n/2⌉ if n is an even number. Assume that n is an odd number, and thus n⩾ 9. If one of ℛ_1 and ℛ_2 contains less than ⌈n-1/2⌉ points, then the other one contains at least ⌈n/2⌉ points. 
		Assume that each of ℛ_1 and ℛ_2 contains ⌈n-1/2⌉ points, which is at least 4 points. 
		Let ℛ'_1 and ℛ'_2 be the sub-chains of ℛ_1 and ℛ_2, respectively, that are to the left of p. Similarly define sub-chains ℛ”_1 and ℛ”_2 to the right of p. 
		
		Assume without loss of generality that |ℛ'_1| ⩽ |ℛ'_2|.
		We consider two cases:
		
		
			
  * |ℛ'_1| < |ℛ'_2|.  Then |ℛ”_1| > |ℛ”_2| and |ℛ'_2| ⩾ 3.
			Then the concatenation of ℛ'_2, p, and ℛ”_1 is a suitable rollercoaster.
			
			
  * |ℛ'_1| = |ℛ'_2|.Then |ℛ”_1| = |ℛ”_2|.  By reversing the sequences if necessary, we may assume that |ℛ'_1| ⩾ |ℛ”_1|, and thus |ℛ'_1| ⩾ 3.  
			Let ℛ_1=(a_1,a_2,a_3,a_4,…) and ℛ_2=(b_1,b_2,b_3,b_4,…). 
			If a_2 is to the right of the vertical line through b_2, then as depicted in Figure <ref> the rollercoaster (b_1,b_2,a_2,a_3,a_4,…) is suitable, otherwise (a_1,a_2,b_2,b_3,b_4,…) is suitable.
			
		
		
	



	Depending on whether or not p_1 belongs to ℛ_1 or ℛ_2 we consider four cases.
	
	
		
  * p_1∈ℛ_1 and p_1∈ℛ_2. Since p_1 belongs to both ℛ_1 and ℛ_2, and p_n is the only point that may not be in either of ℛ_1 and ℛ_2, we have that |ℛ_1|+|ℛ_2|⩾ n, and our result follows.
		
  * p_1∉ℛ_1 and p_1∉ℛ_2. Recall—from the final refinement—that ℛ_1 is obtained from the pseudo-rollercoaster R_1 by removing p_1 and ℛ_2 is obtained from the pseudo-rollercoaster R_2 by removing p_1. Since p_1 is removed from both R_1 and R_2, as described at the end of final refinement, R_1 starts with an increasing chain with 2 points followed by a 3-descent, and R_2 starts with an decreasing chain with 2 points followed by a 3-ascent. In this setting, Observation <ref> implies that ℛ_1 and ℛ_2 share a point p∈{p_2,…,p_n-1}. To this end, if p_n∈ℛ_1∪ℛ_2, then we have |ℛ_1|+|ℛ_2|⩾ n, and our result follows. Assume that p_n∈ℛ_1∪ℛ_2. Observation <ref> and our assumption that ℛ_1 and ℛ_2 share at most one point, imply that the runs of ℛ_1 and ℛ_2 that contain p, wont switch from an ascent to a descent nor vice versa. This configuration is depicted in Figure <ref>(a).    
		
		To this end we have |ℛ_1|+|ℛ_2|⩾ n-1, and thus the length of the longer rollercoaster is at least ⌈n-1/2⌉, which is ⌈n/2⌉ if n is an even number. Assume that n is an odd number, and thus n⩾ 9. If one of ℛ_1 and ℛ_2 contains less than ⌈n-1/2⌉ points, then the other one contains at least ⌈n/2⌉ points. Assume that each of ℛ_1 and ℛ_2 contains ⌈n-1/2⌉ points, which is at least 4 points. Let ℛ_1=(a_1,a_2,a_3,a_4,…) and ℛ_2=(b_1,b_2,b_3,b_4,…). Let ℛ'_1 and ℛ'_2 be the sub-chains of ℛ_1 and ℛ_2, respectively, that are to the left of p. Similarly define sub-chains ℛ”_1 and ℛ”_2 to the right of p. We consider three cases
		
		
			
  * |ℛ'_1|⩾ 2 and |ℛ'_2|⩾ 2. If a_2 is to the right of the vertical line through b_2, then as depicted in Figure <ref>(a) the rollercoaster (b_1,b_2,a_2,a_3,a_4,…) is a suitable, otherwise (a_1,a_2,b_2,b_3,b_4,…) is suitable.
			
  * |ℛ'_1|⩾ 2 and |ℛ'_2|< 2. In this case |ℛ”_2|⩾ 2, moreover |ℛ”_2|>|ℛ”_1|. Thus, the concatenation of ℛ'_1, p, and ℛ”_2 is a suitable rollercoaster.
			
  * |ℛ'_1|< 2 and |ℛ'_2|< 2. In this case  |ℛ”_1|⩾ 2 and |ℛ”_2|⩾ 2, and we obtain a suitable rollercoaster as in case 1.
		
		
		
  * p_1∈ℛ_1 and p_1∉ℛ_2. In this case |ℛ_1|+|ℛ_2|⩾ n-1 assuming that p_n∉ℛ_1∪ℛ_2. Recall—from the final refinement—that ℛ_1=R_1 and ℛ_2 is obtained from R_2 by removing p_1. In this case, ℛ_1 starts with a 3-ascent. Moreover, R_2 starts with a decreasing chain with 2 points followed by a 3-ascent; this implies that ℛ_2 starts with a 3-ascent. Since p_n∉ℛ_1∪ℛ_2, Observation <ref> implies that the rightmost run of one rollercoaster has to switch from an ascent to a descent. If this switch happens, then by Observation <ref> either the two rollercoasters share a point (Figure <ref>(b)), which implies that |ℛ_1|+|ℛ_2|⩾ n, or p_n will be added to ℛ_1 or ℛ_2, which contradicts our assumption that p_n∉ℛ_1∪ℛ_2.
		
  * p_1∉ℛ_1 and p_1∈ℛ_2. This case can be handled similar to the previous case.
	








§ DATA STRUCTURE FOR FINDMAX AND UPDATE



Recall from Section <ref> that we have an array A containing distinct elements from {1,…,n}, and we want to perform the following two operations on A in O(loglog n) time:


	
  * (A,x): Find the largest index l such that A[l]>x. 
	
  * (A,l,x): Set A[l]=x.


 
	Let B be an array with n elements from the set {0,1,…,n} such that each non-zero number occurs at most once in B. We can construct, in linear time, a data structure that, 
	in O(loglog n) amortized time,  performs the operations Suffix Maximum Query (SMQ) and Update defined as follows:
	
	
	
		
  * (l): Return the position of the largest element in B[l..n], and
		
		
  * (B,l,x): Set B[l]=x, assuming that 
		x ∈{1,…,n} is not currently in B.
	



	In linear time, we construct a doubly linked list L (by indices of B) as follows. Set M=n and initialize L by M. For i from n-1 to 1 we do the following: if B[i]>B[M], we add the index i to the front of L and then set M=i. 
	After this, L contains indices i_1,i_2,…,i_k, where i_1<i_2<…<i_k=n, and 
	
    B[i_j] =largest element in
    	B[1 .. n]            for    j=1
    
    	B[(i_j-1+1) .. n]            for all    1< j⩽ k

	This means that every position that will be returned by  queries on B belongs to L. 
	More precisely, for every l∈{1,…,n} we have (l)=i_j where i_j is the smallest index in L that is not smaller than l.
	
	Then in linear time we construct a van Emde Boas tree T with the elements of L; this tree allows us to perform predecessor search, successor search, insert, and delete in O(loglog n) time. 
	To answer an (l) query, we report the smallest element i_j in L such that i_j⩾ l. This can be done in O(loglog n) time by reporting the successor of l in T. 
	
	We implement the (B,l,x) operation as follows. Notice that this operation will not change the answer to (t) queries for any t>l. Thus, we only need to update L and T such that (t) reports a correct position when t⩽ l. We find in L the largest index i_h such that i_h ⩽ l; this can be done is done in O(loglog n) time by a predecessor search in T. If B[i_h+1]>x then we don't do anything as the position of x will not be reported by any  query. Assume that B[i_h+1]<t. Then we insert l in L, between i_h and i_h+1, and also in T. Then we remove from L and T every index i_j, with j⩽ h, for which B[i_j]<x. This can be done in O(r loglog n) where r is the number of elements we that remove. Since every index of B is inserted at most once in L, and also deleted once, the amortized running time of this operation is O(loglog n).


A data structure similar to that of Lemma <ref> can be obtained for Prefix Maximum Queries (l), which ask for the position of the largest element inf B[1..l].
Now we prove Lemma <ref>, which is restated below.



Lemma <ref>. Let A be an array with n elements from the set {0,1,…,n} such that each non-zero number occurs at most once in A. We can construct, in linear time, a data structure that performs  and  operations in O(loglog n) amortized time.



	We construct a van Emde Boas tree T for A (we maintain links between every element of T and its occurrence in A). We construct an array B where B[i]=j if and only if A[j]=i. Then we preprocess B as in the proof of Lemma <ref>.
	
	To answer a (A,x) query we proceed as follows.  We describe the case where we look for the largest index l such that A[l]>x; the description of the case where A[l]<x is analogous. We first compute the successor A[j] of x in A, i.e., the smallest element in A that is greater than x. This can be done by a successor search in T. Since A[j]⩾ x, we have (A,x)⩾ j and A[(A,x)]⩾ A[j]. Hence, to retrieve (A,x) we need to find the largest index k, with k⩾ j, such that A[k]⩾ A[j]. This index k is the maximum element in B[A[j]..n], which is (B,A[j]). By Lemma <ref> this can be done in O(loglog n) time. Therefore, in O(loglog n) time, we can answer (A,x).
	
	To perform (A,l,x), we set A[l]=x, update T (by deleting the old value A[l] and inserting x), and execute (B,x,l). These operations take O(loglog n) amortized time. 


