All The Names: Algorithmic Design and the 9/11 Memorial

By Jer | June 10, 2011

In late October, 2009, I received an e-mail from Jake Barton from Local Projects, titled plainly ‘Potential Freelance Job’. I read the e-mail, and responded with a reply in two parts: First, I would love to work on the project. Second, I wasn’t sure that it could be done.

The project was to design an algorithm for placement of names on the 9/11 memorial in New York City. In architect Michael Arad‘s vision for the memorial, the names were to be laid according to where people were and who they were with when they died – not alphabetical, nor placed in a grid. Inscribed in bronze parapets, almost three thousand names would stream seamlessly around the memorial pools. Underneath this river of names, though, an arrangement would provide a meaningful framework; one which allows the names of family and friends to exist together. Victims would be linked through what Arad terms ‘meaningful adjacencies’ – connections that would reflect friendships, family bonds, and acts of heroism. through these connections, the memorial becomes a permanent embodiment of not only the many individual victims, but also of the relationships that were part of their lives before those tragic events.

Over several years, staff at the 9/11 Memorial Foundation undertook the painstaking process of collecting adjacency requests from the next of kin of the victims, creating a massive database of requested linkages. Often, several requests were made for each victim. There were more than one thousand adjacency requests in total, a complicated system of connections that all had to be addressed in the final arrangement. In mathematical terms, finding a layout that satisfied as many of these adjacency requests as possible is an optimization problem – a problem of finding the best solution among a myriad of possible ones. To solve this problem and to produce a layout that would give the Memorial Designers a structure to base their final arrangement of the names upon, we built a software tool in two parts: First, an arrangement algorithm that optimized this adjacency problem to find the best possible solution. And second, an interactive tool that allowed for human adjustment of the computer-generated layout.

The Algorithm

The solution for producing a solved layout for the names arrangement sat at the bottom of a precariously balanced stack of complex requirements.

First, there was the basic spatial problem – the names for each pool had to fit, evenly, into a set of 76 panels (18 panels per side plus one corner). 12 of these panels were irregularly shaped (the corners and the panels adjacent to the corners, as seen in the image at the top of this post). Because the names were to appear in one continuous flowing group around each pool, some names had to overlap between panels, crossing a thin, invisible expansion joint between the metal plates. This expansion joint was small enough it would fit in the space between many of the first and last names (or middle initials), but with certain combinations of letterforms (for example, a last name starting with a J, or a first name ending with a y), names were unable to cross this gap. As a result, the algorithm had to consider the typography of each name as it was placed into the layout.

Of course, the most challenging problem was to place the names within the panels while satisfying as many of the requested adjacencies as possible. There were more than 1200 adjacency requests that needed to be addressed. One of the first things that I did was to get an idea of how complex this network of relations was by building some radial maps:

Clearly, there was a dense set of relations that needed to be considered. On top of that, the algorithm needed to be aware of the physical form of each of the names, since longer names could offer more space for adjacency than smaller ones. Because each person could have more than one adjacency request, there were groups of victims who were linked together into large clusters of relationship – the largest one of these contained more than 70 names. Here is a map of the adjacency clusters within one of the major groupings:

On top of these crucial links between victim names, there were a set of larger groupings in which the names were required to be placed: affiliations (usually companies), and sub-affiliations (usually departments within companies). To complicate matters, many of the adjacency requests linked people in different affiliations and subaffiliations, so the ordering of these groupings had to be calculated in order to satisfy both the adjacency requests and the higher-level relationships.

At some point I plan on detailing the inner workings of the algorithm (built in Processing). For the time being, I’ll say that the total process is in fact a combination of several smaller routines: first, a clustering routine to make discrete sets of names in which the adjacency requests are satisfied. Second, a space filling process which places the clusters into the panels and fills available space with names from the appropriate groupings. Finally, there is a placement routine which manages the cross-panel names, and adjusts spacing within and between panels.

The end result from the algorithm is a layout which completes as many of the adjacency requests as completely as possible. With this system, we were able to produce layouts which satisfied more than 98% of the requested adjacencies.

The Tool

Early on in the project, it became clear that the final layout for the names arrangement would not come directly from the algorithm. While the computerized system was able to solve the logistical problems underlying the arrangement, it was not as good at addressing the myriad of aesthetic concerns. The final layout had to be reviewed by hand – the architects needed to be able to meticulously adjust spacing and placement so that the final layout would be precisely as they wanted it. With this in mind, we built a custom software tool which allowed the memorial team to make custom changes to the layout, while still keeping track of all of the adjacencies.

The tool, again built in Processing, allowed users to view the layouts in different modes, easily move names within and between panels, get overall statistics about adjacency fulfillment, and export SVG versions of the entire system for micro-level adjustments in Adobe Illustrator. In the image above, we see an early layout for the South Pool. The colouring here represents two levels of grouping within the names. Main colour blocks represent affiliations, while shading within those colour blocks represents sub-affiliations. Below, we see a close-up view of a single panel, with several names placed in the ‘drawer’ below. Names can be placed in that space when they need to be moved from one panel to another. Note that adjacency indications remain active while the names are in the drawer.

