# Cross-modal Learning of Graph Representations using Radar Point Cloud for
Long-Range Gesture Recognition

Souvik Hazra14, Hao Feng134, Gamze Naz Kiprit13, Michael Stephan12, Lorenzo
Servadei13, Robert Wille3,
Robert Weigel2, Avik Santra1  1Infineon Technologies AG, Neubiberg, Germany
2Friedrich-Alexander-University Erlangen-Nuremberg, Erlangen, Germany
3Technical University of Munich, Munich, Germany  Email: {souvik.hazra,
lorenzo.servadei<EMAIL_ADDRESS>Email<EMAIL_ADDRESS>E-mail: {michael.stephan<EMAIL_ADDRESS>4equal contribution

###### Abstract

Gesture recognition is one of the most intuitive ways of interaction and has
gathered particular attention for human computer interaction. Radar sensors
possess multiple intrinsic properties, such as their ability to work in low
illumination, harsh weather conditions, and being low-cost and compact, making
them highly preferable for a gesture recognition solution. However, most
literature work focuses on solutions with a limited range that is lower than a
meter. We propose a novel architecture for a long-range (1m - 2m) gesture
recognition solution that leverages a point cloud-based cross-learning
approach from camera point cloud to 60-GHz FMCW radar point cloud, which
allows learning better representations while suppressing noise. We use a
variant of Dynamic Graph CNN (DGCNN) for the cross-learning, enabling us to
model relationships between the points at a local and global level and to
model the temporal dynamics a Bidirectional Long short-term memory (LSTM)
network is employed. In the experimental results section, we demonstrate our
model’s overall accuracy of 98.4% for five gestures and its generalization
capability.

###### Index Terms:

Gesture Recognition, mm-wave radar, Dynamic Graph CNN, Graph Neural Networks

††publicationid: pubid: 0000–0000/00$00.00 $\copyright$2015 IEEE

##  I Introduction

Human control interfaces for various indoor applications, e.g., sound systems,
television, and lightning, continuously evolve to increase user comfort. Going
from buttons, switches, and rotary knobs, to touchscreen-based control with
smartphone-apps, the trend is now heading towards gesture-based control [1,
2], allowing for interaction from further distances without requiring
additional hardware. Gesture control needs to be intuitive, accurate, and
should be computationally cheap [3]. While vision-based systems nowadays
fulfill these criteria, they are often seen as too privacy-invasive.
Therefore, radar-based systems have recently been under investigation as a
privacy-preserving alternative solution [4, 5, 6, 7, 8]. However, while
progress has been made, and radar-based gesture sensing has been deployed in
products [4, 9, 10, 11], it is still less accurate than vision-based systems,
especially on longer distances. Therefore, we present a mmWave radar-based
gesture-recognition solution that incorporates knowledge from a camera system
during the training process. Our proposed system uses preprocessed radar data,
in the form of point clouds, as input to a DGCNN [12] for performing cross-
learning from a camera point cloud, which then predicts the performed gesture,
taking multiple frames into account.

##  II Camera Point Cloud

To determine 3D joint coordinates from 2D camera images, the joints must be
visible in at least two cameras and must be matched. First, we feed all camera
images into Detectron2 [13] to detect people and their associated keypoints in
2D space. Here we use the best pretrained keypoint Regions with CNN features
(R-CNN) architecture available in the Detectron2 model zoo trained on the Coco
keypoint dataset [14]. The Coco keypoint dataset contains 17 keypoints for
each person, which are the nose, left eye, right eye, left ear, right ear,
left shoulder, right shoulder, left elbow, right elbow, left wrist, right
wrist, left hip, right hip, left knee, right knee, left ankle, right ankle.
Matching 2D poses through multiple views is challenging for various reasons,
such as occlusion and truncation. Our association component, as shown in Fig.
2, consists of two robust approaches that complement and reinforce each other:
person re-identification and epipolar geometry. The result of our approach is
as shown in Fig. 1(b), 3D joint coordinates, and 17 keypoints.

(a) Radar setup. $\theta_{tilt}=0$.

(b) Camera point cloud.

(c) Range-Doppler Image. Color bar shows the intensity of each bin.

(d) Radar point cloud with color showing velocity value in m/s.

Figure 1: Visualization during anti-clockwise gesture.

####  II-1 Person Re-Identification

The goal of person re-identification is to identify the corresponding person
of interest in different views or at different times. We use the
implementation provided in [15]. It uses a Machine Learning (ML) model, in
which the embeddings of individuals that are close to each other are
considered to be the same person.

####  II-2 Epipolar Geometry

Using epipolar geometry, the geometric information can be leveraged and
objects localized in different cameras. For example, if the object’s location
is specified in the first camera, the search area in the second camera is
constrained to a single line if the epipolar geometry is known [16].

Figure 2: Overview of used approach for skeleton detection. Given an input set
of calibrated camera recordings from different views, we first detect persons
and their keypoints in 2D space using Detectron2. Thus, to match 2D poses in
multiple views, we combine person re-identification and geometric information
of persons. The person re-identification cues along with the geometric cues
are then concatenated and triangularized to determine 3D points.

##  III Radar Point Cloud

This section describes the radar sensor setup and the preprocessing for
converting raw radar data to 5-dimensional point clouds [17] with x-y-z
coordinates, intensity, and Doppler values, as illustrated in Fig. 3.

Figure 3: Pre-processing of raw radar data.

###  III-A mmWave FMCW Radar Sensor

We use Infineon’s BGT60TR13C FMCW radar chipset. It operates by transmitting
multiple frames, each containing a sequence of frequency chirps with a short
ramp time. The response is digitized in 12-bit by the analog-digital
converter, and is further passed to the PC over USB. The operating parameters
of the radar are presented in Tab. I.

Parameters, Symbol | Value
---|---
Ramp start frequency, $f_{\text{min}}$ | 57.5 GHz
Ramp stop frequency , $f_{\text{max}}$ | 58.5 GHz
Frame rate, $f$ | 20 fps
Number of samples per chirp, NTS | 64
Sampling frequency, $fs$ | 2 MHz
Chirp time, $T_{c}$ | 64 $\mu$s
Number of chirps, PN | 128
Number of Tx antennas, $N_{\text{Tx}}$ | 1
Number of Rx antennas, $N_{\text{Rx}}$ | 3
Table I: Operating Parameters.

###  III-B Point Cloud Transformation

####  III-B1 Range Doppler Image (RDI) and Angles Estimation

The reflected target signal is mixed with the transmitted chirp signal and
then passed through a low-pass filter to obtain the intermediate frequency
signal [18]. Since we are only interested in moving targets in gesture
recognition, we use previous frame subtraction as Moving Target Indication
(MTI) [19]. By applying 2D Range-Doppler-Fast Fourier Transform (FFT) along
the sample and chirp axes, we can acquire RDIs, comprising range, Doppler, and
intensity information, as shown in Fig. 1(c). Additionally, as we work with
single-person scenarios, we first detect the range-Doppler bin with the
highest intensity and filter out any points far away from it as noise [20].
Afterwards, we select a certain number of high-intensity range-Doppler bins
and use the values in a $5\times 3$ window around each bin, seen in Fig 1(c),
to estimate the covariance matrix for Direction Of Arrival (DOA) estimation
with bartlett beamforming. Now the points are in spherical radar coordinates
$(r,\theta_{azi},\theta_{ele})$, which correspond to range, azimuth angle, and
elevation angle. We finally apply the transformation matrix [21] shown below,

$\begin{bmatrix}x\\\ y\\\ z\end{bmatrix}=\begin{bmatrix}1&0&0\\\
0&\cos{\theta_{tilt}}&\sin{\theta_{tilt}}\\\
0&-\sin{\theta_{tilt}}&\cos{\theta_{tilt}}\end{bmatrix}\begin{bmatrix}r\cos{\theta_{ele}}\sin{\theta_{azi}}\\\
r\cos{\theta_{ele}}\cos{\theta{azi}}\\\
r\sin{\theta_{ele}}\end{bmatrix}+\begin{bmatrix}x_{r}\\\ y_{r}\\\
h\end{bmatrix}$

(1)

where $(x,y,z)$ denote the resulting ground Cartesian coordinates,
$\theta_{tilt}$ and $(x_{r},y_{r},h)$ are the tilt angle and ground Cartesian
coordinates of radar, respectively.

####  III-B2 Point Cloud

With the help of a radar sensor, we can collect the points corresponding to
the detected object. However, a specific number of sample points for each
frame is required as input. Thus, to simplify the computation, traditional
zero-padding is the method we choose for oversampling, which means adding all-
zero points to complement the point cloud. Meanwhile, for frames with more
points than we require, sorting the points by their intensity and selecting a
predefined number allows us to save the samples with the most information
[22]. Finally, we take $(x,y,z,d,intensity)$ which are coordinates, Doppler,
and intensity value into consideration as the features of each point, shown in
Fig. 1(d).

##  IV Architecture and Learning

In this section, we introduce the network’s architecture of our proposed
Autoencoder shown in Fig. 4 for cross-learning between radar and camera
information [23]. The architecture is composed of a Graph Neural Network (GNN)
[24], specifically DGCNN [12], followed by LSTM layers for recognition of
gesture sequences.

Figure 4: Network Architecture: Radar point cloud in shape $n\times 5$ first
passes through an input transformation module and then is fed into DGCNN
Autoencoder, followed by one fully connected layer to reconstruct camera-based
skeletons. Next, the latent space of each Autoencoder-frame is stacked in
temporal order with sequence length $l=30$, which is used to generate
classification scores for five classes by two bidirectional LSTM layers and
two fully connected layers. EdgeConv block: A tensor of shape $n\times f$ is
fed into the block as input, for computing edge features of each point in
$k$-nn Graph by a MLP with the number of layer units denoted as
$\\{a_{1},a_{2},\dots,a_{n}\\}$. Then, after max pooling across neighboring
edge features, we get a updated tensor of shape $n\times a_{n}$.

###  IV-A Edge Convolution

The radar point cloud contains $n$ points with $F$ features in each frame,
denoted by
$\mathrm{\mathbf{R}=\\{\mathbf{r}_{1},...,\mathbf{r}_{n}\\}}\subseteq\mathbb{R}^{F}$.
In our case, $F=5$, representing 3D coordinates $x_{i},y_{i},z_{i}$, intensity
and Doppler value $i,d$ in RDI and $n$ points per frame. We apply $k$-Nearest
Neighbour ($k$-NN) by Euclidean distance to generate the local graph of
$\mathrm{\mathbf{R}}$ in $\mathbb{R}^{F}$ including self-loop, represented as
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\\{1,...,n\\}$ and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ are the $vertices$ and
$edges$, respectively. As illustrated in Fig. 5, to capture both global
structure and local neighbourhood information, $edgefeatures$ between two
points is computed as

$\bm{e}_{ij}=h_{\mathbf{\Theta}}(\mathbf{r}_{i},\mathbf{r}_{j}-\mathbf{r}_{i})$
(2)

where
$h_{\mathbf{\Theta}}:\mathbb{R}^{F}\times\mathbb{R}^{F}\rightarrow\mathbb{R}^{F^{\prime}}$
is a nonlinear function with learnable parameters $\mathbf{\Theta}$ and
$\\{\mathbf{r}_{j}:(i,j)\in\mathcal{E}\\}$ is the set of neighbours around
$\mathbf{r}_{i}$. More specifically, this edge convolution can be expressed as

$e_{ijf^{\prime}}=\sigma(\bm{\theta}_{f^{\prime}}\cdot(\mathbf{r}_{j}-\mathbf{r}_{i})+\bm{\phi}_{f^{\prime}}\cdot\mathbf{r}_{i}),$
(3)

and implemented as a shared MLP, here
$\mathbf{\Theta}=(\bm{\theta}_{1},\dots,\bm{\theta}_{F^{\prime}},\bm{\phi}_{1},\dots,\bm{\phi}_{F^{\prime}})$,
$leakyReLU$ is chosen as non-linear function $\sigma(\cdot)$. At last, we take
max pooling as the aggregation operation on the $edgefeatures$ to update the
points

$r^{\prime}_{if^{\prime}}=\max_{j:(i,j)\in\mathcal{E}}e_{ijf^{\prime}}.$ (4)

which can capture the sharpest features to represent the points in lower-
level. In general, this EdgeConv creates an $F^{\prime}$-dimensional point
cloud with the same number of points as the input $F$-dimensional point cloud,
where $k=3$ and $n=64$.

Figure 5: Left: Generating $f^{{}^{\prime}}$-dimensional edge features
$\mathbf{e}_{ij}$ from two $f$-dimensional points $\mathbf{r}_{i}$ and
$\mathbf{r}_{j}$. Here, we choose one fully connected layer as
$h_{\Theta}(\cdot)$ and $f=3$, $f^{{}^{\prime}}=4$ for example. Right:
Updating $\mathbf{r}_{i}^{{}^{\prime}}$ from $\mathbf{r}_{i}$ by Edge
Convolution, $k=3$ in our case, and $e_{i0}$ indicates self loop.

###  IV-B Model Architecture

The overview of our whole network architecture is visualized in Fig. 4,
including three main parts: input transformation, cross learning between radar
and camera point cloud, and gesture recognition.

####  IV-B1 Input transformation

As described in Section 3, we multiply the coordinates in radar coordination
by our radar setup’s rotation matrix to convert them to ground Cartesian
coordinates. However, this transformation is insufficiently precise due to the
measurement, and the object, in this case the test person, should be invariant
following certain geometric modifications. As a result, we refer to the
spatial transformation in this contribution [25], in which a mini-network
(T-net in Fig. 4) predicts an affine transformation matrix from the point
itself and its neighbours, and applies it directly to the input point cloud.

####  IV-B2 Cross Learning

The upper branch of the network architecture illustrated in Fig. 4, is the
Autoencoder for cross learning between the point cloud from radar and camera
domain. The Encoder contains three successive EdgeConv blocks, where the graph
is dynamically updated after each one. Afterwards, their multi-scale outputs
are concatenated together, followed by one fully-connected layer to form 136
dimensional latent space. Then, the Decoder is used to reconstruct camera
skeletons from prior latent feature vector, having similar structure with the
Encoder, while only two EdgeConv blocks present. Finally, after going through
the last fully-connected layer (51), the point cloud is reshaped to $17\times
3$, representing 17 joints of the person in $(x,y,z)$ coordinates. The number
$k$ for computing $k$-NNs is set as 3 for all EdgeConv blocks.

####  IV-B3 Classification

After obtaining the latent features from Encoder, the lower branch shown in
Fig. 4 extracts both spatial and temporal information of each gesture motion
sequence with length $l=30$. The latent feature vectors of each frame in the
sequence are firstly stacked to create $l\times 136$ tensor, fed as input into
two 64-units Bidirectional LSTM layers [26]. The last two fully-connected
layer (64,5) produce 5 dimensional feature vector for gesture classification.

##  V Experimental

We used a synchronized camera-radar setup as introduced in Section 3 to
perform seamless multi-modal data acquisition to train our proposed model and
then for evaluation. The training data is balanced and consists of 1773
recordings and 392 recordings (sequence length $l=30$ for each recording) for
evaluation. The evaluation dataset doesn’t include any camera data as only
radar data is used as input during inference.

Figure 6: Confusion matrix.

We define five macro-gestures as classes that involve a complete hand
movement. The five classes are swipe - where the hand is moved horizontally
from one end to another, push- where the hand is moved toward the radar from
the body, pull - where the hand is moved from away from the radar towards the
body, clockwise - where a big circular movement is done by the hand in a
clockwise manner and anti-clockwise - where the same is done but in an anti-
clockwise manner. The choice of gestures was made based on their relevance to
past literature and simplicity. The training data involved five volunteers who
performed the gesture at a distance ranging between 1m -2 m with minimal prior
instructions and switched between left and right hands and their distance from
the radar. The evaluation dataset was similarly performed by another five
volunteers but in a different room and radar orientation setup to demonstrate
the proposed architecture’s generalization capability. Furthermore, the room
setup for the evaluation dataset contained more reflecting objects so as to
check our model’s ability to suppress such reflections.

Figure 7: Accuracy comparison among uni-modal, cross learning and cross
learning with fine-tuning.

The upper branch in Fig. 4 is first trained with synchronized radar point
cloud and camera skeletons data using Mean Squared Error (MSE)loss, and then
we save the input transformation and Encoder modules for the training of
classification in the lower branch by Cross-Entropy and Triplet losses
combined in the same weight, which can be set as frozen or not for fine-
tuning. The overall accuracy for the proposed model is 98.4% compared to from
45% to 90% for the baseline model, which is trained in a uni-modal fashion.
Fig. 6 depicts the confusion matrix for our proposed model and Fig. 7
represents the training and testing accuracy of different setups. It clearly
demonstrates the superiority of the proposed learning approach over a uni-
modal approach with better accuracy, robustness, and stable learning.

##  VI Conclusion

The paper proposes a low-cost radar-based gesture recognition system with an
overall accuracy of 98% where the subject performs macro gestures at a varying
range between 1m to 2m. We introduce a novel architecture based on GNN s that
enables knowledge distillation from camera point clouds to radar point clouds,
allowing the system to learn better underlying relationships between the radar
points and suppress other possible targets in the field of view.

## References

  * [1] Q. Wan, Y. Li, C. Li, and R. Pal, “Gesture recognition for smart home applications using portable radar sensors,” in _2014 36th Annual International Conference of the IEEE Engineering in Medicine and Biology Society_ , 2014, pp. 6414–6417.
  * [2] K. A. Smith, C. Csech, D. Murdoch, and G. Shaker, “Gesture recognition using mm-wave sensor for human-car interface,” _IEEE Sensors Letters_ , vol. 2, no. 2, pp. 1–4, 2018.
  * [3] S. Mitra and T. Acharya, “Gesture recognition: A survey,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , vol. 37, no. 3, pp. 311–324, 2007.
  * [4] E. Hayashi, J. Lien, N. Gillian, L. Giusti, D. Weber, J. Yamanaka, L. Bedal, and I. Poupyrev, “RadarNet: Efficient gesture recognition technique utilizing a miniature radar sensor,” in _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_. ACM, may 2021.
  * [5] M. Stephan, S. Hazra, A. Santra, R. Weigel, and G. Fischer, “People counting solution using an FMCW radar with knowledge distillation from camera data,” in _2021 IEEE Sensors_. IEEE, october 2021.
  * [6] M. Stephan, L. Servadei, J. Arjona-Medina, A. Santra, R. Wille, and G. Fischer, “Scene-adaptive radar tracking with deep reinforcement learning,” _Machine Learning with Applications_ , vol. 8, p. 100284, june 2022.
  * [7] L. Servadei, H. Sun, J. Ott, M. Stephan, S. Hazra, T. Stadelmayer, D. S. Lopera, R. Wille, and A. Santra, “Label-aware ranked loss for robust people counting using automotive in-cabin radar,” _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , may 2022.
  * [8] A. Santra and S. Hazra, _Deep Learning Applications of Short Range Radars_ , ser. Artech House radar library. Artech House, 2020. [Online]. Available: https://books.google.de/books?id=Qb-VzQEACAAJ
  * [9] S. Hazra and A. Santra, “Robust gesture recognition using millimetric-wave radar system,” _IEEE Sensors Letters_ , vol. 2, no. 4, pp. 1–4, 2018.
  * [10] ——, “Radar gesture recognition system in presence of interference using self-attention neural network,” in _2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)_ , 2019, pp. 1409–1414.
  * [11] P. Molchanov, S. Gupta, K. Kim, and K. Pulli, “Short-range fmcw monopulse radar for hand-gesture sensing,” in _2015 IEEE Radar Conference (RadarCon)_ , 2015, pp. 1491–1496.
  * [12] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon, “Dynamic graph cnn for learning on point clouds,” _ACM Trans. Graph._ , vol. 38, no. 5, october 2019. [Online]. Available: https://doi.org/10.1145/3326362
  * [13] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick, “Detectron2,” https://github.com/facebookresearch/detectron2, 2019.
  * [14] T.-Y. Lin, M. Maire, S. Belongie, L. Bourdev, R. Girshick, J. Hays, P. Perona, D. Ramanan, C. L. Zitnick, and P. Dollár, “Microsoft coco: Common objects in context,” 2015.
  * [15] H. Luo, Y. Gu, X. Liao, S. Lai, and W. Jiang, “Bag of tricks and a strong baseline for deep person re-identification,” in _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 2019, pp. 1487–1495.
  * [16] Z. Zhang, _Epipolar Geometry_. Boston, MA: Springer US, 2014, pp. 247–258. [Online]. Available: https://doi.org/10.1007/978-0-387-31439-6_128
  * [17] D. Salami, R. Hasibi, S. Palipana, P. Popovski, T. Michoel, and S. Sigg, “Tesla-rapture: A lightweight gesture recognition system from mmwave radar sparse point clouds,” _IEEE Transactions on Mobile Computing_ , pp. 1–1, 2022.
  * [18] Z. Zhang, Z. Tian, and M. Zhou, “Latern: Dynamic continuous hand gesture recognition using fmcw radar sensor,” _IEEE Sensors Journal_ , vol. 18, no. 8, pp. 3278–3289, 2018.
  * [19] G. Zhang, X. Geng, and Y.-J. Lin, “Comprehensive mpoint: A method for 3d point cloud generation of human bodies utilizing fmcw mimo mm-wave radar,” _Sensors_ , vol. 21, no. 19, 2021. [Online]. Available: https://www.mdpi.com/1424-8220/21/19/6455
  * [20] P. Svenningsson, F. Fioranelli, and A. Yarovoy, “Radar-pointgnn: Graph based object recognition for unstructured radar point-cloud data,” in _2021 IEEE Radar Conference (RadarConf21)_ , 2021, pp. 1–6.
  * [21] F. Jin, A. Sengupta, and S. Cao, “mmfall: Fall detection using 4-d mmwave radar and a hybrid variational rnn autoencoder,” _IEEE Transactions on Automation Science and Engineering_ , pp. 1–13, 2020.
  * [22] K. Qian, Z. He, and X. Zhang, “3d point cloud generation with millimeter-wave radar,” _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ , vol. 4, no. 4, december 2020. [Online]. Available: https://doi.org/10.1145/3432221
  * [23] Y. Wang, Z. Jiang, Y. Li, J.-N. Hwang, G. Xing, and H. Liu, “RODNet: A real-time radar object detection network cross-supervised by camera-radar fused object 3d localization,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 15, no. 4, pp. 954–967, june 2021. [Online]. Available: https://doi.org/10.1109%2Fjstsp.2021.3058895
  * [24] D. S. Lopera, L. Servadei, G. N. Kiprit, S. Hazra, R. Wille, and W. Ecker, “A survey of graph neural networks for electronic design automation,” in _2021 ACM/IEEE 3rd Workshop on Machine Learning for CAD (MLCAD)_ , 2021, pp. 1–6.
  * [25] R. Q. Charles, H. Su, M. Kaichun, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 77–85.
  * [26] P. Gong, C. Wang, and L. Zhang, “Mmpoint-gnn: Graph neural network with dynamic edges for human activity recognition through a millimeter-wave radar,” in _2021 International Joint Conference on Neural Networks (IJCNN)_ , 2021, pp. 1–7.


# Fast and Longest Rollercoasters

Paweł Gawrychowski  Institute of Computer Science, University of Wrocław,
Poland
gawry<EMAIL_ADDRESS>Florin Manea  Kiel University,
Germany
<EMAIL_ADDRESS>Radosław Serafin  Institute of Computer Science,
University of Wrocław, Poland
gawry<EMAIL_ADDRESS>
###### Abstract

For $k\geq 3$, a k-rollercoaster is a sequence of numbers whose every maximal
contiguous subsequence, that is increasing or decreasing, has length at least
$k$; $3$-rollercoasters are called simply rollercoasters. Given a sequence of
distinct real numbers, we are interested in computing its maximum-length (not
necessarily contiguous) subsequence that is a $k$-rollercoaster. Biedl et al.
(2018) have shown that each sequence of $n$ distinct real numbers contains a
rollercoaster of length at least $\lceil n/2\rceil$ for $n>7$, and that a
longest rollercoaster contained in such a sequence can be computed in $O(n\log
n)$-time (or faster, in $O(n\log\log n)$ time, when the input sequence is a
permutation of $\\{1,\ldots,n\\}$). They have also shown that every sequence
of $n\geqslant(k-1)^{2}+1$ distinct real numbers contains a $k$-rollercoaster
of length at least $\frac{n}{2(k-1)}-\frac{3k}{2}$, and gave an $O(nk\log
n)$-time (respectively, $O(nk\log\log n)$-time) algorithm computing a longest
$k$-rollercoaster in a sequence of length $n$ (respectively, a permutation of
$\\{1,\ldots,n\\}$).

In this paper, we give an $O(nk^{2})$-time algorithm computing the length of a
longest $k$-rollercoaster contained in a sequence of $n$ distinct real
numbers; hence, for constant $k$, our algorithm computes the length of a
longest $k$-rollercoaster in optimal linear time. The algorithm can be easily
adapted to output the respective $k$-rollercoaster. In particular, this
improves the results of Biedl et al. (2018), by showing that a longest
rollercoaster can be computed in optimal linear time. We also present an
algorithm computing the length of a longest $k$-rollercoaster in
$O(n\log^{2}n)$-time, that is, subquadratic even for large values of $k\leq
n$. Again, the rollercoaster can be easily retrieved. Finally, we show an
$\Omega(n\log k)$ lower bound for the number of comparisons in any comparison-
based algorithm computing the length of a longest $k$-rollercoaster.

##  1 Introduction

The mathematical study of patterns occurring in sequences of numbers is a
rather old and well developed topic in combinatorics and algorithms on
sequences. Within this topic, of a particularly high interest is the study of
long increasing and decreasing (not necessarily contiguous) subsequences
occurring in a sequence. For example, already in 1749, Euler defined the
Eulerian polynomials, which are the generating function for the number of
descents in permutations. Almost 200 years later, Erdős and Szekeres [9]
proved the existence of an increasing or a decreasing subsequence of length at
least $a+1$ in a sequence of at least $n=a^{2}+1$ distinct reals. More
precisely, they have shown the following theorem.

######  Theorem 1 (Erdős and Szekeres, 1935).

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$.

The theorem of Erdős--Szekeres is strongly related to, and in fact also
follows from, the well-known decomposition of Dilworth (see [17]) regarding
chains and antichains in a finite partially ordered set. Dilworth’s result can
be restated in the context of the combinatorics of patterns in sequences of
numbers as follows.

######  Theorem 2 (Dilworth, 1950).

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$.

Recent surveys on the combinatorics of patterns occurring in sequences are
[14, 13].

The study of patterns in sequences of numbers also has a well developed
algorithmic side (see, e.g., [10, 12, 8, 4]). For instance, finding a longest
increasing subsequence (not necessarily contiguous) contained in the input
sequence is a basic problem in theoretical computer science, studied already
from the 1960s [16, 3, 15], with applications in areas such as bioinfomatics
and physics (see [18] and the references therein). In particular, in 1975
Fredman [10] presented an algorithm (which he attributed to Knuth, now
considered folklore) computing the length of a longest increasing subsequence
(LIS) in an array of $n$ numbers in $O(n\log n)$ time, and proved that this is
optimal for comparison-based algorithms. If required, the algorithm can be
extended to retrieve such a subsequence. If the input sequence can be sorted
in linear time (in particular, when the input sequence is a permutation of
$\\{1,\ldots,n\\}$) and we do not require the algorithm to be comparison-
based, the solution given by Fredman can be implemented in $O(n\log\log n)$
time, see [8] and the references therein. Fredman’s algorithm is often called
Patience Sorting, and has some connections to constructing the so-called Young
Tableaux [3, 15].

We consider a notion that is strongly related to longest increasing
subsequences (and longest decreasing subsequences). A run in a sequence of
numbers is a maximal contiguous subsequence that is either increasing or
decreasing. A $k$-rollercoaster, where $k\geq 3$, is a sequence of numbers
whose every run has length at least $k$; $3$-rollercoasters are called, for
short, rollercoasters. For example, the sequence $(3,6,8,10,9,5,1,2,4,7,11)$
is a $4$-rollercoaster with runs $(3,6,8,10)$, $(10,9,5,1)$, $(1,2,4,7,11)$.
Given a sequence $S[1:n]=(S[1],S[2],\dots,S[n])$ of $n$ distinct numbers, the
$k$-rollercoaster problem is to find a maximum-size set of indices
$i_{1}<i_{2}<\dots<i_{m}$ such that $(S[{i_{1}}],S[{i_{2}}],\dots,S[{i_{m}}])$
is a $k$-rollercoaster. In other words, this problem asks for a longest
$k$-rollercoaster contained in the input sequence $S$.

There is a simple, but useful, geometrical interpretation of
$k$-rollercoasters. The input sequence $S[1:n]$ can be depicted as a set $P$
of points in the plane by translating, for $i$ from $1$ to $n$, the number
$S[i]$ to a point $p_{i}=(i,S[i])$. In this setting, a $k$-rollercoaster in
$S$ translates to a polygonal path in the plane, whose vertices are points of
$P$, and such that every maximal sub-path, with positive- or negative-sloped
edges, has at least $k$ points. The rollercoaster $(3,6,8,10,9,5,1,2,4,7,11)$
is depicted in the left half of Figure 1. Two $4$-rollercoasters occurring in
the sequence $(3,6,1,8,7,17,13,10,11,12,9,5,14,4,2,15,16)$ are depicted in the
right half of the same figure.

Figure 1: Left: a $4$-rollercoaster $(3,6,8,10,9,5,1,2,4,7,11)$ with runs
$(3,6,8,10)$, $(10,9,5,1)$, $(1,2,4,7,11)$. Right: two $4$-rollercoasters,
represented with a solid and, respectively, a dashed line, in
$(3,6,1,8,7,17,13,10,11,12,9,5,14,4,2,15,16)$.

While rollercoasters seem interesting on their own as a combinatorial
structure, the original motivation for their study was a connection to
computational geometry and graph drawing, namely to point-set embeddings of
caterpillars (see [6, 5] and the references therein). More precisely,
constructing a long rollercoaster in a sequence of numbers was used as an
intermediate step towards obtaining a method of drawing a $n$-vertex top-view
caterpillar, with L-shaped edges, on a set of $\frac{25}{3}n$ general
orthogonal position points in the plane. This is currently the best known
bound on the number of points required to draw such a graph.

In [5], the following results regarding $k$-rollercoasters were shown. First,
from a combinatorial point of view, for $k=3$, it was shown that the length of
a longest rollercoaster contained in a sequence of $n\geq 7$ distinct numbers
is at least $\lceil\frac{n}{2}\rceil$. As far as $k$-rollercoasters are
concerned, it was shown that for $k\geqslant 4$ every sequence of
$n\geqslant(k-1)^{2}+1$ distinct numbers contains a $k$-rollercoaster of
length at least $\frac{n}{2(k-1)}-\frac{3k}{2}$. From an algorithmic point of
view, both previously mentioned results were constructive, leading to an
$O(n)$-time (respectively $O(n\log k)$) algorithm computing a long (but not
necessarily a longest) rollercoaster (respectively, $k$-rollercoaster)
contained in a sequence of $n$ distinct numbers. A longest rollercoaster
contained in such a sequence was computed by an extension of Fredman’s
algorithm in $O(n\log n)$-time, and if the input sequence is a permutation of
$\\{1,\ldots,n\\}$ (or, more generally, sortable in linear time) in
$O(n\log\log n)$ time. By further generalising this approach, an $O(nk\log
n)$-time (respectively, $O(nk\log\log n)$-time) algorithm computing a longest
$k$-rollercoaster in a sequence of $n$ distinct numbers (respectively, a
permutation of $\\{1,\ldots,n\\}$) can be obtained. Note that, by the theorem
of Erdös and Szekeres, a sequence of $n$ distinct numbers always contains a
$\lfloor\sqrt{n}\rfloor$-rollercoaster, and the aforementioned algorithm
computes a longest such rollercoaster in $O(n^{1.5}\log n)$ time.

### Our contributions.

We consider the problem of computing a longest $k$-rollercoaster in an input
sequence $S[1:n]$ and provide three results.

Firstly, we design a comparison-based algorithm computing the length of a
longest $k$-rollercoaster in a sequence of $n$ distinct numbers in $O(nk^{2})$
time. Thus, we obtain an optimal linear-time algorithm for constant values of
$k$, in particular for $k=3$. This significantly improves the results of [5]
and shows that, even though longest rollercoasters are related to longest
increasing subsequences, the rich combinatorial structure of the former makes
them provably easier to find. The starting point of our algorithm is the
following natural dynamic programming formulation. For each $2\leq i\leq k$,
and for each element $S[j]$, we compute a longest (not necessarily contiguous)
subsequence of $S$ ending with $S[j]$ and with every run of length at least
$k$, except for the last run, which has only $i$ elements if $i<k$ and at
least $k$ elements if $i=k$. Now the difficulty is to find the predecessor
$S[j^{\prime}]$ of $S[j]$ in such a subsequence in time proportional to $k$,
in particular avoiding any kind of binary search. We greedily decompose the
input sequence into blocks with a certain property related to Dilworth’s
theorem and prove, by a careful case analysis, that $j^{\prime}$ must belong
to the previous few such blocks. This, together with the special structure of
the blocks and appropriate data structures, allows us to find $j^{\prime}$ in
$O(k)$ amortised time.

Secondly, we focus on the case of large $k$. Given that both the previous and
the new algorithm have at least linear dependency on $k$, it might seem
plausible that this is inherent to the problem, for example that for
$k\geq\lfloor\sqrt{n}\rfloor$ the running time of any algorithm needs to be
$\Omega(n^{1.5})$. We show that this is not the case by designing a
subquadratic algorithm that computes a longest $k$-rollercoaster in a sequence
of $n$ distinct numbers in $O(n\log^{2}n)$ time. To obtain this result, we
exploit the fact that if an increasing (respectively, decreasing) run in a
longest $k$-rollercoaster extends from $S[i]$ to $S[j]$, then that run should
be LIS (respectively, longest decreasing sequence, LDS for short) in $S[i:j]$.
If one arranges the length of LIS (respectively, LDS) in $S[i:j]$ in an
$n\times n$ matrix then the matrix has the anti-Monge property. It is known
that all row maxima of an anti-Monge matrix can be found in $O(n)$ time [2],
that is, in sublinear time w.r.t. the size of the matrix (given an oracle
access to the elements of the matrix). Such properties have been successfully
exploited to speed up certain dynamic programming algorithms. We also follow
this route, and construct a longest $k$-rollercoaster using dynamic
programming, essentially by gluing together LISs and LDSs of consecutive
contiguous subsequences of $S$.

Thirdly, we show that any comparison-based algorithm computing a longest
$k$-rollercoaster needs $\Omega(n\log k)$ comparisons. Our reasoning is
similar to the one used by Fredman to show that any comparison-based algorithm
computing a LIS needs $\Omega(n\log n)$ comparisons. We leave as an open
problem to close the gap between the lower and upper bounds shown here.

The paper is organised as follows. After a series of preliminaries, we
describe the $O(nk^{2})$-time algorithm for computing the length of a longest
$k$-rollercoaster, followed by the $O(n\log^{2}n)$-time algorithm. Then we
show how the respective longest $k$-rollercoasters can be effectively
constructed. We conclude with the lower bound for the number of comparisons
needed to compute the length of a longest $k$-rollercoaster in a sequence of
length $n$.

##  2 Preliminaries

We consider sequences of distinct real numbers and work in the comparison-
based model. If $S$ is a sequence of $n$ numbers, then $|S|=n$ is the length
of the sequence, and $S[i]$ denotes its $i^{\text{th}}$ element. A subsequence
of $S$ is a sequence $(S[i_{1}],S[i_{2}],\ldots,S[i_{m}])$, defined by
specifying the indices $1\leq i_{1}<i_{2}<\ldots<i_{m}\leq n$. For $1\leq
i\leq j\leq n$, $S[i:j]$ denotes the contiguous subsequence
$(S[i],S[i+1],\ldots,S[j])$; in particular, $S[1:n]$ denotes the entire $S$.
Note that unless explicitly stated, a subsequence is not necessarily
contiguous. An increasing subsequence (respectively, decreasing subsequence)
of $S$ is a subsequence $(S[i_{1}],S[i_{2}],\ldots,S[i_{m}])$ such that
$S[i_{j}]<S[i_{j+1}]$, for all $1\leq j\leq m-1$ (respectively,
$S[i_{j}]>S[i_{j+1}]$, for all $1\leq j\leq m-1$). A longest increasing
(respectively, decreasing) sequence, for short LIS (respectively, LDS), is an
increasing (respectively, decreasing) sequence with the largest possible
length. Fredman gave an $O(n\log n)$-time algorithm for computing the length
of LIS, denoted $\mathsf{res}$ in Algorithm 1. A byproduct of this algorithm
is a partition of $S[1:n]$ into $\mathsf{res}$ non-increasing subsequences
that can be obtained by creating, for every $1\leq j\leq\mathsf{res}$, a list
of elements that has been stored in $R[j]$.

Algorithm 1 Finding the length of LIS of $S$

1:$R[0]\leftarrow 0$

2:$\mathsf{res}\leftarrow 0$

3:for $i\leftarrow 1$ to $n$ do

4: $k\leftarrow\max\\{j:R[j]<S[i]\\}$ $\triangleright$ binary search over
$R[0]<R[1]<R[2]<\ldots$

5: $R[k+1]\leftarrow S[i]$

6: $\mathsf{res}\leftarrow\max\\{\mathsf{res},k+1\\}$

7:return $\mathsf{res}$

A run in a sequence of numbers is a maximal contiguous subsequence that is
increasing or decreasing. A $k$-rollercoaster is a sequence of numbers such
that every run has length at least $k$; $3$-rollercoasters are called, for
short, rollercoasters. Given a sequence $S[1:n]$ we are interested in finding
its longest subsequence that is a $k$-rollercoaster. To make the exposition
easier to follow, we focus first on finding the length of such a subsequence.
Recovering the subsequence itself is, in all our algorithms, rather
straightforward, and explained in Section 5.

##  3 Computing a Longest $k$-Rollercoaster in $O(nk^{2})$-Time

In this section we show how to find a longest $k$-rollercoaster of $S[1:n]$ in
$O(nk^{2})$ time.

We begin our algorithm with a preprocessing phase. An alternating
$k$-decomposition of $S[1:n]$ is a partition of $S[1:n]$ into contiguous
subsequences (called parts) $S_{1},S_{2},\ldots,S_{m}$ such that the length of
LIS in the odd parts ($S_{1}$, $S_{3}$, $S_{5}$, and so on) is $k$ while the
length of LDS in the even parts is $k$, possibly smaller for the very last
part, and additionally by removing the last element of any odd (even) part we
obtain a sequence with LIS (LDS) of length less than $k$. In other words, for
$\ell\geq 1$, $S_{\ell}$ is either the shortest contiguous subsequence of $S$
that follows directly after $S_{1}\cdots S_{\ell-1}$ and has for $\ell$ odd
(even) a LIS (respectively, LDS) of length $k$, if such a subsequence exists,
or the whole remaining part of $S$ otherwise. For example, an alternating
3-decomposition of $S=(1,4,2,5,8,7,6,3)$ is $(1,4,2,5),(8,7,6),(3)$.

######  Lemma 1.

An alternating $k$-decomposition of $S[1:n]$ can be found in $O(n\log k)$
time.

###### Proof.

By terminating Algorithm 1 as soon as $\mathsf{res}=k$ we can find the
shortest prefix of $S$ with LIS equal to $k$ in $O(d\log k)$ time, where $d$
is the length of the prefix. Then we find the shortest prefix of the remaining
suffix of $S$ with LDS equal to $k$, and repeat. Overall, this takes $O(n\log
k)$ time because all parts are disjoint. ∎

######  Proposition 1.

Let $A$ be a $k$-rollercoaster in $S$. Any part $S_{\ell}$ contains elements
of at most four consecutive runs of $A$.

###### Proof.

By contradiction. Let $S^{\prime}_{\ell}$ be $S_{\ell}$ without the last
element. If $S_{\ell}$ contains elements of five consecutive runs of $A$ then
$S^{\prime}_{\ell}$ contains elements of four consecutive runs of $A$, and
hence all elements of two such consecutive runs. Thus, if $S_{\ell}$ is an odd
(even) part then $S^{\prime}_{\ell}$ contains LIS (LDS) of length $k$, which
contradicts the definition of an alternating $k$-decomposition. ∎

By Dilworth’s theorem, a part with LIS of length $k$ can be decomposed into
$k$ decreasing subsequences, and such a decomposition can be obtained as a
byproduct of Algorithm 1. Thus, we can decompose each part into up to $k$
monotone (increasing or decreasing, depending on whether the part is odd or
even) subsequences. These subsequences can be then merged to obtain a sorted
list $P_{\ell}$ of all elements in the corresponding part $S_{\ell}$ in
$O(n\log k)$ overall time, for example by first merging pairs of subsequences,
then quadruples, and so on.

Before moving on to the description of our algorithm, we need a combinatorial
lemma that relates an alternating $k$-decomposition to a longest
rollercoaster.

######  Lemma 3.

Suppose that $x=S[j]$ is a non-first element occurring in an increasing run of
a longest $k$-rollercoaster, and $y=S[j^{\prime}]$ is its predecessor in the
same run, and consider an alternating $k$-decomposition of $S[1:n]$. Then
either $x$ and $y$ are in the same part $S_{i}$, or $y$ is in one of the parts
$S_{i-4},S_{i-3},S_{i-2},S_{i-1}$.

###### Proof.

By contradiction. Suppose that there are at least four parts between $x$ and
$y$, i.e., $x$ is in $S_{i}$ and $y$ is in some $S_{k}$ with $k<i-4$. Let $r$
denote the run in the $k$-rollercoaster that contains $x$ and $y$, let $d$ be
the length of $r$, and let $\ell$ be such that $r[\ell]=y$ and $r[\ell+1]=x$.
We assume that $r$ is an increasing run (see Figure 2); the case when $r$ is
decreasing can be treated in the same way.

Figure 2: The increasing run $r$ from Lemma 3, with the points $x$ and $y$
highlighted.

Consider the following four cases:

  1. 1.

$\ell\leq k-1$ (i.e., there are at most $k-2$ elements in $r$ before $y$) and
$k-2\geq d-\ell-1$ (there are at most $k-2$ elements in $r$ after $x$).

  2. 2.

$\ell\leq k-1$ and $k-1\leq d-\ell-1$ (there at least $k-1$ elements in $r$
after $x$).

  3. 3.

$\ell\geq k$ (there are at least $k-1$ elements in $r$ before $y$) and
$k-2\geq d-\ell-1$.

  4. 4.

$\ell\geq k$ and $k-1\leq d-\ell-1$.

Recall that there are at least four whole parts between $x$ and $y$.
Therefore, in particular there are three consecutive parts
$S_{i^{\prime}},S_{i^{\prime}+1}$, and $S_{i^{\prime}+2}$ such that the first
has LIS of length $k$, the second has LDS of length $k$, and the third has LIS
of length $k$.

In the first case, we replace $r[2:d-1]$ with LIS of $S_{i^{\prime}}$, the LDS
of $S_{i^{\prime}+1}$, and LIS of $S_{i^{\prime}+2}$. It is straightforward to
verify that we obtain a valid $k$-rollercoaster, and because we remove at most
$2k-4$ elements and add at least $3k$, this creates a longer
$k$-rollercoaster, which is a contradiction. In the second case, we replace
$r[2:\ell]$ with LIS of $S_{i^{\prime}}$ and LDS of $S_{i^{\prime}+1}$. Again,
it is straightforward to verify that we obtain a valid longer
$k$-rollercoaster, because we remove at most $k-2$ elements and add at least
$2k$. Similarly, in the third case, we replace $r[\ell+1:d-1]$ with LDS of
$S_{i^{\prime}+1}$ and LIS of $S_{i^{\prime}+2}$ to obtain a longer
$k$-rollercoaster. Finally, in the fourth case we simply insert LDS of
$S_{i^{\prime}+1}$ between $x$ and $y$ to obtain a longer $k$-rollercoaster. ∎

After the initial preprocessing phase we apply dynamic programming. For $1\leq
i\leq k$, we say that a subsequence of $S$ (not necessarily contiguous) is a
$(k,i)_{+}$-rollercoaster if it ends with an increasing run of length exactly
$i$ when $i<k$ and at least $k$ when $i=k$, while every other run is of length
at least $k$. Additionally, we consider $k$-rollercoaster ending with a
decreasing run as $(k,1)_{+}$-rollercoaster. We want to construct, for every
$1\leq i\leq k$ and $1\leq j\leq n$, a longest $(k,i)_{+}$-rollercoaster
ending with $S[j]$. To this end we calculate $M_{+}[j,i]$, the position in $S$
of the predecessor of $S[j]$ in such a $(k,i)_{+}$-rollercoaster, and
$L_{+}[j,i]$, the length of the respective $(k,i)_{+}$-rollercoaster. A
$(k,i)_{-}$-rollercoaster is defined similarly, except that the last run
should be decreasing, and we also calculate the values $M_{-}[j,i]$ and
$L_{-}[j,i]$, defined similarly to the above and corresponding to such a
$(k,i)_{-}$-rollercoaster. We only describe in detail how to compute
$M_{+}[j,i]$ and $L_{+}[j,i]$, as $M_{-}[j,i]$ and $L_{-}[j,i]$ are computed
analogously. The computation proceeds from left to right, that is, we iterate
over the parts $S_{1},S_{2},\ldots$ and compute, for every element $S[j]$ of
the current part $S_{\ell}$, the values of $M_{+}[j,i]$ and $L_{+}[j,i]$ for
every $1\leq i\leq k$. See Algorithm 2 for a high-level overview of the
algorithm.

Algorithm 2 Computing the length of a longest $k$-rollercoaster

1:Find an alternating $k$-decomposition $S_{1},\ldots,S_{m}$ of $S$.

2:for $1\leq\ell\leq m$ do

3: Merge the $k$ monotone subsequences constituting $S_{\ell}$ to obtain a
single sorted list $P_{\ell}$.

4:for $1\leq\ell\leq m$ do

5: $\triangleright$ For each $S[j]$ in $S_{\ell}$ and $1\leq i\leq k$, we
compute the following:

6: $M_{+}[j,i]$: position in $S$ of the predecessor of $S[j]$ in its
$(k,i)_{+}$-rollercoaster

7: $L_{+}[j,i]$: length of the respective $(k,i)_{+}$-rollercoaster

8: for $2\leq i\leq k$ do

9: for $1\leq d\leq 4$ and each $S[j]\in S_{\ell}$ in the order of their
occurrences in $P_{\ell}$ do

10: Find $M^{d}_{+}[j,i]$ and $L^{d}_{+}[j,i]$.

11: for each $S[j]\in S_{\ell}$ do

12: $L_{+}[j,i]\leftarrow\max\\{L^{d}_{+}[j,i]:1\leq d\leq 4\\}$

13: Set $M_{+}[j,i]$ so that it corresponds to $L_{+}[j,i]$.

14: Compute, for each $S[j]\in S_{\ell}$, $L_{-}[j,i]$ and $M_{-}[j,i]$ with a
similar approach.

15: repeat 4 times

16: for each $S[j]\in S_{\ell}$ do

17: $L_{+}[j,1]\leftarrow\max\\{L_{-}[j,k],1\\}$

18: $M_{+}[j,1]\leftarrow M_{-}[j,k]$ if $L_{-}[j,k]>0$ and $0$ otherwise

19: for $2\leq i\leq k$ do

20: for each $S[j]\in S_{\ell}$ in the order of their occurrences in
$P_{\ell}$ do

21: Find $M^{\prime}_{+}[j,i]$, $L^{\prime}_{+}[j,i]$ using decomposition of
$S_{\ell}$ into $k$ monotone sequences.

22: for each $S[j]\in S_{\ell}$ do

23: $L_{+}[j,i]\leftarrow\max\\{L_{+}[j,i],L^{\prime}_{+}[j,i]\\}$

24: Update $M_{+}[j,i]$ so that it corresponds to $L_{+}[j,i]$.

25: Update, for each $S[j]\in S_{\ell}$, $L_{-}[j,i]$ and $M_{-}[j,i]$ with a
similar approach.

26:return $\max\\{\max\\{L_{-}[j,k],L_{+}[j,k]\\}:1\leq j\leq n\\}$

When we begin computing the arrays $M_{+}[\cdot,i]$, $L_{+}[\cdot,i]$,
$M_{-}[\cdot,i]$ and $L_{-}[\cdot,i]$, for $2\leq i\leq k$, corresponding to
all $S[j]\in S_{\ell}$, we have already computed $M_{+}[j^{\prime},1]$,
$M_{+}[j^{\prime},2],\ldots,$ $M_{+}[j^{\prime},k]$ and $L_{+}[j^{\prime},1]$,
$L_{+}[j^{\prime},2],\ldots,$ $L_{+}[j^{\prime},k]$, as well as
$M_{-}[j^{\prime},1]$, $M_{-}[j^{\prime},2],\ldots,$ $M_{-}[j^{\prime},k]$ and
$L_{-}[j^{\prime},1]$, $L_{-}[j^{\prime},2],\ldots,$ $L_{-}[j^{\prime},k]$,
for every $S[j^{\prime}]\in S_{\ell^{\prime}}$ such that $\ell^{\prime}<\ell$.

We start with computing the values $M_{+}[\cdot,i]$, $L_{+}[\cdot,i]$,
$M_{-}[\cdot,i]$ and $L_{-}[\cdot,i]$, for $2\leq i\leq k$, assuming that the
predecessor $S[j^{\prime}]$ of $S[j]$ in its corresponding rollercoaster
belongs to $S_{\ell-d}$, for some $1\leq d\leq 4$. In such case the longest
rollercoaster ending at $S[j^{\prime}]$ has been already correctly determined
and the computation is quite straightforward. If $S[j^{\prime}]$ also belongs
to $S_{\ell}$, we must be more careful to guarantee that the longest
rollercoaster ending at $S[j^{\prime}]$ is already known. We proceed in
iterations. In the $t^{\text{th}}$ iteration, we guarantee to compute the
values such that at most $t$ runs of the corresponding rollercoaster contain
elements from $S_{\ell}$. By Proposition 1, four iterations are enough. In a
single iteration, we start with computing the initial values $M_{+}[\cdot,1]$,
$L_{+}[\cdot,1]$, $M_{-}[\cdot,1]$ and $L_{-}[\cdot,1]$ corresponding to
$S[j]$ being the first element of its run. These values can be simply copied
from the already known $M_{-}[\cdot,k]$, $L_{-}[\cdot,k]$, $M_{+}[\cdot,k]$
and $L_{+}[\cdot,k]$ corresponding to $S[j]$ being the last element of a
rollercoaster with less than $t$ runs containing elements from $S_{\ell}$ (or
set to 1 corresponding to $S[j]$ being the only element in the rollercoaster).
This is correct because a $(k,1)_{+}$-rollercoaster is actually either a
$(k,k)_{-}$-rollercoaster or a sequence consisting of a single element. Then,
we calculate the values $M_{+}[\cdot,i]$, $L_{+}[\cdot,i]$, $M_{-}[\cdot,i]$
and $L_{-}[\cdot,i]$, for $2\leq i<k$, such that the predecessor
$S[j^{\prime}]\in S_{\ell}$ belongs to the same run as $S[j]$. By performing
the calculation for $i=2,3\ldots,k-1$ in this order we guarantee that the
longest rollercoaster ending at the predecessor $S[j^{\prime}]\in S_{\ell}$ is
already known for all $S[j]\in S_{\ell}$, but the computation is still not
completely trivial and requires a different approach depending on whether
$S_{\ell}$ was decomposed into at most $k$ increasing, respectively
decreasing, subsequences. Finally, we extend this to $i=k$.

###  $M_{+}[j,i]$ belongs to $S_{\ell-d}$ for some $1\leq d\leq 4$.

We process $S_{\ell-d}$ to identify some candidates, denoted $M^{d}_{+}[j,i]$
and $L^{d}_{+}[j,i]$, for $M_{+}[j,i]$ and $L_{+}[j,i]$, respectively, for
every $S[j]\in S_{\ell}$. The idea is to compute these candidates in the order
in which the elements $S[j]$ occur on the sorted list $P_{\ell}$. So, let us
consider $P_{\ell}$ and $P_{\ell-d}$. For each element $S[j]$ in the current
part we want to identify a longest $(k,i-1)_{+}$-rollercoaster ending in
$S_{\ell-d}$ with an element less than $S[j]$. Thus, as $P_{\ell-d}$ is
increasing, for every element of the current part we need to consider all
elements in a prefix of $P_{\ell-d}$. Also, if $S[j^{\prime}]$ is to the right
of $S[j]$ in $P_{\ell}$, that is, $S[j^{\prime}]\geq S[j]$, then the prefix of
$P_{\ell-d}$ that we need to consider to compute $M^{d}_{+}[j^{\prime},i]$ is
at least as long as the prefix that we need to consider to compute
$M^{d}_{+}[j,i]$. Therefore, we can use two pointers to sweep through
$P_{\ell}$ and $P_{\ell-d}$ from left to right, and obtain the information
needed to compute $M^{d}_{+}[j,i]$ and $L^{d}_{+}[j,i]$, for every $S[j]\in
S_{\ell}$. At the beginning the pointers point to the first element of
$P_{\ell}$ and $P_{\ell-d}$, respectively. Say that the current element in
$P_{\ell}$ and $P_{\ell-d}$ is $S[j]$ and $S[h]$, respectively (we update
indices $j$ and $h$ along with the pointers). We keep moving forward the
pointer corresponding to $S[h]$ until we find an element $S[h]>S[j]$. Then we
set $M^{d}_{+}[j,i]=h^{\prime}$ and $L^{d}_{+}[j,i]=L_{+}[h^{\prime},i]+1$,
where $S[h^{\prime}]$ is an element occurring earlier than $S[h]$ in
$P_{\ell-d}$ with the largest value of $L_{+}[h^{\prime},i-1]$. The element
$S[h^{\prime}]$ is maintained as we move from left to right in $P_{\ell-d}$.
Then we proceed to the next element in $P_{\ell}$. Overall, computing
candidates $M^{d}_{+}[j,i]$ and $L^{d}_{+}[j,i]$, for every $S[j]\in
S_{\ell}$, takes $O(|S_{\ell-d}|+|S_{\ell}|)$ time.

###  $M_{+}[j,i]$ belongs to $S_{\ell}$ decomposed into $k$ increasing
subsequences.

Recall that we have already computed $M_{+}[j^{\prime},i^{\prime}]$ and
$L_{+}[j^{\prime},i^{\prime}]$ for every $i^{\prime}<i$ and $S[j^{\prime}]\in
S_{\ell}$, and the goal is to identify candidates, denoted
$M^{\prime}_{+}[j,i]$ and $L^{\prime}_{+}[j,i]$, for $M_{+}[j,i]$ and
$L_{+}[j,i]$, respectively, for every $S[j]\in S_{\ell}$. Consider the
decomposition of $S_{\ell}$ into $k$ increasing subsequences
$I_{1},I_{2},\ldots,I_{k}$. The elements of every sequence are increasing
w.r.t. their values and w.r.t their positions in $S$. Consider an element
$S[j]\in I_{a}$ and $1\leq b\leq k$ (possibly $a=b$). The elements of $I_{b}$
that can be the predecessor of $S[j]$ in a $(k,i)_{+}$-rollercoaster (that is,
possible candidates for $M_{+}[j,i]$) are both less w.r.t. value and w.r.t.
position in $S$. Thus, these elements form a prefix of $I_{b}$, and for every
$S[j]\in I_{a}$ and $1\leq b\leq k$ we want to maximise $L_{+}[h^{\prime},i]$
over all $S[h^{\prime}]$ in such a prefix. As in the previous case, we can use
two pointers to sweep through $I_{a}$ and $I_{b}$ and compute, for every
$S[j]\in I_{a}$, the element $S[h^{\prime}]\in I_{b}$ that could precede
$S[j]$ in a $(k,i)_{+}$-rollercoaster with the largest value of
$L_{+}[h^{\prime},i-1]$. Finally, we set $M^{\prime}_{+}[j,i]$ and
$L^{\prime}_{+}[j,i]$ to correspond to the largest such value among all $1\leq
b\leq k$. Overall, computing the candidates $M^{\prime}_{+}[j,i]$ and
$L^{\prime}_{+}[j,i]$, for every $S[j]\in S_{\ell}$, takes $O(k|S_{\ell}|)$
time.

###  $M_{+}[j,i]$ belongs to $S_{\ell}$ decomposed into $k$ decreasing
subsequences.

This is the most complicated case. Recall that the decomposition into $k$
decreasing subsequences $D_{1},D_{2},\ldots,D_{k}$ was obtained with Algorithm
1. In more detail, $D_{a}$ consists of elements assigned to $R[a]$ throughout
the execution of the algorithm. Thus, if $S[j]\in D_{a}$ then the predecessor
of $S[j]$ in a sought longest $(k,i)_{+}$-rollercoaster, denoted
$S[j^{\prime}]$, must belong to $D_{b}$ for some $1\leq b<a$. Indeed,
Algorithm 1 first processes $S[j^{\prime}]$ and then $S[j]$, so if
$S[j^{\prime}]\in D_{b}$ then $R[b]\leq S[j^{\prime}]$ when processing $S[j]$
and consequently $S[j^{\prime}]<S[j]$ implies that $S[j]$ is assigned to
$R[a]$ with $a>b$. So, we first compute the candidates $M^{\prime}_{+}[j,i]$
and $L^{\prime}_{+}[j,i]$ for every $S[j]\in D_{1}$, then for every $S[j]\in
D_{2}$, and so on. That is, consider a decreasing subsequence $D_{a}$ and
suppose that we have already computed the desired result for all elements in
$D_{1},D_{2},\ldots,D_{a-1}$. Note that at this point we have already
computed, for every $S[j]\in D_{1}\cup\ldots\cup D_{a-1}$, the values of
$M^{d}_{+}[j,i]$ and $L^{d}_{+}[j,i]$, for $1\leq d\leq 4$, as well as the
values $M^{\prime}_{+}[j,i]$ and $L^{\prime}_{+}[j,i]$ corresponding to the
current iteration. Thus, we are already able to set $M_{+}[j,i]$ and
$L_{+}[j,i]$ by choosing the option that maximises the length of the
corresponding $(k,i)_{+}$-rollercoaster, which is important when extending
this case to $i=k$.

Consider an element $S[j]\in D_{a}$ and $1\leq b<a$. The elements of $D_{b}$
that can be the predecessor of $S[j]$ in a $(k,i)_{+}$-rollercoaster (that is,
possible candidates for $M_{+}[j,i]$) are both less w.r.t. value and w.r.t.
position in $S$, similarly as in the previous case. The difference is that now
these elements form contiguous subsequence $X$ of $D_{b}$ that is not
necessarily a prefix. The first element of $X$ can be found by searching for
the first element with sufficiently small value, while its last element can be
found by searching the last element with sufficiently small position (note
that $X$ might be empty). Let $S[j^{\prime}]$ be the next element after $S[j]$
in $D_{a}$, and $Y$ be its corresponding contiguous subsequence of $D_{b}$
consisting of possible predecessors in a $(k,i)_{+}$-rollercoaster. Clearly,
$S[j]>S[j^{\prime}]$ while $j<j^{\prime}$. Thus, the first element of $Y$ is
either the same as the first element of $X$ or occurs after the first element
of $X$ in $D_{a}$, while the last element of $Y$ is either the same as the
last element of $X$ or occurs after the last element of $X$ in $D_{a}$
(assuming that both $X$ and $Y$ are non-empty). Thus, we sweep through $D_{a}$
while maintaining the current contiguous subsequence $X$ of $D_{b}$
corresponding to the possible predecessors of the current $S[j]\in D_{a}$.
This requires the following tool.

######  Lemma 2 ([11]).

There is a data structure that maintains a list of elements under the
following operations: pop an element from the front, push an element in the
back, and return the maximum element in the current list, each in $O(1)$ time.

When processing the current element $S[j]\in D_{a}$ we maintain the first
element $S[f]\in D_{b}$ such that $S[f]<S[j]$ and the last element $S[\ell]\in
D_{b}$ such that $\ell<j$. Then $X$ consists of all elements between $S[f]$
and $S[\ell]$ in $D_{b}$ (inclusive), and is maintained in a structure from
Lemma 2 storing the lengths of their corresponding $(k,i)_{+}$-rollercoaster,
that is, the already known value of $L_{+}[\cdot,i-1]$. This allows us to
extract the element $S[j^{\prime}]\in X$ with the largest value of
$L_{+}[j^{\prime},i-1]$, and set $M^{\prime}_{+}[j,i]=j^{\prime}$ and
$L^{\prime}_{+}[j,i]=L_{+}[j^{\prime},i-1]+1$ in constant time, while updating
$f$ and $\ell$ takes amortised constant time. Overall, computing the
candidates $M^{\prime}_{+}[j,i]$ and $L^{\prime}_{+}[j,i]$, for every $S[j]\in
S_{\ell}$, takes $O(k|S_{\ell}|)$ time.

### Case $i=k.$

To compute $M_{+}[j,k]$ and $L_{+}[j,k]$, we first use exactly the same
approach as before for $i=k$, so consider the values of $M_{+}[\cdot,k-1]$ and
$L_{+}[\cdot,k-1]$. But this only allows us to compute the length of a longest
$(k,k)_{+}$-rollercoaster with the last run of length exactly $k$. To extend
this to arbitrary $(k,k)_{+}$-rollercoasters with the last run of length
greater than $k$ we additionally run the same algorithm but instead of looking
at $M_{+}[\cdot,k-1]$ and $L_{+}[\cdot,k-1]$ we use $M_{+}[\cdot,k]$ and
$L_{+}[\cdot,k]$, including the values already computed in this extra step in
the third case. The reason why this works is that, due to the order in which
we consider the elements of $S_{\ell}$, at the moment when we compute the
length of a longest $(k,k)_{+}$-rollercoaster ending with $S[j]$, and which
may have more than $k$ elements in the final run, we have already computed the
length of a longest $(k,k)_{+}$-rollercoaster ending with any element
$S[j^{\prime}]$ which may be a predecessor of $S[j]$ on the respective
$(k,k)_{+}$-rollercoaster.

### Conclusion.

With these final remarks, our algorithm is completely described. It only
remains to find the element $S[j]$ for which $\max\\{L_{-}[j,k],L_{+}[j,k]\\}$
is maximum. The correctness follows from the comments made throughout its
description. To compute the complexity, it is enough to note that each part
$S_{\ell}$ of the partition of $S$ is processed in $O(k|S_{\ell}|)$ time, for
each $2\leq i\leq k$. Adding this up, we get that the total complexity of our
algorithm is $O(nk^{2})$.

######  Theorem 4.

For every sequence $S[1:n]$ and $k\geq 3$, the length of a longest
$k$-rollercoaster in $S$ can be found in $O(nk^{2})$-time.

##  4 Computing a Longest $k$-Rollercoaster in $O(n\log^{2}{n})$-time

Before we describe our algorithm, we introduce two preliminary procedures.
Firstly, we introduce the definition of an anti-Monge matrix and the algorithm
for finding the maximum in every column of such a matrix. Secondly, we
describe the algorithm for finding LIS in contiguous subsequences of the input
sequence. Finally, we describe the algorithm computing a longest
$k$-rollercoaster in this sequence, using the previously developed tools as
black boxes.

### Monge matrices.

Let $A$ be an $n\times n$ matrix, and $A[i,j]$ denote its element in the
$i^{\text{th}}$ row from the top and the $j^{\text{th}}$ column from the left.
$A$ is Monge (respectively, anti-Monge) if, for every $1\leq i<j\leq n$ and
$1\leq k<\ell\leq n$, the Monge equality holds, namely $A[i,k]+A[j,\ell]\leq
A[i,\ell]+A[j,k]$ (respectively, $A[i,k]+A[j,\ell]\geq A[i,\ell]+A[j,k]$). An
$n\times n$ falling staircase anti-Monge matrix is a matrix with blanks such
that for every blank all elements below and to the left are blanks, and the
anti-Monge inequality holds whenever the four concerned elements are non-
blank. Similarly, an $n\times n$ reverse falling staircase anti-Monge matrix
is a matrix with blanks such that for every blank all elements above and to
the right are blanks, and the anti-Monge inequality holds whenever the four
concerned elements are non-blank. Finally, an $n\times n$ matrix $A$ is
totally monotone if, for every $1\leq i<j\leq n$ and $1\leq k<\ell\leq n$,
$A[i,k]\leq A[i,\ell]$ implies $A[j,k]\leq A[j,\ell]$.

0 | 1 | 2 | 2 | 2
---|---|---|---|---
-1 | 0 | 1 | 1 | 2
-2 | -1 | 0 | 1 | 2
-3 | -2 | -1 | 0 | 1
-4 | -3 | -2 | -1 | 0

|  |  |  |
---|---|---|---|---
4 |  |  |  |
3 | 2 |  |  |
2 | 1 |  |  |
4 | 4 | 2 | 6 |

| 1 | 2 | 2 | 2
---|---|---|---|---
|  |  | 1 | 2
|  |  | 1 | 2
|  |  |  | 1
|  |  |  |

Figure 3: Anti-Monge matrix, reverse falling staircase anti-Monge matrix, and
falling staircase anti-Monge matrix.

Let us now recall some basic facts regarding Monge matrices.

######  Observation 1.

Adding the same value to every element in a row (or a column) of an anti-Monge
matrix results in an anti-Monge matrix.

######  Observation 2.

To check if an array is anti-Monge it is sufficient to check if every
contiguous $2\times 2$ submatrix is anti-Monge.

The following lemma follows from the well-known SMAWK algorithm [2].

######  Lemma 3 (Lemma 3.3 in Aggarwal et al. [1]).

All row maxima in a reverse falling staircase totally monotone matrix can be
found in $O(n)$ time.

By transposing the matrix and observing that being anti-Monge implies being
totally monotone we obtain the following.

######  Corollary 1.

All column maxima in a falling staircase anti-Monge matrix can be found in
$O(n)$ time.

### LIS-in-range queries.

Let $S[1:n]$ be the input sequence. Define $M$ as an $(n+1)\times(n+1)$ matrix
with $0$-indexed rows and columns, such that $M[i,j]$ is the length of LIS in
$S[i+1:j]$ for $i<j$ and $M[i,j]=j-i$ otherwise (the anti-Monge matrix in
Figure 3 is such a matrix for the sequence $(3,4,1,2)$). As hinted by our
example, this matrix turns out to have a rather special structure as observed
by Tiskin [19]. We describe this structure in the following.

Let $S^{\prime}$ be the sequence obtained by sorting $S$ (recall that $S$
consists of distinct elements), and observe that LIS of $S$ is the same as a
longest common subsequence (LCS, for short) of $S$ and $S^{\prime}$. Thus, we
can think that $M[i,j]$ is LCS of $S^{\prime}$ and $S[i+1:j]$. As such, the
following result can be shown (see [19] and the references therein).

######  Lemma 5.

$M$ is anti-Monge.

Our algorithm needs to access the elements of $M$. Since the matrix contains
$(n+1)^{2}$ elements, it is too large to be explicitly stored in memory.
Fortunately, Tiskin also showed how to create in $O(n\log^{2}{n})$ time an
$O(n)$-space implicit representation of $M$ that allows us to obtain any of
its elements in $O(\log{n})$ time [19]. Before we present the internals of
this representation, we need to introduce some additional definitions
illustrated in Figure 4.

######  Definition 1.

Let $A$ be any $n\times n$ matrix. Its distribution matrix $A^{\Sigma}$ is an
$(n+1)\times(n+1)$ matrix defined by $A^{\Sigma}[x,y]=\sum_{i\geq
x,j<y}A[i,j]$, for every $1\leq x\leq n+1,1\leq y\leq n+1$.

######  Definition 2.

A permutation matrix is a square matrix that has exactly one $1$ in every row
and column, and the remaining elements are equal to $0$.

0 | 1 | 0
---|---|---
1 | 0 | 0
0 | 0 | 1

0 | 1 | 2 | 3
---|---|---|---
0 | 1 | 1 | 2
0 | 0 | 0 | 1
0 | 0 | 0 | 0

Figure 4: A permutation matrix $A$ and its distribution matrix $A^{\Sigma}$.

Now, we can provide the final ingredients of the construction. For two strings
$w_{1}$ and $w_{2}$ of length $d$, Tiskin defines in [19] a
$(2d+1)\times(2d+1)$ matrix $L$ in the following way. Let $w_{2}^{\prime}$ be
the string equal to $?^{d}w_{2}?^{d}$, whose positions are indexed from
$-(d-1)$ to $2d$. The rows of $L$ are indexed from $-d$ to $d$, while the
columns of $L$ are indexed from $0$ to $2d$. The elements of $L$ are defined
by $L[i,j]=\text{LCS}(w_{1},w_{2}^{\prime}[i+1:j])$ if $j>i$, and $L[i,j]=j-i$
otherwise. In this definition, it is assumed that $?$ matches any character.
If $w_{2}$ is the input sequence $S$ and $w_{1}$ is $S^{\prime}$ then, for
$0\leq i,j\leq n$ we have $L[i,j]=M[i+1,j+1]$. Tiskin proved (Theorem 4.10 in
[19]) that there exists $2d\times 2d$ permutation matrix $P$ such that
$L[i,j]$ = $j-i-P^{\Sigma}[i,j]$. Furthermore, he provided an
$O(n\log^{2}n)$-time algorithm that finds all the non-zero entries of $P$
(Algorithm 8.2 in [19]). Having all the non-zero entries of $P$ we can apply a
dominance counting structure of Chazelle [7] that can be constructed in
$O(n\log n)$ time, uses $O(n)$ space, and calculates $P^{\Sigma}[i,j]$ and
hence also $M[i+1,j+1]$ in $O(\log n)$ time. Summarising, in $O(n\log^{2}n)$
time we obtain a structure that returns any element of $M$ in $O(\log n)$
time. We similarly obtain a matrix storing the length of LDS of every
$S[i+1:j]$.

### Description of the algorithm.

Let $S[1:n]$ be the input sequence. For every $1\leq x\leq n$, let
$\mathsf{res}[x]$ be the length of a longest $k$-rollercoaster in $S[1:x]$,
and $\mathsf{inc}[x]$ (respectively, $\mathsf{dec}[x]$) be the length of a
longest $k$-rollercoaster in $S[1:x]$ with the last run increasing
(respectively, decreasing). Note that we do not require that these
$k$-rollercoasters contain $S[x]$. Then,
$\mathsf{res}[x]=\max\\{\mathsf{dec}[x],\mathsf{inc}[x]\\}$, for $1\leq x\leq
n$. Firstly, we introduce two structural lemmas.

######  Lemma 6.

Let $A$ be a $k$-rollercoaster in $S[1:i]$ with the last run decreasing, and
$r$ be an increasing subsequence in $S[i:n]$ such that ${\lvert r\rvert}\geq
k$. Then there exists a $k$-rollercoaster in $S[1:n]$ of length at least
${\lvert A\rvert}+{\lvert r\rvert}-1$ with the last run increasing.

###### Proof.

Let $A^{\prime}$ be the sequence consisting of all elements from both $A$ and
$r$. Recall that a sequence is a $k$-rollercoaster if every run has length at
least $k$. In order to show that $A^{\prime}$ is a $k$-rollercoaster with last
run increasing we need to consider three cases: the first element of $r$ is
the last element of $A$, the first element of $r$ is greater than the last
element of $A$, and the first element of $r$ is less than the last element of
$A$.

In the first case, all runs in $A^{\prime}$ but the last are the same as in
$A$, and the last run is equal to $r$. Since $A$ is a $k$-rollercoaster and
${\lvert r\rvert}\geq k$ we conclude that $A^{\prime}$ is a $k$-rollercoaster.
$A$ and $r$ have one common element, so ${\lvert A^{\prime}\rvert}={\lvert
A\rvert}+{\lvert r\rvert}-1$.

In the second case, all runs in $A^{\prime}$ but the last are also the same as
in $A$, and the last run consists of the last element of $A$ and $r$. Again we
conclude that $A^{\prime}$ is a $k$-rollercoaster. Since $A$ and $r$ have no
common elements, ${\lvert A^{\prime}\rvert}={\lvert A\rvert}+{\lvert
r\rvert}$.

In the third case, all runs in $A^{\prime}$ but the last two are the same as
in $A$. The second-to-last run in $A^{\prime}$ consist of the last run of $A$
and the first element of $r$, and the last run in $A^{\prime}$ is $r$. Hence,
$A^{\prime}$ is a $k$-rollercoaster. Since $A$ and $r$ have no common
elements, ${\lvert A^{\prime}\rvert}={\lvert A\rvert}+{\lvert r\rvert}$. ∎

######  Lemma 7.

Consider a longest $k$-rollercoaster in $S[1:n]$ with the last run increasing
(respectively, decreasing), and let $r$ be its last run with the first element
$S[i]$. Then $r$ is a longest increasing (respectively, decreasing)
subsequence in $S[i:n]$.

###### Proof.

By contradiction. Let $A$ be a longest $k$-rollercoaster from the statement of
the lemma, and suppose that there exists a longer increasing sequence
$r^{\prime}$ in $S[i:n]$. Let $A^{\prime}$ be the prefix of $A$ ending at
$S[i]$. Observe that ${\lvert A^{\prime}\rvert}={\lvert A\rvert}-{\lvert
r\rvert}+1$. Then by Lemma 6 there exists a $k$-rollercoaster in $S$ of length
at least ${\lvert A^{\prime}\rvert}+{\lvert r^{\prime}\rvert}-1={\lvert
A\rvert}-{\lvert r\rvert}+{\lvert r^{\prime}\rvert}>{\lvert A\rvert}$. ∎

The above lemmas allow us to obtain the formula for calculating the arrays
$\mathsf{inc}$ and $\mathsf{dec}$. Recall that $M[i,j]$ is the length of LIS
in $S[i+1:j]$. Let $M^{\prime}$ be the matrix obtained from $M$ by replacing
all elements less than $k$ by $-\infty$, and let $Z(j,j^{\prime})$ be the set
of indices $j\leq i\leq j^{\prime}$ such that length of LIS in
$S[i:j^{\prime}]$ is at least $k$ (or, in other words,
$M^{\prime}[i-1,j^{\prime}]\neq-\infty$).

######  Proposition 2.

For every $1\leq x\leq n$, the following holds:

$\displaystyle\mathsf{inc}^{\prime}[x]=\max\\{\mathsf{dec}[i]+M^{\prime}[i-1,x]-1:i\in
Z(1,x)\\},\mathsf{inc}[x]=\max\\{\mathsf{inc}^{\prime}[x],M^{\prime}[0,x]\\}.$

If $Z(1,x)$ is empty then we set $\mathsf{inc}^{\prime}[x]=0$.

###### Proof.

By Lemma 6 we obtain that for every $i\in Z(1,x)$ there exists a
$k$-rollercoaster in $S[1:x]$ with the last run increasing of length at least
$\mathsf{dec}[i]+M^{\prime}[i-1,x]-1$. We conclude that
$\mathsf{inc}^{\prime}[x]$ is less or equal to the length of a longest
$k$-rollercoaster with the last run increasing in $S[1:x]$. Observe that
$M^{\prime}[0,x]$ corresponds to an increasing run of length at least $k$ or
is equal to $-\infty$. We obtain that $\mathsf{inc}[x]$ is less or equal than
the length of a longest $k$-rollercoaster with the last run increasing in
$S[1:x]$.

For the converse, consider a $k$-rollercoaster $A$ with the last run
increasing in $S[1:x]$. If $A$ consists of just a single run then its length
is $M^{\prime}[0,x]$. Otherwise, let $S[i]$ be the first element in the last
run of $A$. Then by Lemma 7 the length of the last run is equal to
$M^{\prime}[i-1,x]$ and the length of $A$ is
$\mathsf{dec}[i]+M^{\prime}[i-1,x]-1$. Overall, the length of $A$ is at most
$\mathsf{inc}[x]$. ∎

Proposition 2 cannot be applied directly if we aim to achieve the announced
$O(n\log^{2}n)$ time complexity, and we need to introduce some auxiliary
definitions. For every $1\leq d\leq x$ we define $\mathsf{inc}_{d}[x]$ as
follows:

$\mathsf{inc}_{d}^{\prime}[x]=\max\\{\mathsf{dec}[i]+M^{\prime}[i-1,x]-1:i\in
Z(1,d-1)\\},\mathsf{inc}_{d}[x]=\max\\{\mathsf{inc}_{d}^{\prime}[x],M^{\prime}[0,x]\\}.$

If $Z(1,d-1)$ is empty then we set $\mathsf{inc}_{d}^{\prime}[x]=0$. In other
words, $\mathsf{inc}_{d}[x]$ is equal to the length of a longest
$k$-rollercoaster in $S[1:x]$ with the last run increasing and starting at an
element $S[i]$ with $i<d$ or LIS of $S[1:n]$ of length at least $k$. Thus,
$\mathsf{inc}_{1}[x]$ is equal to either $0$ or the length of a LIS in
$S[1:x]$. We similarly define $\mathsf{dec}_{d}[x]$.

######  Observation 3.

For every $j>i-k+1$, $\mathsf{inc}_{j}[i]=\mathsf{inc}[i]$.

We describe a function Compute that receives a contiguous subsequence $S[i:j]$
together with the previously calculated arrays $\mathsf{inc}_{i}[i:j]$ and
$\mathsf{dec}_{i}[i:j]$, and returns the arrays $\mathsf{inc}[i:j]$ and
$\mathsf{dec}[i:j]$. To calculate the length of a longest $k$-rollercoaster in
$S[1:n]$ we invoke the function with the whole $S[1:n]$ and the arrays
$\mathsf{inc}_{1}[1:n]$, $\mathsf{dec}_{1}[1:n]$ as arguments, and return the
maximum over the two resulting arrays. Note that $\mathsf{inc}_{1}[1:n]$ and
$\mathsf{dec}_{1}[1:n]$ can be calculated in $O(n\log n)$ time using Algorithm
1.

Let $m=\left\lceil\frac{i+j}{2}\right\rceil$. The main idea of Compute is to
call the function recursively for the left half to calculate
$\mathsf{inc}[i:m-1]$ and $\mathsf{dec}[i:m-1]$. The next step is to calculate
$\mathsf{inc}_{m}[m:j]$ and $\mathsf{dec}_{m}[m:j]$ using tools from the
previous paragraphs (as described below). Finally, we recursively calculate
$\mathsf{inc}[m:j]$ and $\mathsf{dec}[m:j]$. Concatenating the results from
both recursive calls gives us the desired result. This is summarised in
Algorithm 3.

Algorithm 3 Computing the length of a longest $k$-rollercoaster

1:procedure Compute($k$, $S[i:j]$, $\mathsf{inc}_{i}[i:j]$,
$\mathsf{dec}_{i}[i:j]$)

2: if $j-i+2\leq k$ then

3:
$\\{\mathsf{inc}[i:j],\mathsf{dec}[i:j]\\}\leftarrow\\{\mathsf{inc}_{i}[i:j],\mathsf{dec}_{i}[i:j]\\}$

4: return $\\{\mathsf{inc}[i:j],\mathsf{dec}[i:j]\\}$

5: $m\leftarrow\left\lceil\frac{i+j}{2}\right\rceil$

6:
$\\{\mathsf{inc}[i:m-1],\mathsf{dec}[i:m-1]\\}\leftarrow\textsc{Compute}(k,S[i:m-1],\mathsf{inc}_{i}[i:m-1],\mathsf{dec}_{i}[i:m-1])$

7: Compute $\mathsf{inc}_{m}[m:j]$ and $\mathsf{dec}_{m}[m:j]$

8:
$\\{\mathsf{inc}[m:j],\mathsf{dec}[m:j]\\}\leftarrow\textsc{Compute}(k,S[m:j],\mathsf{inc}_{m}[m:j],\mathsf{dec}_{m}[m:j])$

9: return $\\{\mathsf{inc}[i:j],\mathsf{dec}[i:j]\\}$

### Computing $\mathsf{inc}_{m}[m:j]$ and $\mathsf{dec}_{m}[m:j]$.

We only describe how to calculate $\mathsf{inc}_{m}[m:j]$, as
$\mathsf{dec}_{m}[m:j]$ can be computed by a similar approach. Recall the
previously introduced matrix $M^{\prime}$, obtained by replacing values less
than $k$ by $-\infty$ in $M$. Let $A_{\mathsf{inc}}$ be the
$(m-i)\times(j+1-m)$ matrix with rows indexed from $i$ to $m-1$ and columns
indexed from $m$ to $j$ satisfying:

$A_{\mathsf{inc}}[x,y]=\begin{cases}\mathsf{dec}[x]+M^{\prime}[x-1,y]-1&\text{when
}M^{\prime}[x-1,y]\neq-\infty,\\\ \text{blank}&\text{otherwise.}\\\
\end{cases}$

Since we are able to retrieve any element of $M^{\prime}$ in $O(\log n)$ time
using LIS-in-range queries, and the value of $\mathsf{dec}[x]$, for every
$i\leq x\leq m-1$, is already available, each element of $A_{\mathsf{inc}}$
can be calculated in $O(\log n)$ time. Furthermore, we have the following
property.

######  Proposition 3.

$A$ is a falling staircase anti-Monge matrix.

###### Proof.

By Lemma 5 $M$ is an anti-Monge matrix. By Observation 1 this is still the
case if we add the same value to all elements in the same row.

To prove that $A$ is a falling staircase matrix consider a non-blank element
$A[i,j]$. Then $M[i,j]\geq k$. But this implies $M[i-1,j]\geq k$ and
$M[i,j+1]\geq k$ (as long as $i>1$ and $j<n$), so all elements above and to
the right are also non-blank as required. ∎

######  Proposition 4.

For every $m\leq\ell\leq j$, $\mathsf{inc}_{m}[\ell]$ is equal to either
$\mathsf{inc}_{i}[\ell]$ or the maximum in the $\ell^{\text{th}}$ column of
$A$.

###### Proof.

For every $m\leq\ell\leq j$, $\mathsf{inc}_{m}[\ell]$ is equal to either
$\mathsf{inc}_{i}[\ell]$ or
$\max\\{\mathsf{dec}[j]+M^{\prime}[j-1,\ell]-1:j\in Z(i,m-1)\\}$. However, the
latter is exactly the maximum in the $\ell^{\text{th}}$ column of $A$. ∎

######  Lemma 4.

We can compute $\mathsf{inc}_{m}[m:j]$ and $\mathsf{dec}_{m}[m:j]$ in
$O((j-i+1)\log{n})$ time.

###### Proof.

By Proposition 4 computing $\mathsf{inc}_{m}[m:j]$ reduces to finding all the
column maxima in $A$. Since $A$ is a falling staircase anti-Monge matrix, we
can use the algorithm from Corollary 1. Access to any element of $A$ requires
$O(\log n)$ time, so in total we obtain $O((j-i+1)\log n)$ time complexity. ∎

We can now state with the main result of this section.

######  Theorem 8.

For every sequence $S[1:n]$ and $k\geq 3$, the length of a longest
$k$-rollercoaster in $S$ can be found in $O(n\log^{2}{n})$ time.

###### Proof.

The algorithm needs $O(n\log^{2}{n})$ preprocessing time to construct the LIS-
in-range (and LDS-in-range) structure. We compute $\mathsf{inc}_{1}[1:n]$ and
$\mathsf{dec}_{1}[1:n]$ in $O(n\log n)$ time using Algorithm 1. Then, we call
the recursive function Compute. By Lemma 4 a call of the function on $S[i:j]$
takes $O((j-i+1)\log n)$ time, so its running time is described by the
recurrence $T(n)=2T(n/2)+O(n\log n)$ that solves to $O(n\log^{2}n)$. Thus, the
overall time complexity is $O(n\log^{2}{n})$. ∎

##  5 Constructing a Longest $k$-Rollercoaster

In this section we briefly discuss how to construct a longest rollercoaster
for both algorithms.

### For the $O(nk^{2})$ algorithm.

In the respective algorithm, for each $2\leq i\leq k$, and for each element
$S[j]$, we compute the predecessor of $S[j]$ on a longest (not necessarily
contiguous) subsequence of $S$ ending with $S[j]$ and with every run of length
at least $k$, except for the last run, which has only $i$ elements if $i<k$
and at least $k$ elements if $i=k$. If, together with this predecessor, we
store also the length of the last run in the respective subsequence of $S$, we
can trace the whole sequence back. Indeed, the predecessor gives us the
information what element should we list before $S[j]$ in the subsequence. The
length of the run gives us information on the length of the run ending with
the predecessor of $S[j]$, so we know where we should look in our data
structures for the predecessor of $S[j]$. For some $i$ and $j$, tracing back a
longest (not necessarily contiguous) subsequence of $S$ ending with $S[j]$ and
with every run of length at least $k$, except for the last run, which has only
$i$ elements if $i<k$ and at least $k$ elements if $i=k$, takes, clearly,
$O(n)$ time, provided that we have the information described above.

In the end, we will only need to trace back a longest (not necessarily
contiguous) subsequence of $S$ ending with some element $S[j]$ and with every
run of length at least $k$. Given that we also compute the length of a longest
(not necessarily contiguous) subsequence of $S$ ending with each $S[j]$ and
with every run of length at least $k$, we can select in $O(n)$ time the ending
element of the subsequence we need to trace back.

In conclusion, once the $O(nk^{2})$ time algorithm for computing the length of
a longest $k$-rollercoaster is executed, we can actually compute the
respective $k$-rollercoaster in $O(n)$ additional time.

### For the $O(n\log^{2}n)$ algorithm.

In order to retrieve the elements of a longest $k$-rollercoaster we need to
extend our algorithm to maintain global arrays
$Pred_{\mathsf{inc}}[1,\ldots,n]$ and $Pred_{\mathsf{dec}}[1,\ldots,n]$.
Elements of these arrays are computed during the calculations of
$\mathsf{inc}_{m}[m:j]$ and $\mathsf{dec}_{m}[m:j]$ as follows. Initially they
are equal to $-1$. After execution of the algorithm we demand that
$Pred_{\mathsf{inc}}$ satisfies the following: for every $1\leq i\leq n$ we
have that
$\mathsf{inc}[i]=\mathsf{dec}[Pred_{\mathsf{inc}}[i]]+M^{\prime}[Pred_{\mathsf{inc}}[i]-1,i]-1$
if $Pred_{\mathsf{inc}}[i]\neq-1$ and
$\mathsf{inc}[i]=\max\\{0,M^{\prime}[0,i]\\}$ otherwise, and similarly for
$Pred_{\mathsf{dec}}$. It is straightforward to augment the algorithm from
Corollary 1 to obtain such information.

We retrieve the elements of a longest $k$-rollercoaster from the last one to
the first one. Recall that a longest $k$-rollercoaster has the length equal to
$\max\\{\mathsf{inc}[n],\mathsf{dec}[n]\\}$. We focus on how to obtain a
longest $k$-rollercoaster $R$ of length $\mathsf{inc}[n]$ with last run
increasing (so, assume, w.l.o.g., that $\mathsf{inc}[n]>\mathsf{dec}[n]$); the
procedure is similar for $\mathsf{dec}[n]$ and the last run decreasing.

Observe that if $\mathsf{inc}[n]$ is equal to the length of LIS in the input
sequence, we can obtain the elements of $R$ by Algorithm 1 in $O(n\log{n})$
time. Otherwise, there exists $i<n$ such that
$\mathsf{inc}[n]=\mathsf{dec}[i]+M[i-1,n]-1$. The value $i$ is stored in
$Pred_{\mathsf{inc}}[n]$. In this case, we construct $R$ by finding
recursively a longest $k$-rollercoaster associated with $\mathsf{dec}[i]$ and
concatenating it with LIS in $S[i:n]$. This holds because, by Lemma 7 the last
run of $R$ is a LIS in $S[i:n]$. Obtaining LIS in $S[i:n]$ can be done in
$O((n-i)\log n)$ time.

Thus, in general, we will need to compute a series of LISs and LDSs on the
ranges $S[n_{i-1}:n_{i}]$, for $1\leq i\leq m$, where $m$ is the number of
runs in a longest $k$-rollercoaster, $n_{m}=n$ and $n_{0}=1$. Moreover,
$n_{i-1}=Pred_{\mathsf{inc}}[n_{i}]$, if the $i^{\text{th}}$ run of the
rollercoaster is increasing and $n_{i-1}=Pred_{\mathsf{dec}}[n_{i}]$, if the
$i^{\text{th}}$ run of the rollercoaster is decreasing. Obtaining the LIS in
$S[n_{i-1}:n_{i}]$ can be done in $O((n_{i}-n_{i-1}+1)\log{n})$ time.

Adding up the time needed to compute LIS or LDS for each of these ranges we
get $O(n\log{n})$ total time needed to obtain elements of a longest
$k$-rollercoaster.

##  6 Lower Bound

In the final section of our paper, we prove that any comparison-based
algorithm computing the length of a longest $k$-rollercoaster in a permutation
$S$ of $\\{1,\ldots,n\\}$, for $4\leq k\leq\frac{n}{3}$, performs at least
$\Omega(n\log{k})$ comparisons. Let $T$ be a binary comparison tree associated
with an algorithm that computes the result. The number of comparisons made in
the algorithm is equal to the height of $T$, and this is a lower bound on the
execution time of the algorithm.

Let $A$ be a partial ordering associated with a path from the root to some
leaf of $T$. Since the algorithm cannot distinguish between permutations
following the same path, every permutation consistent with $A$ has to give the
same result. Our approach is to first identify a set $U$ of permutations of
$\\{1,\ldots,n\\}$ such that $\log{{\lvert U\rvert}}=\Theta(n\log{k})$, and
any ordering associated with a leaf of $T$ can be consistent with at most one
permutation from $U$. Hence, the number of leaves in $T$ is at least ${\lvert
U\rvert}$. Since the height of a binary tree is at least logarithm of the
number of leaves, this will show that the height of $T$, and hence also the
number of comparison performed by the algorithm, is at least
$\Omega(\log{{\lvert U\rvert}})=\Omega(n\log{k})$.

We first recall the set $\Gamma$ of $\ell^{n-2\ell}$ permutations of
$\\{1,\ldots,n\\}$ proposed by Fredman in [10], where $\ell$ is a parameter.
These permutations are essentially different inputs $S$ for an algorithm
computing the length of LIS, each leading to a different leaf in the
comparison tree.

So, essentially, we want to construct input sequences $(x_{1},\ldots,x_{n})$,
with their elements $x_{1},\ldots,x_{n}$ chosen so that certain linear
orderings of the $x_{i}$s are induced. To create a permutation from $\Gamma$
we partition $(x_{1},\ldots,x_{n})$ into $\ell$ subsequences
$P_{1},P_{2},\ldots,P_{\ell}$. To simplify the exposure, let
$\ell_{\text{prefix}}$ of a sequence be its prefix of length $\ell$, while the
$\ell_{\text{suffix}}$ is its suffix of length $\ell$; the remaining $n-2\ell$
elements are called $\ell_{\text{middle}}$ of the sequence. We partition
$(x_{1},\ldots,x_{n})$ in the following way: the $i^{\text{th}}$ element of
$\ell_{\text{prefix}}$ (that is, $x_{i}$) and the $i^{\text{th}}$ element of
$\ell_{\text{suffix}}$ ($x_{n-\ell+i}$) belong to $P_{i}$. Each element from
$\ell_{\text{middle}}$ of the sequence belongs to an arbitrary chosen part
$P_{j}$. This gives us $\ell^{n-2\ell}$ different partitions. For a partition
$P_{1},\ldots,P_{\ell}$, we assign values from $\\{1,\ldots,n\\}$ to the input
sequence in such a way, that the elements of each part $P_{i}$ form a
decreasing sequence and, for $1\ \leq i\leq\ell-1$, each element of $P_{i}$ is
less than any element of $P_{i+1}$ (see Figure 5). So, each such possible
assignment gives us a permutation from $\Gamma$. LIS of any permutation from
$\Gamma$ is of length $\ell$ because it contains one element from each
$P_{i}$. LDS of any permutation of $\Gamma$ is no longer than $n-2\ell+2$
because it contains at most one element from $\ell_{\text{prefix}}$ and at
most one from $\ell_{\text{suffix}}$.

######  Proposition 5.

Each permutation from $\Gamma$ can be split into $\ell$ descending
subsequences in only one way. For two different permutations from $\Gamma$
these ways of splitting are different.

###### Proof.

Let $P$ be a permutation from $\Gamma$ and $P_{1},\ldots,P_{\ell}$ be its
corresponding partition as described above. Observe that elements of
$\ell_{prefix}$ (respectively, $\ell_{suffix}$) of $P$ form an increasing
subsequence, so no two of them can be in the same decreasing subsequence. Now
let $D_{1},\ldots,D_{\ell}$ be a partition of $P$ into $\ell$ decreasing
subsequences, such that $D_{i}$ contains the $i^{\text{th}}$ element from
$\ell_{prefix}$. Since elements of $\ell_{suffix}$ form an increasing
subsequence, each $D_{i}$ has to contain exactly one of them. Because only the
first element in $\ell_{suffix}$ is smaller than the first element in the
$\ell_{prefix}$, $D_{1}$ actually has to contain the first element of
$\ell_{suffix}$. Repeating this reasoning, we obtain that $D_{i}$ contains the
$i^{\text{th}}$ element from $\ell_{prefix}$ and also the $i^{\text{th}}$
element from $\ell_{suffix}$. Then, we obtain that $D_{1}$ is actually equal
to $P_{1}$, and by repeating this reasoning, that $D_{i}=P_{i}$ for all
$i=1,\ldots,\ell$. ∎

Figure 5: Example permutation $P\in\Gamma$ for $\ell=3$ in a plane. In this
figure, we have $P=(6,13,20,5,19,12,4,11,18,17,16,15,10,3,9,8,2,1,7,14)$.

We now consider the algorithm computing the length of a longest
$k$-rollercoaster. Using the permutations from $\Gamma$ we create a set $U$ of
$k^{n\frac{k-3}{3k-3}}$ permutations of $\\{1,\ldots,n\\}$, again with the
same principle behind: they should be input sequences which lead to different
paths in the comparison tree associated to an algorithm computing the length
of a longest $k$-rollercoaster. Observe that
$\log{(k^{n\frac{k-3}{3k-3}})}=\Theta(n\log{k})$, so this would imply the
desired lower bound of $\Theta(n\log{k})$ on the number of comparisons done by
an algorithm to compute the length of a longest $k$-rollercoaster.

A permutation from $U$ is obtained as follows. Suppose that $(3k-3)$ divides
$n$. Split the sequence $(x_{1},\ldots,x_{n})$ into $\frac{n}{3k-3}$ blocks
(contiguous subsequences) of size $3k-3$. We will assign to the elements of
the $i^{\text{th}}$ contiguous block $(x_{i(3k-3)+1},\ldots,x_{(i+1)(3k-3)})$
distinct values from the set $\\{{i(3k-3)+1},\ldots,{(i+1)(3k-3)}\\}$, as
follows. In every block, use one of the permutations from $\Gamma$ (with the
parameter $\ell$ set to $k$) to values to the elements
$x_{i(3k-3)+1},\ldots,x_{(i+1)(3k-3)}$ of that block, and then assign values
to those elements according to that ordering. In this way, we can create
$|\Gamma|^{\frac{n}{3k-3}}=(k^{k-3})^{\frac{n}{3k-3}}$ permutations of
$\\{1,\ldots,n\\}$. Observe that in every block the length of a longest
decreasing subsequence is less than $k$. Since every block consists of
strictly greater values than the previous ones, a longest decreasing
subsequence of every permutation from $U$ is less than $k$. A longest
increasing subsequence of every element of $\Gamma$ is equal to $k$, so a
longest $k$-rollercoaster for every element of $U$ is equal to
$\frac{kn}{3k-3}$ and consists only of longest increasing subsequences
corresponding to all the blocks glued one after the other. We can now show a
result similar to Proposition 5.

######  Proposition 6.

Each permutation from $U$ can be split into $\frac{kn}{3k-3}$ descending
subsequence in only one way. For two different permutations from $U$ these
ways of splitting are different.

###### Proof.

Let $S$ be a permutation from $U$. Recall that we can partition $S$ into
$\frac{n}{3k-3}$ contiguous blocks of length $3k-3$. All values in a block are
strictly greater than the values in all previous blocks, so in a decreasing
subsequence of $S$ we can have only elements from one block. Since every block
corresponds to a permutation from $\Gamma$, by Proposition 5 it can be split
into exactly $k$ decreasing subsequences in only one way. For each two
different permutations of $U$, there exists at least one block (i.e.,
permutation from $\Gamma$) that differentiates them. By Proposition 5, this
block is split in a different way than all the other blocks of $\Gamma$, so
the conclusion follows: each particular permutation from $U$ will also be
split in a different way than all other permutations of $U$. ∎

Having constructed the set $U$, we can proceed with the lower bound. Let $A$
be a partial ordering associated with a path to some leaf of $T$ (the
comparison tree associated to the algorithm computing the length of a longest
$k$-rollercoaster). Since the algorithm cannot distinguish between
permutations following the same path, every permutation consistent with $A$
has to give the same result. We recall the following lemma.

######  Lemma 5 (Lemma 3.6 in [10]).

Let $\leq$ be a partial ordering defined on $S$. The maximum length of LIS in
$S$ associated with any linear embedding of this ordering, is equal to the
minimum number of decreasing subsequences relative to $\leq$ into which $S$
can be partitioned.

Now we can prove the following.

######  Lemma 6.

Let $A$ be partial ordering associated with the path from the root to a leaf
of $T$. Only one permutation from $U$ can be consistent with $A$.

###### Proof.

Consider $S\in U$ that is consistent with $A$, and let $D=\frac{kn}{3k-3}$ be
the length of its LIS. Now let $m$ be the minimum number of decreasing
subsequences relative to the results of the comparisons made on the path $A$
into which $S$ can be partitioned. If $m<d$ then $S$ is consistent with $A$,
so we can partition $S$ into the same decreasing subsequences, but $S$ cannot
be divided into less than than $d$ decreasing subsequences, a contradiction.
If $m>d$ then by Lemma 5 there exists a permutation $S^{\prime}$ consistent
with $A$ with the length of LIS greater than $d$. $S^{\prime}$ follows the
same path as $S$ in the comparison tree, but has a longer $k$-rollercoaster
(consisting only of LIS of $S^{\prime}$) than $S$, a contradiction. Thus,
$m=d$ for any such $S$.

Consider two $S_{1},S_{2}\in U$ consistent with $A$. By Proposition 6, the
only partition of $S_{1}$ into $d$ decreasing sequences is different from the
only such partition of $S_{2}$ (into $d$ decreasing sequences), so $A$ can be
consistent with only one permutation, a contradiction. ∎

Thus, each permutation from $U$ corresponds to a distinct leaf of $T$, making
the depth of $T$ at least $\log{\lvert U\rvert}=\Theta(n\log{k})$ as required
and proving the following theorem.

######  Theorem 9.

For every $k$ satisfying $4\leq k\leq\frac{n}{3}$, any comparison-based
algorithm that computes the length of a longest $k$-rollercoaster in a
permutation of $\\{1,\ldots,n\\}$ performs at least $\Omega(n\log{k})$
comparisons.

## References

  * [1] Alok Aggarwal and Maria M. Klawe.  Applications of generalized matrix searching to geometric algorithms.  Discrete Applied Mathematics, 27(1-2):3--23, 1990.
  * [2] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber.  Geometric applications of a matrix-searching algorithm.  Algorithmica, 2:195--208, 1987.
  * [3] David Aldous and Persi Diaconis.  Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem.  Bulletin of the American Mathematical Society, 36:413--432, 1999\.
  * [4] Sergei Bespamyatnikh and Michael Segal.  Enumerating longest increasing subsequences and patience sorting.  Information Processing Letters, 76(1):7 -- 11, 2000.
  * [5] Therese C. Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit.  Rollercoasters and caterpillars.  In ICALP, volume 107 of LIPIcs, pages 18:1--18:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
  * [6] Therese C. Biedl, Timothy M. Chan, Martin Derka, Kshitij Jain, and Anna Lubiw.  Improved bounds for drawing trees on fixed points with L-shaped edges.  In Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers, volume 10692 of Lecture Notes in Computer Science, pages 305--317. Springer, 2017.
  * [7] Bernard Chazelle.  A functional approach to data structures and its use in multidimensional searching.  SIAM J. Comput., 17(3):427--462, 1988.
  * [8] Maxime Crochemore and Ely Porat.  Fast computation of a longest increasing subsequence and application.  Information and Computation, 208(9):1054--1059, 2010.
  * [9] Paul Erdős and George Szekeres.  A combinatorial problem in geometry.  Compositio Mathematica, 2:463--470, 1935.
  * [10] Michael L. Fredman.  On computing the length of longest increasing subsequences.  Discrete Mathematics, 11(1):29--35, 1975.
  * [11] Hania Gajewska and Robert Endre Tarjan.  Deques with heap order.  Information Processing Letters, 22(4):197--200, 1986.
  * [12] James W. Hunt and Thomas G. Szymanski.  A fast algorithm for computing longest common subsequences.  Communications of the ACM, 20(5):350--353, 1977.
  * [13] Sergey Kitaev.  Patterns in Permutations and Words.  Springer, 2011.
  * [14] S. Linton, N. Ruškuc, and V. Vatter, editors.  Permutation Patterns.  London Mathematical Society Lecture Note Series, vol. 376, Cambridge, 2010\.
  * [15] Dan Romik.  The Surprising Mathematics of Longest Increasing Subsequences.  Cambridge, 2015.
  * [16] Craige Schensted.  Longest increasing and decreasing subsequences.  Canadian Journal of Mathematics, 13:179--191, 1961.
  * [17] J. Michael Steele.  Variations on the monotone subsequence theme of Erdős and Szekeres.  In David Aldous, Persi Diaconis, Joel Spencer, and J. Michael Steele, editors, Discrete Probability and Algorithms, pages 111--131. Springer New York, 1995.
  * [18] Xiaoming Sun and David P. Woodruff.  The communication and streaming complexity of computing the longest common and increasing subsequences.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, pages 336--345. Society for Industrial and Applied Mathematics, 2007.
  * [19] Alexander Tiskin.  Fast distance multiplication of unit-Monge matrices.  Algorithmica, 71(4):859--888, 2015.