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

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.

36 thoughts on “All The Names: Algorithmic Design and the 9/11 Memorial”

  1. Great read, and a beautiful project to work on. Just wondering: did you consider (or use) some sort of genetic algorithm to find the best layout?

  2. This was a really great post, thanks for writing it. I'm new to the world of Data Visualization but have been really intrigued by your real-world examples. Your comments at the end about the weight of information was right on the money. Too often people forget the real meaning behind numbers.

  3. So inspiring! For me this story sums up one of the things that we in the rest of the world respect most about America: the can-do attitude in finding an ingenious way to follow through a vision some would write off as too challenging, without compromise.

  4. Pingback: eyes open
  5. Brilliant! Thoughtful process and innovative code: Your SOP. I'm intrigued by the architect's storytelling-oriented vision for the monument vis-a-vis the visiting families and friends of those lost in the tragedy. Clearly, the connections tell an important story, but how will they find their loved one's engraved name? Perhaps your code could be extended to create a visitors' aid to locate the lost? A computer kiosk or mobile app? Just a thought, but more importantly an expression of thanks and appreciation for supporting such an important project.

  6. Wow this sounds like only a partially-automatable-problem. I'm really glad it seems that everyone involved agrees lots of manual man-hours will be required. I'd promise a maximum of 66% satisfaction with the outcome, with quickly decreasing marginal solution satisfaction added for each additional unit of work time. Yes, I say it can't satisfactorily be done. Additionally, a kiosk will be needed to help visitors find a certain name. In future, I think architects should incorporate holographs in the typography of this type of monument if they have any dream of solving this problem even half-satisfactorily.

  7. Though I love math, the concepts needed for such a project are beyond my understanding. However, I cannot help but think that the original vision of the connectedness, the adjacencies, was the best choice. Thanks for spending the time and effort to make it work, for the memories of those we lost that day.

  8. This story just made my day.

    Cynic that I am, I tend to lament what appears to me to be the ever decreasing robustness of the collective human condition. Then something like this comes along and gives me hope.

    Despite having a Ph.D. (pathology) and an MBA (technology management), math is not my strong suite. I know just enough to appreciate and basically understand the underlying concepts of the algorithm developed for this project. It’s simply brilliant ! The architect’s adjacency vision is a wonderful idea and here, someone with an extremely gifted mind has made it work. The achieved solution transcends just the routine application of a tool (math) and synthesizes understanding, skill, caring, passion, and ability to communicate into an extremely clever result. Again, simply brilliant. I’m awed and thrilled that people like this exist in our world.

  9. Why all this complication? Wouldn't it have been easier just to list the names Alphabetically, so that family members and friends could easily locate each name? Was anything done to make sure that the names of the terrorists were not included (I saw an article that the Pennsylvania memorial had included the terrorists. . which makes a mockery of the memorial).
    Another thing upsetting about this "Memorial" is that there will be no titles. . .if the person who died was a fireman or policeman or clergy. . those titles should be a part of this memorial.

  10. This project is incredible! It's great to see that more is still being done to honor all those who perished on that fateful day. It's also refreshing to see that such powerful minds can get together to accomplish something so positive in today's day and age.

    1. Yes Kevin I totally agree it's an amazing project to honor all the heros that died in 9/11 on that tragic day.

      "In late October, 2009, I received an e-mail from Jake Barton from Local Projects, titled plainly ‘Potential Freelance Job’."
      Total respect to Jake Barton for starting this whole project too.

    1. Unfortunately not. This algorithm is so closely tied to the architectural constraints of the memorial that it probably won't be useful out of context.

  11. Whoa that sure is an amazing journey and although painstaking as it should, it's only what we could do, only a little as compared to what they have lost. Remarkable!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>