Visibility computations: From discrete algorithms to real algebraic geometry

Thorsten Theobald (Technische Universitaet Muenchen):
Visibility Computations: From Discrete Algorithms to Real Algebraic Geometry

We investigate visibility problems with moving viewpoints in $\mathbb{R}^3$ that naturally arise when representing a crystal by a set of balls. Algorithmic solutions to these problems lead to some fundamental geometric problems, such as: Under which conditions do four unit balls in $\mathbb{R}^3$ have only finitely many common tangent lines? What is the maximum number of tangents in the finite case?

In [1] it is shown that if the four centers are not collinear then finiteness is guaranteed, and the maximum number of common tangents is 12. In this talk, we also discuss the underlying enumerative geometry problems when the bodies are combinations of polytopes and balls. In particular, we compute some tight bounds for the maximum number of common tangent lines in these cases.

References:
[1] I.G. Macdonald, J. Pach, T. Theobald: Common tangents to four unit balls in R^3, Discrete and Computational Geometry 26(1), pp. 1-17, 2001
[2] T. Theobald: An enumerative geometry framework for algorithmic line problems in R^3, Manuscript, 2001

Sylvain Lazard

Last modified: Mon Dec 17 12:15:55 MET 2001