Other features were built in to make the process of finalizing the layout as easy as possible: users could search for individual names, as well as affiliations and sub-affiliations; a change-tracking system allowed users to see how a layout had changed over multiple saved versions, and a variety of interface options allowed for precise placement of names within panels. Here is a video of the tool in use, again using a preliminary layout for the South Pool:

Computer Assisted Design

It would be misleading to say that the layout for the final memorial was produced by an algorithm. Rather, the underlying framework of the arrangement was solved by the algorithm, and humans used that framework to design the final result. This is, I think, a perfect example of something that I’ve believed in for a long time: we should let computers do what computers do best, and let humans do what humans do best. In this case, the computer was able to evaluate millions of possible solutions for the layout, manage a complex relational system, and track a large set of important variables and measurements. Humans, on the other hand, could focus on aesthetic and compositional choices. It would have been very hard (or impossible) for humans to do what the computer did. At the same time, it would have been very difficult to program the computer to handle the tasks that were completed with such dedication and precision by the architects and the memorial team.

The Weight of Data

This post has been a technical documentation of a very challenging project. Of course, on a emotional level, the project was also incredibly demanding. I was very aware throughout the process that the names that I was working with were the names of fathers and sons, mothers, daughters, best friends, and lovers.

Lawrence Davidson. Theresa Munson. Muhammadou Jawara. Nobuhiro Hayatsu. Hernando Salas. Mary Trentini.

In the days and months that I worked on the arrangement algorithm and the placement tool, I found myself frequently speaking these names out loud. Though I didn’t personally know anyone who was killed that day, I would come to feel a connection to each of them.

This project was a very real reminder that information carries weight. While names of the dead may be the heaviest data of all, almost every number or word we work with bears some link to a significant piece of the real world. It’s easy to download a data set – census information, earthquake records, homelessness figures - and forget that the numbers represent real lives. As designers, artists, and researchers, we always need to consider the true source of data, and the moral responsibility which they carry.

Ultimately, my role in the construction of the memorial was a small, and largely invisible one. Rightly, visitors to the site will never know that an algorithm assisted in its design. Still, it is rewarding to think that my work with Local Projects has helped to add meaning to such an important monument.

The 9/11 Memorial will be dedicated on September 11, 2011 and opens to the public with the reservation of a visitor pass on September 12th.

32 Comments

Your Device: Your data. How to save your iPhone location data (and help researchers make the world a better place)

By Jer | May 5, 2011

An hour ago, Apple announced that it has released a patch for iOS and iTunes, which reduces the size of the location cache stored on your machine, and prevents an automatic back-up through iTunes.

Good news, right?

I don’t think so. Apple is still collecting this data, still getting this data from you, and still using it. The only difference is that you can’t use your own data.

Location data is extremely useful. That’s why Apple, Google, and Microsoft are collecting it. Over the last year, Apple has, intentionally or not, created what is likely the largest locational database ever. This is a hugely, massively, ridiculously useful database. And with this new update, Apple are the only ones who will be able to get their hands on it. I believe that our data should be… well, our data. We should be able to store it securely, explore it, and use it for any purposes that we might choose. This data would be extraordinarily useful for researchers – people studying how diseases spread, trying to solve traffic-flow problems, and researching human mobility.

With all of this in mind, some colleagues and I have been working on a project for the last week called openpaths.cc. It lets you upload your location data from your iDevice, securely store it, explore it via a map interface, and we’ll eventually offer you a system to directly donate your data to well-deserving research projects.

We’re pushing this project out quickly in hopes that we can gather as many location files as we can before people upgrade iOS and iTunes.

Visit openpaths.cc now to upload, explore, and securely store your iDevice location data.

We are existing a world where data is being collected about us on a massive scale. This data is currently being stored, analyzed and monetized by corporations – there is little or no agency for the people to whom the data actually belongs. I believe that grass-roots initiatives like openpaths.cc can provide a framework for how data sovereignty can be established and managed.

In the short term, I am hoping we can collect and store enough locational data to be of use to researchers. So please, before you upgrade iOS and iTunes, visit openpaths.cc and make your own data your own data. And please (please) – pass this on.

8 Comments

Random Number Multiples

By Jer | February 1, 2011

Random Number Multiples - RGB

About seven years ago, I had a bit of a career crisis. I was freelancing – working for clients I didn’t care much about on projects that I didn’t care much about, and feeling that there was a huge distance between the work that I was creating and my physical self. I was sick of computers, and was considering a range of (in hindsight) ridiculous vocational changes.

My rescue didn’t come from a new programming language, or a faster computer, or even better clients. It came, instead, from a return to the physical. I learned how to screenprint, and made rock posters for local bands, out of my living room. Every weekend, a friend and I would rack paper, pull squeegees, make an enormous mess – and escape from all of our pixel-based problems. We kept it up for a few years; after I moved into a larger, cleaner, less ink-friendly place I put my screens into storage. Even though I stopped printing, that time I spent screenprinting turned the rest of my career in a more creative direction.

