The Art Gallery Guardian

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.

Two Radar Charts

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

Given the sequence of data , where is the value, a positive number, 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 , where , and are the value for two adjacent coordinates. The area of the entire shape is the sum.

Once we can maximize , we are done.

Lemma1

If , then .

Proof

Let’s consider what is required to make sure the property works. The lemma is true, as is part of the hypothesis for .

Theorem2

Let be a sequence of positive numbers, such that .

Let be the following:

  1. .
  2. if is even
  3. if is odd.

maximizes

Proof

Proof by induction.

Base case: Base case for are trivial.

Inductive Step: Consider it is true for , we want to show it is true for .

Consider we already obtained a sequence from to , and we want to insert somewhere. Clearly need to be placed in a position that maximizes its contribution. If we can insert it between and , then we get a contribution of . 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 to , then we are done. The inductive hypothesis show the maximum configuration have adjacent and , therefore this shows the maximum configuration is where we insert in between and in the previous maximum configuration.

This implies a simple 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 for vectors and . It is solvable in polynomial time if 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 .
Tags: math.