# Best way to visualize scatterplot with thousands of points in a grayscale-friendly way?

I have 10,000 data points like shown in this plot:
It's comparing the running time of some piece of code with the size of the problem it's running on.
(There are 2 important steps in the code; step 1's running time is in blue and step 2's is in green.)

I'm hoping to keep this grayscale-friendly, because I'm hoping to publish this and it may end up being in grayscale.

I'm trying to figure out how to best visualize this data. Currently I'm thinking it may be best to perform kernel density estimation in log-scale and just plot a smooth surface, but I'm not sure... is there a better way to visualize it clearly?

• Are you open to suggestions about other ways to present the same data visually, such as sequences of boxplots, smooths, and other such visual summaries? If so, which features of the data do you want to emphasize? Is showing extreme or outlying data of importance? How about depicting variation in running time? Are you interested in helping readers compare the running times of the two steps or not? – whuber Jan 21 '15 at 19:57
• Snowstorms or snowdrifts, like yours, are best to overlay in front of some scenery. Where the points are dense the background shapes will come through dimly. – ttnphns Jan 21 '15 at 20:09
• @whuber: Yes. I'm basically trying to show that my algorithm is "in practice" linear-time, even though theoretically I can't prove there aren't problems on which it can take exponential time, and I'm doing that by trying 10000 random problem instances. So in that scenario, it's important that people can see outliers (because the worst-case behavior matters), but it's also important to see the clustering in the low-range (because people need to see that in practice it's very fast). I'm also hoping to depict it in a way such that people can visually see the approximate running time (e.g. 10 ms) – Mehrdad Jan 21 '15 at 22:18
• have you considered a log-log plot, with a 45 degree line through a typical point - say (x-median,y-median) - marked in? If your thesis is correct the data should tend to lie close to/parallel to the line – Glen_b Jan 21 '15 at 23:19
• Consider a pair of graphs, each with a loess curve (as well as the suggested reference line), and each also with the loess curve from the other plot as a dashed curve for ready comparison. – Glen_b Jan 22 '15 at 1:15

A log-log plot will spread the points out quite a bit.

If your thesis is correct the data should tend to lie close to/parallel to a 45 degree line through a typical point - say (x-median,y-median).

Having seen your log-log scale plot in the comments, a greyscale would be a problem because the overlap of the point clouds is so substantial even on the log scale. With color you can use transparency but that's difficult on greyscale.

So for that issue, consider a pair of graphs, each with a LOESS curve (as well as the suggested reference line), and each also with the LOESS curve from the other plot as a dashed curve for ready comparison.

The run time as a function of the size is usually polynomial (when you're lucky) or exponential. Hence, I'd first try to figure which is the case.

• For the former try log transform both time and size, then scatter.
• for the latter try log transform only time

If neither of these scatter plots show a linear pattern, then we need to think of something else, otherwise, you're good.

If you know theoretical run time function such as $O(n\ln n)$, then you can use this for transformation too. The point is to get to some kind of a linear function, as they tend to be easier to present and consume.

Also, you could bucket your data into bins. for instance, say you're run time $t$ is $t=10s^3$, where $s$ is the size of the problem, then $\ln t=\ln 10+3\ln s$. This would be handled by log-log transform. Next, you break the log of size $\ln s$ into buckets. Then for each bucket you put a candle stick. This will create the candle stick chart like shown below. It'll show the dispersion of log run times for each bucket.