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

30
The categories of this paper are: q-alg
6
The categories of this paper are: astro-ph
33
The categories of this paper are: plasm-ph
5
The categories of this paper are: gr-qc
21
The categories of this paper are: adap-org
29
The categories of this paper are: funct-an
2
The categories of this paper are: math
34
The categories of this paper are: chem-ph
9
The categories of this paper are: nlin
18
The categories of this paper are: econ
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
35
The categories of this paper are: mtrl-th
11
The categories of this paper are: hep-lat
36
The categories of this paper are: cmp-lg
10
The categories of this paper are: q-bio