Exact and efficient 2D-arrangements of arbitrary algebraic curves

ABSTRACT

We show how to compute the planar arrangement induced by segments of arbitrary algebraic curves with the Bentley-Ottmann sweep-line algorithm. The necessary geometric primitives reduce to cylindrical algebraic decompositions of the plane for one or two curves. We compute them by a new and efficient method that combines adaptive-precision root finding (the Bitstream Descartes method of Eigenwillig et al., 2005) with a small number of symbolic computations, and that delivers the exact result in all cases. Thus we obtain an algorithm which produces the mathematically true arrangement, undistorted by rounding error, for any set of input segments. Our algorithm is implemented in the EXACUS library AlciX. We report on experiments; they indicate the efficiency of our approach.

REFERENCES

• 1: J. Abbott: "Quadratic Interval Refinement for Real Roots". URL http://www.dima.unige.it/~abbott/. Poster presented at the 2006 Int. Symp. on Symb. and Alg. Comp. (ISSAC 2006).
• 2: P. K. Agarwal, M. Sharir: "Arrangements and Their Applications". In: J.-R. Sack, J. Urrutia (eds.) Handbook of Computational Geometry, 49--119. Elsevier, 2000.
• 3: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
• 4: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: J. L. Bentley , T. A. Ottmann, Algorithms for Reporting and Counting Geometric Intersections, IEEE Transactions on Computers, v.28 n.9, p.643-647, September 1979 [doi>10.1109/TC.1979.1675432]
• 6: E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, L. Kettner, K. Mehlhorn, J. Reichel, S. Schmitt, E. Schömer, N. Wolpert: "EXACUS: Efficient and exact algorithms for curves and surfaces". In: Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005), LNCS, vol. 3669. Springer, 2005 155--166.
• 7: Eric Berberich , Arno Eigenwillig , Michael Hemmer , Susan Hert , Kurt Mehlhorn , Elmar Schömer, A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons, Proceedings of the 10th Annual European Symposium on Algorithms, p.174-186, September 17-21, 2002
• 8: E. Berberich, E. Fogel, D. Halperin, K. Mehlhorn, R. Wein: "Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step". In: Proc. of the 15th Annual European Symposium on Algorithms (ESA 2007), 2007 To appear in Springer LNCS.
• 9: Eric Berberich , Michael Hemmer , Lutz Kettner , Elmar Schömer , Nicola Wolpert, An exact, complete and efficient implementation for computing planar maps of quadric intersection curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064110]
• 10: E. Berberich, L. Kettner: Linear-Time Reordering in a Sweep-line Algorithm for Algebraic Curves Intersecting in a Common Point. Research Report MPI-I-2007-1-001, Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany, 2007. URL http://domino.mpi-inf.mpg.de/internet/reports. nsf/NumberView/2007-1-001.
• 11: C. W. Brown: "Constructing Cylindrical Algebraic Decompositions of the Plane Quickly", 2002. URL http://www.cs.usna.edu/~wcbrown/. Unpublished.
• 12: B. Buchberger , George E. Collins , Rudiger Loos , Rudolf Albrecht, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 13: J. Caravantes, L. Gonzalez-Vega: "Computing the Topology of an Arrangement of Quartics". In: R. R. Martin, M. A. Sabin, J. R. Winkler (eds.) IMA Conference on the Mathematics of Surfaces, LNCS, vol. 4647. Springer, 2007 104--120.
• 14: B. F. Caviness, J. R. Johnson (eds.): Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation. Springer, 1998.
• 15: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 16: George E. Collins , Jeremy R. Johnson , Werner Krandick, Interval arithmetic in cylindrical algebraic decomposition, Journal of Symbolic Computation, v.34 n.2, p.145-157, August 2002 [doi>10.1006/jsco.2002.0547]
• 17: O. Devillers, A. Fronville, B. Mourrain, M. Teillaud: "Algebraic methods and arithmetic filtering for exact predicates on circle arcs". Computational Geom. 22 (2002) 119--142.
• 18: L. Ducos: "Optimizations of the Subresultant Algorithm". J. of Pure and Applied Algebra 145 (2000) 149--163.
• 19: Arno Eigenwillig, Short Communication: On multiple roots in Descartes' Rule and their distance to roots of higher derivatives, Journal of Computational and Applied Mathematics, v.200 n.1, p.226-230, March, 2007 [doi>10.1016/j.cam.2005.12.016]
• 20: Arno Eigenwillig , Michael Kerber , Nicola Wolpert, Fast and exact geometric analysis of real algebraic plane curves, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277570]
• 21: A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, N. Wolpert: "A Descartes Algorithm for Polynomials with Bit-Stream Coefficients". In: 8th International Workshop on Computer Algebra in Scientific Computing (CASC 2005), LNCS, vol. 3718, 2005 138--149.
• 22: Arno Eigenwillig , Lutz Kettner , Elmar Schömer , Nicola Wolpert, Exact, efficient, and complete arrangement computation for cubic curves, Computational Geometry: Theory and Applications, v.35 n.1, p.36-73, August 2006 [doi>10.1016/j.comgeo.2005.10.003]
• 23: Arno Eigenwillig , Lutz Kettner , Nicola Wolpert, Snap rounding of Bézier curves, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247101]
• 24: I. Z. Emiris , A. Kakargias , S. Pion , M. Teillaud , E. P. Tsigaridas, Towards and open curved kernel, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997882]
• 25: Joachim von zur Gathen , Thomas Lücking, Subresultants revisited, Theoretical Computer Science, v.297 n.1-3, p.199-239, 17 March 2003 [doi>10.1016/S0304-3975(02)00639-4]
• 26: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 27: C. G. Gibson, Elementary geometry of algebraic curves: an undergraduate introduction, Cambridge University Press, New York, NY, 1998
• 28: L. Gonzalez-Vega, T. Recio, H. Lombardi, M.-F. Roy: "Sturm-Habicht Sequences, Determinants and Real Roots of Univariate Polynomials". In {14}, pp. 300--316.
• 29: D. Halperin: "Arrangements". In: J. Goodman, J. O'Rourke (eds.) Handbook of Discrete and Computational Geometry, chap. 24. CRC Press, 2nd edn., 2004.
• 30: D. Halperin, E. Leiserowitz: "Controlled perturbation for arrangements of circles". Internat. J. of Comput. Geom. & Appl. 14 (2004) 277--310.
• 31: Dan Halperin , Christian R. Shelton, A perturbation scheme for spherical arrangements with application to molecular modeling, Computational Geometry: Theory and Applications, v.10 n.4, p.273-287, July 1, 1998 [doi>10.1016/S0925-7721(98)00014-5]
• 32: Iddo Hanniel , Ron Wein, An exact, complete and efficient computation of arrangements of Bézier curves, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236282]
• 33: J. Keyser, T. Culver, D. Manocha, S. Krishnan: "Efficient and exact manipulation of algebraic points and curves". Computer-Aided Design 32 (2000) 649--662.
• 34: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 35: K. Mehlhorn, R. Osbild, M. Sagraloff: "Reliable and Efficient Computational Geometry Via Controlled Perturbation". In: Automata, Languages and Programming, 33rd Internat. Colloquium (ICALP'06), Part I, LNCS, vol. 4051. Springer, 2006 299--310.
• 36: V. Milenkovic, E. Sacks: "An Approximate Arrangement Algorithm for Semi-algebraic Curves". Internat. J. of Comput. Geom. & Appl. 17 (2007) 175--198.
• 37: A. W. Strzebonski: "Cylindrical Algebraic Decomposition using validated numerics". J. of Symbolic Computation 41 (2006) 1021--1038.
• 38: R. J. Walker: Algebraic Curves. Princeton University Press, 1950.
• 39: Ron Wein, High-Level Filtering for Arrangements of Conic Arcs, Proceedings of the 10th Annual European Symposium on Algorithms, p.884-895, September 17-21, 2002
• 40: R. Wein, E. Fogel, B. Zukerman, D. Halperin: "2D Arrangements". In: CGAL-3.3 User and Reference Manual, 2007. URL http://www.cgal.org/Manual/.
• 41: R. Wein, B. Zukerman: Exact and Efficient Construction of Planar Arrangements of Circular Arcs and Line Segments with Applications. Tech. Rep. ACS-TR-121200-01, Tel Aviv University, Israel, 2006.
• 42: N. Wolpert: "Jacobi Curves: Computing the Exact Topology of Arrangements of Non-Singular Algebraic Curves". In: Proc. of the 11th Annual European Symposium on Algorithms (ESA 2003), LNCS, vol. 2832. Springer, 2003 532--543.
• 43: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999
• 44: Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory