Visualize Your Algorithms

As a college student in the ‘90’s with a penchant for “visual learning” I was never drawn to computer science. My one computer science class focused mostly on syntax and basic logic. Had shuffling and sorting been presented as eye-catching animations and colorful braids, I might have taken more CS classes. Mike Bostock presents such eye-catching images, specifically concerning four different goals: sampling of images, shuffling, sorting, and maze generation. For each goal, Bostock chooses several algorithms and explains how they each work visually. Even a brief look at the visualizations, some of which are animated and some static, gives a sense of the differences between the algorithms. As Bostock points out, visualizing algorithms is entertaining, makes understanding the algorithm more intuitive to others, helps in debugging your algorithm, and deepens your own personal understanding. In short, Bostock wants you to visualize not just data, but the algorithms used to analyze the data.  From a mathematical perspective, this is similar to insisting that we find ways to visualize the proof mechanism itself and not just the concept that it justifies.  In other words, we can draw a right triangle with appropriate labeling and call that a visualization of the pythagorean theorem, but it’s not nearly as instructive as this short animation or this geogebra applet.

Sampling is as ubiquitous in digital computing as the Pythagorean theorem is in geometry.  And while it is easy to understand as a concept, sampling is difficult to execute well. Bostock takes as an example an impressionistic painting. How can we choose samples in a way that will best digitally reproduce the original image? It turns out that we can learn form our own biology; the eye’s photoreceptors “sample” the world around us and are distributed in an irregular but uniformly dense manner. Such a sampling helps combat aliasing, a phenomenon whereby regularly spaced samples distort data with high levels of periodicity (Imagine a picture of a striped sweater that is sampled at a resolution lower than the spacing between stripes). This is where Poisson Disk sampling comes in. It is computationally more complex than other options, but produces a uniformly dense yet random sampling. As Bridson’s algorithm for Poisson Disk sampling plays, you immediately notice how the samples emanate from an initial seed rather than populating the entire sample space over time. This is one example of how visualization can helps us distinguish between algorithms.

Bostock works for the New York Times, and has many wonderful examples and posts on his site. Being a delinquent topologist, I was drawn to “How To Infer Topology”. Bostock is very interested in Cartography, and this leads to his writing about how to think about the data in a map more efficiently using a topological perspective. Several animations break down how one might encode a map by recording a sequence of arcs and special intersection points.

After a bit of perusal I realized that I had seen some of the work of one of Bostock’s collaborators, Jason Davies on Math Munch’s page in the past. Looking over Davies’ site, I can’t help but recommend that you take a look at his simple but beautiful graphic of a tiling of the Poincare disc. Zoom in and you can see the upper half plane model of the hyperbolic plane!