We have developed Combinatorica, a Mathematica-based package for experiments in combinatorics and graph theory. Used at over 400 sites, Combinatorica is perhaps the most popular environment for combinatorial computing, and received an EDUCOM award as distinguished mathematics software for higher education. We have used Combinatorica extensively in our own research in discrete mathematics and algorithms.
With colleagues at Indiana, RPI, Bellcore, and Los Alamos, we are beginning the development of LINK, a comprehensive, portable, and efficient environment which we expect to become the standard tool for combinatorial computing. We are interested in applications of combinatorial computing, particularly in computational biology and data compression.
I am also interested in a variety of problems where the goal is to reconstruct a combinatorial or geometric object given the results of certain measurements or invariants of the object. My research in computational geometry has focused on problems in probing, the interactive reconstruction of geometric objects from projections. These problems arise in tactile sensing in robotics, optical character recognition (OCR), and medical imaging. We have applied our theoretical results in point probe decision trees as the foundation for a commercial OCR system.
Other reconstruction problems emerge in computational biology. In restriction site mapping, an enzyme is used to cut clones of molecules at particular patterns. The lengths of the resulting fragments can be measured and used to reconstructthe molecule. We have given algorithms of both practical and theoretical interest for this problem of reconstructing sets from pairwise distances. More recently, we have investigated DNA sequencing by hybridization, essentially reconstructing strings from substrings. Interesting algorithm problems can arise in any application. For example, exploiting special purpose-graphics hardware to render triangulated surfaces requires partitioning the surface into a small number of ``T-mesh'' strips. Our results on Hamiltonian triangulations provide the tools to construct good meshings, leading to heuristics which perform substantially better than others to date.