Research Areas
My research areas lie in the mathematical theory of computation. I am particularly interested in Computational Geometry, Parallel Algorithms, String Pattern Matching, and Digital Topology. Many of the problems I have worked on are concerned with fundamental problems of geometric pattern recognition, with applications in image processing and computer vision.
Computational Geometry is concerned with questions of a geometric nature. Given a set S of n points in a Euclidean space, interesting questions include
which pair of members of S is closest to each other?
which pair of members of S is furthest from each other?
what is the convex hull of S?
can a given pattern P be replicated, or approximately replicated, by a subset of S?
Logo of the Honors Program,
U. of Michigan
These questions often have variations that are both interesting and harder to solve, e.g., we may ask these questions assuming that the members of S are not fixed points, but, rather, moving point-objects whose trajectory functions of time are known, with the solutions to be described as functions of time.
Applications of these questions are found in a variety of areas on the fringes of artificial intelligence, including pattern recognition and image processing, robotic vision systems, etc. These applications arise in diverse areas such as air traffic control and safety, astronomy (recognizing constellations) and biology (recognizing a species), optical character recognition, matching faces or fingerprints, etc.
For each of the problems described above and many others, we are interested not only in producing correct answers, but also in doing so as efficiently as possible, i.e., using as little computer time and/or memory as possible. These are questions that may use considerable computing resources, so that algorithms that are efficient in their use of time and/or memory are desired.
Parallel Algorithms describes research to solve problems on parallel computers. Many problems require such massive resources of time and memory that traditional single-processor computers cannot produce solutions in acceptable time. Increasingly, parallel computers are used for such problems.
A parallel computer may have only a few, or as many as thousands, of processors, among which a problem's data is distributed. The processors work in parallel on their shares of the data, so that the problem may be solved faster than on a serial computer. My work with parallel algorithms is largely concerned with problems in fundamental operations, computational geometry, image processing, and string pattern matching.
PRAM (Parallel Random Access Machine) (left), Hypercube (right) parallel computer architectures
A central problem of String Pattern Matching may be described as follows. Given two character strings, P (the "pattern") and T (the "text"), where T has at least as many characters as P, find every substring of T that's a copy (exact, or with a small number of deviations) of P. For example:
Input
T: Fourscore and seven years ago, our forefathers brought upon this continent
P: our
Output
exact matches only:
T: Fourscore and seven years ago, our forefathers brought upon this continent
matches allowing deviations of at most one character:
T: Fourscore and seven years ago, our forefathers brought upon this continent
Solutions to this problem enable "Find" operations of word processors and Web search engines; they also enable molecular biologists to locate strands of DNA in a genome or protein fragments in protein complexes.
Image Processing and Digital Topology are concerned with the mathematical theory of image processing, with applications in image understanding and computer animation. Since a digital image is made up of discrete "pixels" (dots) much like the grainy photographs often seen in old newspapers, it is for many purposes not practical to consider a digital image as a "continuous" body in a Euclidean space. Thus, fundamental notions of analysis and topology (e.g., connectedness, continuous function, continuous deformation) must be reformulated so as to capture their "flavor" in the setting of a digitized image.
Roughly, Image Processing is concerned with the development of algorithms to process digital images; Digital Topology is concerned with translating into the framework of digitized images our understanding of properties from both geometric and algebraic topology originally developed in the framework of Euclidean space.
Video on a digital topology version of the Borsuk-Ulam Theorem, by my collaborator, P. Christopher Staecker
Before getting into computer science, I was a researcher in Geometric Topology, a branch of mathematics concerned with properties of "the geometry of form." Most of these papers are concerned with hyperspaces, the Theory of Retracts, and the Theory of Shape. Although I have done little in these areas since 1987, they continue to influence my outlook on computational geometry and digital topology, and they have been sources of insight for some of my recent papers.
Am I a calm person? At one time, I was a leading researcher on the shape-theoretic property of calmness, a topic of several of my papers in geometric topology.
My research in digital topology led me to introduce the notion of a shy map. I have since modified this notion as an object of interest in geometric topology.
"Warsaw Circle," an example of lots of neat topological properties, including:
Connected but not locally connected;
Simply connected but not contractible;
Shape of a circle but not homotopic to a circle.
"