How Hard Can It Be to Draw a Pie Chart? - October 1987

Date: Tue, 13 Oct 87 00:49:40 EST
From: Don Hopkins <don@brillig.umd.edu>
To: research!td@uunet.uu.net (Tom Duff)
Cc: don@brillig.umd.edu
Subject: Labeling pie graphs is NP hard?

Were you the one who mentioned that someone has found labeling pie graphs to be NP hard, during my pie menu talk at the Usenix Graphics Workshop? If so, or if you know about it, I'd very much appreciate a reference to this work, or a pointer to the person who did it. Thanks a lot.

-Don

From: Tom Duff <likewise!research!td@uunet.UU.NET>
Date: Tue, 13 Oct 87 09:16:55 edt
To: uunet!brillig.umd.edu!don

Chris Van Wyk and one of his students did the work. I've only seen an internal memorandum describing it, and it's hard to believe that it's publishable. Chris is research!cvw

From: Tom Duff <likewise!research!td@uunet.UU.NET>
Date: Tue, 13 Oct 87 18:05:41 edt
To: uunet!brillig.umd.edu!don

I found the paper. It's called `How hard can it be to draw a pie chart?' by Diane L. Souvaine (Rutgers University) and Christopher J. Van Wyk (research!cvw)

It shows that when the order of sectors is not fixed, the problem of arranging a list of sectors of given size so that each contains a horizontal line of given length is NP-hard.

Date: Fri, 16 Oct 87 20:01:57 EST
From: Don Hopkins <don@brillig.umd.edu>
To: likewise!research!td@uunet.UU.NET
Cc: don@brillig.umd.edu
Subject: How hard can it be to draw a pie chart?

Great -- thanks for the reference! I'll get in touch with cvw.

I've been thinking about how to do more intelligent pie menu label placement, that minimizes menu size while keeping the labels from overlapping. As the giant 360 item pie menu shown in my video tape demonstrated, positioning the labels around an inner radius that is a linear function of the number of labels can end up demanding more real estate than Jim Bakker shopping for amusement parks. (Not that everybody shouldn't have a screen big enough to display such menus!)

One thing I was thinking of experimenting with was "2 1/2 dimensional dynamics", where labels are attracted to their places by springs, but are pushed away from each other when they overlap. This could also be applied to speech balloons, used to annotate a picture. There would be "uphill" regions of the picture that should not be covered up, and the balloons, which are anchored in place by rubber-band-like pointers, fight it out until none of them overlap.

I think it would be neat to use with graphical hypertext, and other things that need dynamically positioned popup windows that don't obscure each other. There's a lot to be done with arbitrarily shaped windows! (Just leaf through a MAD Magazine!)

-Don

Date: Fri, 16 Oct 87 21:03:26 EST
From: Don Hopkins <don@brillig.umd.edu>
To: research!cvw@uunet.uu.net (Chris Van Wyk)
Cc: don@brillig.umd.edu
Subject: `How hard can it be to draw a pie chart?'

At the Usenix Graphics Workshop, Tom Duff mentioned that you've written a paper about labeling pie charts. I'm very interested in reading it, as I am doing research on pie menus -- circular menus, with choice based on cursor direction. Could you please send me a copy? Coming up with a pleasing labeling scheme that does not waste a lot of space has been one of the more difficult problems I've had to deal with. If you'd like, I could send you copies of our papers on pie menus.

-Don

From: Chris Van Wyk <likewise!research!cvw@uunet.UU.NET> Date: Sat, 17 Oct 87 09:24:14 edt
To: uunet!brillig.umd.edu!don

I'll pop a copy into the mail to you Monday.

Chris Van Wyk