[home] - [up] |
Abstract: Computer graphics usually deals with three-dimensional scenes involving objects which are modeled by polyhedra or in an algebraic form. Many rendering techniques like, e.g., ray tracing consider straight lines and their intersection points with the objects of the scene. The set of all lines which are not obscured by any object forms a cell complex in the four-dimensional space of straight lines in three dimensions, called the visibility complex by Pocchiola and Vegter, who first investigated its combinatorial and topological properties. In the lecture, problems concerning the complexity of the three-dimensional visibility complex will be presented which is directly related to the efficiency of rendering algorithms. We will consider both, the worst case and the average case when objects are generated randomly and present some lower and upper bounds. But even for simple objects like convex polyhedra or spheres many open questions remain.
Colloquium - 16:00
Abstract: We start with a brief consideration of different concepts of isomorphism for convex polytopes (affine, combinatorial) and the question, under which conditions isomorphisms of the k-skeleta of polytopes can be extended to isomorphisms of the entire polytopes.
In the main part of the talk we will treat the algorithmic complexity of deciding whether two polytopes are isomorphic. Our first result is that this problem is at least as hard as the graph ismorphism problem, both with respect to the combinatorial as well as to the affine notion of isomorphism. Our second result is that, however, for any fixed dimension there is a polynomial time algorithm for the polytope isomorphism problem. This is obvious for the affine variant; for the combinatorial variant our algorithm relies on Luk's polynomial time algorithm for the graph isomorphism problem for graphs of bounded degree and a result due to Bayer on barycentric subdivisions.
The talk is based on joint work with Alexander Schwartz (TU Berlin).