Abstract
We present a complete, exact and efficient implementation to compute the adjacency graph of an arrangement of quadrics, i.e. surfaces of algebraic degree 2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the adjacency graph of the arrangement. Our implementation is complete in the sense that it can handle all kinds of inputs including all degenerate ones, i.e. singularities or tangential intersection points. It is exact in that it always computes the mathematically correct result. It is efficient measured in running times, i.e. it compares favorably to the only previous implementation.
Project co-funded by the European Commission within FP6 (2002–2006) under contract No. IST-006413.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Proc. 2nd GI Conf. on Automata Theory and Formal Languages. LNCS, vol. 6, pp. 134–183. Springer, Berlin (1975) Reprinted with corrections in: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 85–121. Springer, Heidelberg (1998)
Schömer, E., Wolpert, N.: An exact and efficient approach for computing a cell in an arrangement of quadrics (Special Issue on Robust Geometric Applications and their Implementations). Computational Geometry: Theory and Applications 33, 65–97 (2006)
Mourrain, B., Técourt, J.-P., Teillaud, M.: Sweeping of an arrangement of quadrics in 3D (Special issue, 19th European Workshop on Computational Geometry). Computational Geometry: Theory and Applications 30, 145–164 (2005)
Berberich, E., Hemmer, M., Kettner, L., Schömer, E., Wolpert, N.: An exact, complete and efficient implementation for computing planar maps of quadric intersection curves. In: SCG 2005. Proceedings of the twenty-first annual symposium on Computational geometry, pp. 99–106. ACM Press, New York, USA (2005)
Dupont, L., Lazard, D., Lazard, S., Petitjean, S.: Near-optimal parameterization of the intersection of quadrics, parts I+II+III (accepted). J. Symbolic Computation (2007)
Stolfi, J.: Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, New York (1991)
Yun, D.Y.Y.: On square-free decomposition algorithms. In: SYMSAC 1976. Proceedings of the third ACM symposium on Symbolic and algebraic computation, pp. 26–35. ACM Press, New York, USA (1976)
Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: A descartes algorithm for polynomials with bit-stream coefficients. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 138–149. Springer, Heidelberg (2005)
Lazard, S., Pearanda, L.M., Petitjean, S.: Intersecting quadrics : An efficient and exact implementation. In: ACM Symposium on Computational Geometry - SoCG 2004, Brooklyn, NY, ACM Press, New York (2004)
Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Kettner, L., Mehlhorn, K., Reichel, J., Schmitt, S., Schömer, E., Wolpert, N.: EXACUS: Efficient and exact algorithms for curves and surfaces. In: 13th Annual European Symposium on Algorithms, pp. 155–166. Springer, Heidelberg (2005)
Austern, M.H.: Generic Programming and the STL. Addison-Wesley, Reading (1998)
Brönnimann, H., Kettner, L., Schirra, S., Veltkamp, R.: Applications of the generic programming paradigm in the design of CGAL. In: Jazayeri, M., Musser, D.R., Loos, R.G.K. (eds.) Generic Programming. LNCS, vol. 1766, pp. 206–217. Springer, Heidelberg (2000)
Hemmer, M., Kettner, L., Schömer, E.: Effects of a modular filter on geometric applications. Technical Report ECG-TR-363111-01, MPI Saarbrücken (2004)
Brown, W.S.: The subresultant PRS algorithm. ACM Trans. Math. Softw. 4(3), 237–249 (1978)
Collins, G.E., Akritas, A.-G.: Polynomial real root isolation using Descartes’ rule of sign. In: SYMSAC, pp. 272–275 (1976)
Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28(9), 643–647 (1979)
Brown, W.S.: On euclid’s algorithm and the computation of polynomial greatest common divisors. J. ACM 18, 478–504 (1971)
Langemyr, S.M.L.: The computation of polynomial GCD’s over an algebraic number field. J. Symbolic Computation 8, 429–448 (1989)
Granados, M., Hachenberger, P., Hert, S., Kettner, L., Mehlhorn, K., Seel, M.: Boolean operations on 3D selective nef complexes: Data structure, algorithms, and implementation. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 654–666. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dupont, L., Hemmer, M., Petitjean, S., Schömer, E. (2007). Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics. In: Arge, L., Hoffmann, M., Welzl, E. (eds) Algorithms – ESA 2007. ESA 2007. Lecture Notes in Computer Science, vol 4698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75520-3_56
Download citation
DOI: https://doi.org/10.1007/978-3-540-75520-3_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75519-7
Online ISBN: 978-3-540-75520-3
eBook Packages: Computer ScienceComputer Science (R0)