Homotopy techniques for real-time visualization of geometric tangent problems

ABSTRACT

(MATH) This note accompanies a video presentation on the use of homotopy methods for real-time visualizing a class of geometric tangent problems in $\RR³.

REFERENCES

• 1: P. Agarwal, B. Aronov, and M. Sharir. Line transversals of balls and smallest enclosing cylinders in 3 dim. Discrete Comput. Geom., 21:373--388, 1999.
• 2: http://www.coin3d.org.
• 3: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry, vol. 185 of GTM. Springer, New York, 1998.
• 4: O. Devillers, V. Dujmovic, H. Everett et. al. A linear bound on the expected number of visibility events. Preprint, 2002.
• 5: O. Devillers, B. Mourrain, F. Preparata, and P. Trébuchet. On circular cylinders by 4 or 5 points in space. Technical Report 4195, INRIA Lorraine, 2001.
• 6: Christoph M. Hoffmann , Bo Yuan, On Spatial Constraint Solving Approaches, Revised Papers from the Third International Workshop on Automated Deduction in Geometry, p.1-15, September 25-27, 2000
• 7: I. Macdonald, J. Pach, and T. Theobald. Common tangents to four unit balls in $\mathbbR^3$. Discrete Comput. Geom., 26:1--17, 2001.
• 8: U. Kortenkamp and J. Richter-Gebert. Dynamic geometry I: The problem of continuity. In Proc. European Workshop Comput. Geom. 1999, 51--53.
• 9: E. Schömer, J. Sellen, M. Teichmann, and C. Yap. Smallest enclosing cylinders. Algorithmica, 27:170--186, 2000.
• 10: (MATH) 10. F. Sottile, T. Theobald. Lines tangent to 2n-2 spheres in $\RRn. To appear in Trans. Am. Math. Soc.
• 11: Thorsten Theobald, An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$, SIAM Journal on Computing, v.31 n.4, p.1212-1228, 2002 [doi>10.1137/S009753970038050X]
• 12: (MATH) 12. T. Theobald. How to realize a given number of tangents to 4 unit balls in $\mathbbR3. To app. in Mathematika.
• 13: Jan Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.251-276, June 1999 [doi>10.1145/317275.317286]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory