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 (a1,c1),,(an,cn)(a_1,c_1),\ldots,(a_n,c_n), where aia_i is the value, a positive number, cic_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 abcosθ2ab \frac{\cos \theta}{2}, where θ=2πn\theta = \frac{2\pi}{n}, and a,ba,b are the value for two adjacent coordinates. The area of the entire shape is the sum.

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

Lemma1

If xabcd0x\geq a\geq b \geq c \geq d\geq 0, then ax+bxabcx+dxcdax+bx - ab \geq cx+dx-cd.

Proof

Let’s consider what is required to make sure the property works. (a+b)xab(c+d)xcdxabcdac+bdxabbc+bccdac+bdxb(ac)+c(bd)ac+bdxb(ac+bd)ac+bdxb\begin{aligned} (a+b)x-ab &\geq (c+d)x-cd\\ x&\geq \frac{ab-cd}{a-c+b-d}\\ x&\geq \frac{ab-bc+bc-cd}{a-c+b-d}\\ x&\geq \frac{b(a-c)+c(b-d)}{a-c+b-d}\\ x&\geq \frac{b(a-c+b-d)}{a-c+b-d}\\ x&\geq b \end{aligned} The lemma is true, as xbx\geq b is part of the hypothesis for xx.

Theorem2

Let a1,,ana_1,\ldots,a_n be a sequence of positive numbers, such that a1ana_1 \leq \ldots \leq a_n.

Let π\pi be the following:

  1. π(n+1)=1\pi(n+1) = 1.
  2. π(1),,π(n)=1,3,,n1,n,n2,,4,2\pi(1),\ldots,\pi(n) = 1, 3, \ldots, n-1, n, n-2, \ldots, 4, 2 if nn is even
  3. π(1),,π(n)=1,3,,n2,n,n1,,4,2\pi(1),\ldots,\pi(n) = 1, 3, \ldots, n-2, n, n-1, \ldots, 4, 2 if nn is odd.

π\pi maximizes i=1naπ(i)aπ(i+1) \sum_{i=1}^n a_{\pi(i)}a_{\pi(i+1)}

Proof

Proof by induction.

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

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

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

This implies a simple O(nlogn)O(n \log n) algorithm. Find the permutation that sort the input sequence by value, then composes it with permutation π\pi.

Actually this problem is a special case of the TSP problem on a product matrix. A matrix is called a product matrix if Mi,j=aibjM_{i,j} = a_ib_j for vectors (a1,,an)(a_1,\ldots,a_n) and (b1,,bn)(b_1,\ldots,b_n). It is solvable in polynomial time if MM 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.