Thomas C. Shermer
Current Research

My research can be divided into three main areas: graph theory, computational geometry, and computer graphics.

I have research interests in both pure and applied aspects of graph theory. For example, with Arvind Gupta, I have been working on the theory of partial k-trees, from both a mathematical and complexity-theoretic viewpoint. With Art Liestman, I am working on theoretical network design and communications issues.

In computational geometry, which I would consider my main area, I work in a subarea called visibility. A typical visibility problem is the following: given a set of polygons in the plane, and two points p and q, determine if p sees q (i.e. determine if the line segment from p to q intersects any of the given polygons). In this situation, we are imagining that the polygons are visibility obstacles, such as a set of buildings in a field, and two people are located at p and q. Or perhaps the polygons are the shapes of furniture in a room, and I want to know if I can move a robot from p to q in a straight line without hitting any furniture. This notion of visibility plays a fundamental role in many computing areas, such as graphics, motion planning, shape recognition, and VLSI design. My favorite line of attack for visibility problems is to reduce them to (hopefully solvable) graph-theoretic problems. This relationship of graph theory and visibility is fundamental and there is still much to learn about it.

In computer graphics, my only recent research has been concerned with visual data access and user interfaces. However, I used to be a professional computer animator and still have an interest in many rendering and animation issues.

Back to my home page