[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Algebraic Methods for Computing Smallest Enclosing and Circumscribing Cylinders of Simplices

  • Published:
Applicable Algebra in Engineering, Communication and Computing Aims and scope

Abstract.

We provide an algebraic framework to compute smallest enclosing and smallest circumscribing cylinders of simplices in Euclidean space n. Explicitly, the computation of a smallest enclosing cylinder in 3 is reduced to the computation of a smallest circumscribing cylinder. We improve existing polynomial formulations to compute the locally extreme circumscribing cylinders in 3 and exhibit subclasses of simplices where the algebraic degrees can be further reduced. Moreover, we generalize these efficient formulations to the n-dimensional case and provide bounds on the number of local extrema. Using elementary invariant theory, we prove structural results on the direction vectors of any locally extreme circumscribing cylinder for regular simplices.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Agarwal, P.K., Aronov, B., Sharir, M.: Line transversals of balls and smallest enclosing cylinders in three dimensions. Discrete Comput. Geom. 21, 373–388 (1999)

    MathSciNet  MATH  Google Scholar 

  2. Bonnesen, T., Fenchel, W.: Theorie der konvexen Körper. Springer-Verlag, Berlin, 1934

  3. Brandenberg, R.: Radii of Convex Bodies. Ph.D. thesis, Dept. of Mathematics, Technische Universität München, 2002. http://tumb1.biblio.tu-muenchen.de/publ/diss/ ma/2002/brandenberg.html~

  4. Brandenberg, R.: Radii of regular polytopes. Preprint, 2003. math.GM/0308121

  5. Brandenberg, R., Theobald, T.: Radii minimal projections of simplices and constrained optimization of symmetric polynomials. Preprint, 2003. math.MG/0311017

  6. Chan, T.M.: Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Internat. J. Comp. Geom. Appl. 12, 67–85 (2002)

    Article  MATH  Google Scholar 

  7. Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. UTM, Springer-Verlag, New York, 1996, second edition

  8. Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, 185, Springer-Verlag, New York, 1998

  9. Coxeter, H.S.M.: Introduction to Geometry. John Wiley & Sons, 1961

  10. Devillers, O., Mourrain, B., Preparata, F.P., Trébuchet, Ph.: On circular cylinders through four or five points in space. Discrete Comput. Geom. 29, 83–104 (2002)

    Article  MATH  Google Scholar 

  11. Dos Reis, G., Mourrain, B., Rouillier, F., Trébuchet, Ph.: SYNAPS: An environment for symbolic and numeric computation. Proc. International Congress of Mathematical Software 2002, Beijing, 239-249, World Scientific, 2002

  12. Eggleston, H.G.: Notes on Minkowski geometry (I): Relations between the circumradius, diameter, inradius, and minimal width of a convex set. J. London Math. Soc. 33, 76–81 (1958)

    MATH  Google Scholar 

  13. Emiris, I., Canny, J.: Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symb. Comp. 20, 117–149 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  14. Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete mathematics. Addison-Wesley, 1989

  15. Greuel, G.-M., Pfister, G., Schönemann, H.: Singular 2.0. A computer algebra system for polynomial computations. Centre for Computer Algebra, University of Kaiserslautern, 2001. http://www.singular.uni-kl.de~

  16. Gritzmann, P., Klee, V.: Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom. 7, 255–280 (1992)

    MathSciNet  MATH  Google Scholar 

  17. Gritzmann, P., Klee, V.: Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program. 59A, 163–213 (1993)

    MathSciNet  MATH  Google Scholar 

  18. Gritzmann, P., Klee, V.: Computational convexity. In Handbook of Discrete and Computational Geometry (J.E. Goodman, J. O’Rourke, eds.), 491–515, CRC Press, Boca Raton, 1997

  19. Har-Peled, S., Varadarajan, K.: Projective clustering in high dimensions using core sets. Proc. ACM Symposium on Computational Geometry ‘02 (Barcelona), 312–318, 2002

  20. Hilbert, D., Cohn-Vossen, S.: Anschauliche Geometrie. Springer-Verlag, Berlin, 1932. Translation: Geometry and the Imagination. Chelsea Publ., New York, 1952

  21. Kupitz, Y.S., Martini, H.: Equifacial tetrahedra and a famous location problem. Math. Gazette 83, 464–467 (1999)

    MATH  Google Scholar 

  22. Macdonald, I.G., Pach, J., Theobald, T.: Common tangents to four unit balls in ℝ3. Discrete Comput. Geom. 26, 1–17 (2001)

    MathSciNet  MATH  Google Scholar 

  23. Schaal, H.: Ein geometrisches Problem der metrischen Getriebesynthese. In Sitzungsber., Abt. II, Österr. Akad. Wiss. 194, 39–53 (1985)

    Google Scholar 

  24. Schömer, E., Sellen, J., Teichmann, M., Yap, C.: Smallest enclosing cylinders. Algorithmica 27, 170–186 (2000)

    Article  MathSciNet  Google Scholar 

  25. Stanley, R.P.: Enumerative Combinatorics. Cambridge University Press, 1997

  26. Sottile, F., Theobald, T.: Lines tangent to 2n-2 spheres in ℝn. Trans. Amer. Math. Soc. 354, 4815–4829 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  27. Sturmfels, B.: Solving Systems of Polynomial Equations. CBMS series, 97, AMS, Providence, 2002

  28. Sturmfels, B.: Algorithms in Invariant Theory. RISC Series in Symbolic Computation, Springer-Verlag, Wien, 1993

  29. Theobald, T.: Visibility computations: From discrete algorithms to real algebraic geometry. In S. Basu and L. Gonzalez-Vega (eds.), Algorithmic and Quantitative Real Algebraic Geometry in Mathematics and Computer Science, AMS DIMACS series, 60, 207–219 (2003)

    Google Scholar 

  30. Verschelde, J.: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Software 25, 251–276 (1999)

    Article  MATH  Google Scholar 

  31. Weißbach, B.: Über die senkrechten Projektionen regulärer Simplexe. Beitr. Algebra Geom. 15, 35–41 (1983)

    Google Scholar 

  32. Weißbach, B.: Über Umkugeln von Projektionen regulärer Simplexe. Beitr. Algebra Geom. 16, 127–137 (1983)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Zentrum Mathematik, Technische Universität München, Boltzmannstr. 3, 85747, Garching bei, München

    René Brandenberg & Thorsten Theobald

Authors
  1. René Brandenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thorsten Theobald
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to René Brandenberg.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brandenberg, R., Theobald, T. Algebraic Methods for Computing Smallest Enclosing and Circumscribing Cylinders of Simplices. AAECC 14, 439–460 (2004). https://doi.org/10.1007/s00200-003-0146-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00200-003-0146-0

Keywords

Search

Navigation