Maximize the area of a radar chart

People use radar charts to present their ability in different skills.

Like all self presentations, it need to make the person “look good”. A chart with larger area looks better than the ones with less area. The remaining of the article take about how to find a radar chart with maximum area.

In the image above, the left side has less area than the right.

Given the sequence of data $(a_{1}, c_{1}), \dots, (a_{n}, c_{n})$ , where $a_{i}$ is the value, a positive number, $c_{i}$ is a coordinate(in the image, the coordinates would be “combinatorics”, “algorithms”, etc.). How can we permute them, such that the data plotted on the radio chart is maximized?

The area of of any single section of the radio chart is $ab \frac{c o s θ}{2}$ , where $θ = \frac{2 π}{n}$ , and $a, b$ are the value for two adjacent coordinates. The area of the entire shape is the sum.

Once we can maximize $\sum_{i = 1}^{n} a_{π (i)} a_{π (i + 1)}$ , we are done.

Lemma1

If $x \geq a \geq b \geq c \geq d \geq 0$ , then $a x + b x - ab \geq c x + d x - c d$ .

Proof

Let’s consider what is required to make sure the property works. $(a + b) x - ab x x x x x \geq (c + d) x - c d \geq \frac{ab - c d}{a - c + b - d} \geq \frac{ab - b c + b c - c d}{a - c + b - d} \geq \frac{b ( a - c ) + c ( b - d )}{a - c + b - d} \geq \frac{b ( a - c + b - d )}{a - c + b - d} \geq b$ The lemma is true, as $x \geq b$ is part of the hypothesis for $x$ .

Theorem2

Let $a_{1}, \dots, a_{n}$ be a sequence of positive numbers, such that $a_{1} \leq \dots \leq a_{n}$ .

Let $π$ be the following:

$π (n + 1) = 1$ .
$π (1), \dots, π (n) = 1, 3, \dots, n - 1, n, n - 2, \dots, 4, 2$ if $n$ is even
$π (1), \dots, π (n) = 1, 3, \dots, n - 2, n, n - 1, \dots, 4, 2$ if $n$ is odd.

$π$ maximizes $i = 1 \sum n a_{π (i)} a_{π (i + 1)}$

Proof

Proof by induction.

Base case: Base case for $n = 1, 2$ are trivial.

Inductive Step: Consider it is true for $n - 1$ , we want to show it is true for $n$ .

Consider we already obtained a sequence from $a_{1}$ to $a_{n - 1}$ , and we want to insert $a_{n}$ somewhere. Clearly $a_{n}$ need to be placed in a position that maximizes its contribution. If we can insert it between $a_{n - 1}$ and $a_{n - 2}$ , then we get a contribution of $a_{n - 1} a_{n} + a_{n - 2} a_{n} - a_{n - 1} a_{n - 2}$ . By the lemma, it will give us the maximum contribution.

If we can get the maximum contribution (over all possible configurations) to a maximum configuration for $a_{1}$ to $a_{n - 1}$ , then we are done. The inductive hypothesis show the maximum configuration have adjacent $a_{n - 1}$ and $a_{n - 2}$ , therefore this shows the maximum configuration is where we insert $a_{n}$ in between $a_{n - 1}$ and $a_{n - 2}$ in the previous maximum configuration.

This implies a simple $O (n lo g n)$ algorithm. Find the permutation that sort the input sequence by value, then composes it with permutation $π$ .

Actually this problem is a special case of the TSP problem on a product matrix. A matrix is called a product matrix if $M_{i, j} = a_{i} b_{j}$ for vectors $(a_{1}, \dots, a_{n})$ and $(b_{1}, \dots, b_{n})$ . It is solvable in polynomial time if $M$ is a symmetric matrix [1].

References

[1]

R.E. Burkard, V.G. Deῐneko, R. van Dal, J.A.A. van der Veen, G.J. Woeginger, Well-solvable special cases of the traveling salesman problem: A survey, SIAM Review. 40 (1998) pp. 496–546.

Posted by Chao Xu on 2012-08-08.

Tags: math.