Dr. Laurence Boxer's 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

Logo of the Honors Program, U. of Michigan

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?

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.

PRAM (Parallel Random Access Machine), Hypercube parallel computer architectures	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 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 (presented below in the exact matching version of the problem):

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 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.

"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.

My older writings (pre-1987) are 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 am no longer active in these areas, 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.