\section{Introduction}


Let $\Pi$ be a \textit{circular sequence} of $\{1, 2, \ldots, n\}$. It means, $\Pi = \left ( \pi_0, \ldots, \pi_{n \choose 2} \right )$ is a sequence of permutations of $\{1, 2, \ldots, n\}$ such that $\pi_0$ is the identity permutation $\{1, 2, \ldots, n\}$ and $\pi_{n \choose 2}$ is the reverse permutation $\{n, n - 1, \ldots, 1\}$. Any two consecutive permutations differ by exactly one transposition of two elements in adjacent positions and every these transpositions have defined weight determined by the position of swaped elements. We are interested in case, when the weight in the middle (for even $n$) is zero and increases by one (na obe strany)-- figure (OBRAZEK). Our aim is finding circular sequence with the smallest cost, where the cost of circular sequence is sum of weights its permutations.

Circular sequences are also connected with geometrical problems. nasi volby vah se tyka nasledujici:

Let $S$ be a set of $n$ points in general position in the plane. Every pair of points $a$, $b$ of this set determine a line, which divides $S$ into two parts, let call them $S_1$ and $S_2$ (FIGURE). Now define difference of configuration $S$ as: $$D(S) = \sum_{a, b \in S, a \neq b} {\left |s_1 - s_2 \right |},$$ where $s_1$ resp. $s_2$ denote cardinality of $S_1$ resp. $S_2$ (sometimes we will use next notation $D(ab) = \left |s_1 - s_2 \right |$). In other words, it is sum of differences between the numbers of points in the two open halfplanes determined by the line $ab$ (in particular, if the configuration has an even number of points, then the difference of each pair of point is even). Our aim is determine the following function $$F(n) = \min_{|S| = n}D(S).$$ (opet radsi i slovne)

The connection between geometrical difference problem and circular sequences is folowing: Let $S$ be configuration of $n$ points as above. Let $L$ be directed line that is not orthogonal to any of the lines defined by pairs of points in $S$. We label the points in $S$ as $p_1, p_2, \ldots, p_n$, according to the order in which their orthogonal projctions appear along $L$. Now suppose that we start rotating $L$ counterclockwise, say. The ordering of the projections changes exactly at the positions where $L$ passes through a position orthogonal to the line defined by some pair of points $a$, $b$ in $S$. At the time the projection change occurs, $a$ and $b$ are adjacent in the ordering and the ordering changes by transposing $a$ and $b$. Thus, if we keep track of all permutations of the projections as the line $L$ is rotated by $180 ^\circ$, we obtain a circular sequence $\Pi$. 

Now we show, that cost of circular sequence get in this way is ${1 \over 4}D(S)$. While we are rotating line $L$, in one moment projections of two adjacent points $a$ a $b$ are same and this projection is exactly on intersection of lines $L$ and $ab$. Let $m_l$ be number of points on the left from $a$ and $b$ in this projection, $m_r$ number of points on the right and $m$ minimum of $m_l$ and $m_r$. Number of points on the other side is exactly $n-m-2$, so $D(ab) = n-2m-2$. On the other side, weight of transposition $a$ and $b$ is ${n \over 2} - k - 1$ (ie. $D(ab) \over 2$), because transposition on the most left (right) position is ${n \over 2} - 1$ and weight of swap $a$ with $b$ are decreased by exactly $m$ numbers before (after). So we can get cost of $\Pi$ simply by summing over all lines between two points in $S$ and divide it by $2$. In $D(S)$ we count every line exactly twice and this implies claimed relation between $D(S)$ and cost of its circular sequence.

     
Upper bound for function $F(n)$

This upper bound follows from known mercedes construction of many halving lines.  

popis mercedese:

The mercedes configuration $M$ is defined in recursive way. First we have four points in non-convex position. We scaled them and triplied (ztrojime) (precizneji) So we have configuration of $4 \cdot 3^k$ points (in $k$ step). Let $n := 4 \cdot 3^{k - 1}$ be size of each ot the three parts of the trefoil.
Now we want to compute difference of this mercedes configuration. 

First we express difference of configuration $C$ of $n$ points in next way $$D(C) := \sum_{a \in C} \sum_{b \in C, b \neq a}D(ab), $$ where $D(ab)$ is difference of pair of points $a$, $b$ mentioned above. In particular, every line contribute twice to total difference of the configuration. Mercedes configuration yields the reccurence: $$D(M_k) = 3 \cdot D(M_{k - 1}) + 6 \cdot \sum_{i = 1}^n \sum_{j = 1}^n (|2i + 2j - 2 - 3n|),$$ where $M_k$ is mercedes configuration after $k$ steps. Difference of $M_0$ (difference of the non-convex four-point configuration) is $12$. FIGURE
The double sum $6 \cdot \sum_{i = 1}^n \sum_{j = 1}^n (|2i + 2j - 2 - 3n|)$ in the reccurence above simplifies to the cubic polynomial $\frac{13}{2}n^3 - 2n$, so the reccurence can be expressed as $$D(M_k) = 3 \cdot D(M_{k - 1}) + \frac{13}{2}n^3 - 2n.$$ Substituting $N := 3n = 4 \cdot 3^k$ for the total number of points (i.e. $M_k$ is mercedes configuration on $N$ points), here is a closed-form solution for the difference of an $N$-point mercedes configuration $M_k$. For simplicity denote $D(N) := D(M_k)$. Then $D(N) = 3 \cdot D(\frac N3) + \frac{13}{54} N^3 - \frac23N$. From computation we derive that the leading term is $\frac{13}{48}$, which corresponds after appropriate scaling to the $\frac{13}{24}k^3$ upper bound for the cost of an algorithm reversing $2k$ points with weights $k - 1, k - 2, \ldots, -1, 0, 1, \ldots, k-1.$