Imagine how happy I was, then, to be asked by curator Christina Vassallo to be part of the inaugural edition of her Random Number Multiple series – a project that would produce screenprints from the work of computational artists and designers. Even better, this first edition would pair me with Marius Watz, an artist who has been a huge inspiration to me over the years, and whose work is exceptional in every way.

Marius and Christina and I spent three days at Bushwick Print Lab printing each of the 200 prints by hand. It was a fantastic experience, and the results, I think, speak for themselves. Marius’ prints are explosions of colour, vivid, dramatic pseudo-random that really capture the eye:

RN Multiples 5146 Marius Watz - Arcs04-01

I made two prints. Both are abstractions of my word frequency visualizations that I created using Processing and the NYTimes Article Search API. The first, titled ‘RGB – NYT Word Frequency’, shows usage of the words ‘red’, ‘green’, ‘blue’ in the Times between 1981 and 2011 (you can see a series of details from the print here):

Jer Thorp, "RGB - NYTimes Word Frequencies"

Random Number Multiples - RGB

This print turned out even better than I could have expected. The fine detail is amazing, the colours are rich and vivid, and the half-toning on the individual bars creates a jewel-like halo in the center that is fascinating to look at up close.

My second print visualizes the terms ‘hope’ and ‘crisis’ over the same time period (again, more detailed views can be found here). This print was made with a semi-reflective ink, so it has a unique shimmer to it when viewed in the light:

RN Multiples 5235 Jer Thorp, Hope-Crisis

Overall, I was surprised and delighted by how well this computer-generated work translated to the traditional medium of screenprint. I will definitely be looking to make more prints in the future.

In the meantime, a limited number of both of these prints are available for sale at on the Random Number Multiples site. Prints are $100, made with entirely acid-free media, and ship with a signed certificate of authenticity.

Random Number Multiples - RGB

1 Comment

Angry Birds & Box2D: An Open Source Holiday Wish

By Jer | December 13, 2010

I have been spending far too much of my time over the last week or so playing Angry Birds. It’s a simple, clever, and addictive game which seems to have captivated large part of the human population (just yesterday, I heard a woman on the subway exclaim: “Take that, you %$!# pigs!”). Along with immense popularity, the game has also brought in millions upon millions of dollars for Rovio, the Finnish game company who created the concept and built the game. Though exact figures are unclear, the game has had upwards of 50M downloads, and brings in $1M per month in ad revenue alone. It’s likely that Angry Birds has made upwards of 100 million dollars.

For those that haven’t played, the gameplay is straight-forward: you launch birds out of a slingshot, in an attempt to collapse structures that are protecting egg-thieving pigs (it’s more fun that it sounds). A large part of the effectiveness of the game comes from the fact that these structures – built from blocks, triangles, and cylinders of various materials, react with realistic physics; the blocks knock each other over, the cylinders roll down hills, and the triangles act as convenient ramps.

I can’t say this for sure, but it’s very very likely that Angry Birds is built on top of Erin Catto’s excellent Box2D physics engine. Box2D is a set of libraries for C++ which makes it easy to build rigid body physics simulations – which is, essentially, what Angry Birds is. [EDIT: It has been confirmed that Angry Birds does in fact use Box2D]

Box2D is released with a very liberal open source license – it can basically be used by anyone, for anything. The only requirement is that, if and when source is released, the code has to be attributed to Erin, and can’t be claimed as original. There is absolutely no legal requirement for anyone using Box2D to pay for it in any way.

But is there an ethical requirement? The founders of Rovio are very, very, very rich men – thanks to Angry Birds. If, indeed, Angry Birds relies as heavily on Box2D as I suspect, they are also very, very, very rich men thanks to Erin and Box2D.

I’ve often thought of open source as a gratitude economy – people maintain and distribute projects largely because they are fueled by the thanks that they receive. By releasing Box2D with such a generous license, Erin Catto was clearly aware that he wouldn’t be profiting from its use. Likely, he’s been happy seeing his project used in so many interesting ways. I can’t imagine that he ever expected someone to make such a ridiculous fortune from his code, on the scale of Rovio and Angry Birds.

Of course, Rovio may have built their own physics engine for Angry Birds. And, even if they didn’t, they are perfectly within their rights to keep every penny, and not say a word about Erin or about Box2D.

With Christmas just around the corner, though, I can’t help but imagine an ideal world – in which Erin Catto receives some kind of an unexpected bonus. An open source holiday wish?

27 Comments

tree.growth.redux

By Jer | November 28, 2010

tree.growth.redux by Christian Flaccus

Munich designer Christian Flaccus used my tree.growth source code to create this amazing print, which includes, along with a hugely detailed tree, all of the Processing code used to render the tree. It’s giant – about 84 x 120cm, and is printed at 400dpi.

Digital artists talk a lot about preservation techniques for flaky digital storage media – and indeed a solution that comes up fairly often is to transfer the code onto a much more permanent, more archive-friendly medium – paper. So I suppose this poster serves as an archive as well – I’ll hope that Christian takes good care of it.

4 Comments