The Story Folds

View Original

Pie-bar charts

See this content in the original post

When I wrote about off-center pie charts, I got this response on Reddit:

hoosierEE:

This is one of those "thanks, I hate it" type of things.

Kind of makes me want to see a hybrid pie-bar chart, where the pie is just cut into vertical slices. "For my least favorite guest, a slice which is mostly crust".

That’s an interesting idea. So here are some pie-bar charts (on the right), compared to the regular pie charts (on the left). In each case, the areas of the slices match the percentages, and the pie-bar charts are arranged in a way that minimizes the difference in width between the largest and smallest slices.

See this content in the original post

What do you think of this hybrid between a pie chart and a bar graph? Feel free to make your own pie-bar charts here by adjusting the percentages.

See this content in the original post

How the math works

This version was not as tricky to implement as the off-center pie charts were. I still don’t have a polynomial-time solution to the optimization problem, and it seems similar enough to subset sum that it’s likely to be NP-hard. My first two attempts at a better-than-factorial-time algorithm were wrong. Thanks to Tomek Czajka and Mark Gordon for pointing that out.

This problem is much trickier than it looks, and a few of the obvious-sounding observations are incorrect.

Let’s set the goal of minimizing the difference in width between the widest and the narrowest slice — that will be our cost function. The first observation that jumps out is that the smallest-area slice should always be the leftmost or rightmost slice. The next obvious-looking observation is that the second smallest slice should go to the opposite side.

Proving either of these claims is tricky though, especially given that the second claim is false. The counter-example (due to Tomek) is [1, 9, 10, 80]. Try it above, and it will place the 1 and the 9 on the same side.

Implementing the full O(n!) permutation search seemed like the safer choice here, and fast enough for practical cases. So that’s what the code in this page does.