The incremental construction of a (weighted) Delone complex generates a hierarchy of simplicial grids in form of a directed acyclic graph. We implement and develop this DAG as an abstract data type. Applications of this data type currently pursued are the construction and maintenance of cartograms and multigrid solutions to finite-element problems.

We develop algorithms and software for modeling and analyzing biomolecules as geometric entities. Think of a molecule as a union of spherical balls, one per atom. The (weighted) Voronoi cells decompose the union into closed convex pieces. The nerve of the collection of pieces is a simplicial complex. This complex is the basic data structure that allows us to compute geometric and topological properties of the molecule. The software will be extended and applied to the protein-ligand docking problem and to molecular dynamics.

Geometric modeling questions are typically studied relative to an overall approach or data structure, such as the framework of constructive solid geometry (CSG) or boundary representations, etc. The idea of representing objects by simplicial complexes is old and well developed in the area of algebraic topology. The algorithmic aspects of simplicial complexes are not well understood though. We develop techniques towards a fully general modeling system based on simplicial complexes. In this system, operations such as the intersection of two objects will be translated into a Boolean operation on sets of simplices. This shifts the traditional difficulties with numerical robustness to one of satisfactory approximation by subcomplexes.

This research is aimed at bridging the gap between functional and imperative programming. Imperative lambda calculus is an extension of the typed lambda calculus with new types, such as references, observers, and commands. A state-dependent computation is called an observer and commands are viewed as transformations of observers. The language has a reduction semantics and satisfies the crucial properties of Church-Rosser and strong normalization. It also has a constructive logic interpretation whereby the novel constructs can be viewed as the introduction or elimination operators for a new quantifier. Thus, impera- tive lambda calculus forms a foundation for a new synthe- sis of functional and imperative programming paradigms. Further theoretical properties of this formal system are being investigated.

We are currently investigating a variety of problems in combinatorial algorithms, including algorithms for search problems (unbounded, unimodal, bimodal, and error-prone), graph drawing, scheduling, and pursuit (discrete and continuous). We are also applying combinatorial methods to the solution of divide-and-conquer recurrence relations.

* Denotes principal investigator.