Consider Crust
Strange topology at MIT
Crust is an algorithm for reconstructing surfaces of any topology. In other words, it is a method for digitally rendering any 3-D shape, using data in three-dimensional space as input. Such methods garner a lot of attention now a-days. Graphical simulation models are increasingly prominent for visualization and testing purposes in the field of particle physics. World of Warcraft and Second Life rely heavily on computationally intensive computer graphics, and scalable distributed systems in general. Perhaps the most complex system of all is the U.S. economy, whose governance is partly guided by the results of mathematical models as part of monetary policy and fiscal planning.
Crust was developed as a collaborative effort between two staff scientists at Xerox PARC, now known as Palo Alto Research Center, and a doctoral candidate at MIT. None of this happened recently. In fact, Crust hasn’t been semantically linked with the word “new” since its debut at the 1998 ACM SIGGRAPH Conference.
What is so special about Crust? How is it relevant to global central banks and economic policy officials? What about the Federal Reserve Bank? Patience, please. Tarry a bit longer with me. All will be revealed.
The Crust algorithm is special because it has certain features uncommon in most quantitative models, yet highly sought after. First, the Crust algorithm offers results with “provable” guarantees. Given a “good sample” from a smooth surface, Crust’s results are guaranteed. That is, Crust guarantees that its output is topologically correct, converging to the original surface with increasing faithfulness depending on the input data’s sampling density.
Graphical Computation using the Crust Algorithm: An MIT PIG-tacular!
Crust has another interesting feature. The Crust research team was aware of how difficult it was to accurately model real world phenomena. They express such sentiments in their peer-reviewed academic publications. At least one was unusually receptive to the shortcomings of mathematical models, due to random events and interactions in the wild, e.g. unexpected co-linearity. Manolis Kamvysellis did much of the implementation and testing work on the Crust project. He was the third member of the team, studying for his Ph.D. at MIT. Happily, he had the good sense to demonstrate the algorithm via this fine pink pig! Let’s do the same.
Recall that Crust’s criteria for acceptable sample density is dynamic. Sample size is surprisingly intuitive! It depends on how dense the available data points are. A single topological surface, such as Piggy, may have very detailed surfaces. Observe this near Piggy’s ears and snout. Other areas like the hindquarters are quite featureless. Yet Crust dynamically adjusts its smallest acceptable sample size accordingly. Even minimally detailed surfaces such as Piggy’s lower hind legs above the hooves can be reconstructed accurately.
Manolis wrote a short-form version of the original ACM journal publication: A New Voroni Based Reconstruction Algorithm, click to download as a pdf file. Google Chrome browser users may save directly to Google Docs, an option built into yesterday’s Chrome version 8.xxxx update.
To Be Continued….
Check back for Part 2 of Economic Models for Turbulent Times
Learn how and why crusty old Crust is relevant to the 2007 – 2010 economic and global financial crisis, and how it might be helpful going forward in 2011.
