An approximate arrangement algorithm for semi-algebraic curves

ABSTRACT

We present an arrangement algorithm for plane curves. The inputs are (1) continuous, compact, x-monotone curves and (2) a module that computes approximate crossing points of these curves. There are no general position requirements. We assume that the crossing module output is ε accurate, but allow it to be inconsistent, meaning that three curves are in cyclic y order over an x interval. The curves are swept with a vertical line using the crossing module to compute and process sweep events. When the sweep detects an inconsistency, the algorithm breaks the cycle to obtain a linear order. We prove correctness in a realistic computational model of the crossing module. The number of vertices in the output is V=2n+N+min(3kn,n²/2) and the running time is O(V log n) for n curves with N crossings and k inconsistencies. The output arrangement is realizable by curves that are O(ε+kn&3949;) close to the input curves, except in knε neighborhoods of the curve tails. The accuracy can be guaranteed everywhere by adding tiny horizontal extensions to the segment tails, but without the running time bound. An implementation is described for semi-algebraic curves based on a numerical equation solver. Experiments show that the extensions only slightly increase the running time and have little effect on the error. On challenging data sets, the number of inconsistencies is at most 3N, the output accuracy is close to ε, and the running time is close to that of the standard, non-robust floating point sweep.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: Behnke, Bachmann, Fladt, and Kunle. Fundamentals of Mathematics, Volume II: Geometry. MIT Press, Cambridge, MA, 1974.
• 3: 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
• 4: Arno Eigenwillig , Lutz Kettner , Elmar Schömer , Nicola Wolpert, Complete, exact, and efficient computations with cubic curves, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997879]
• 5: Eyal Flato , Dan Halperin , Iddo Hanniel , Oren Nechushtan , Eti Ezra, The design and implementation of panar maps in CGAL, Journal of Experimental Algorithmics (JEA), 5, p.13-es, 2000 [doi>10.1145/351827.384255]
• 6: Nicola Geismann , Michael Hemmer , Elmar Schömer, Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually!, Proceedings of the seventeenth annual symposium on Computational geometry, p.264-273, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378689]
• 7: J. Keyser, T. Culver, M. Foskey, S. Krishnan, and D. Manocha. ESOLID—a system for exact boundary evaluation. Computer-Aided Design, 36(2):175--193, 2004.
• 8: J. Keyser, T. Culver, D. Manocha, and S. Krishnan. Efficient and exact manipulation of algebraic points and curves. Computer Aided Design, 32:649--662, 2000.
• 9: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 10: V. Milenkovic and K. Daniels. Translational polygon containment and minimal enclosure using mathematical programming. International Transactions in Operational Research, 6:525--554, 1999.
• 11: Victor J. Milenkovic, Rotational polygon containment and minimum enclosure using only robust 2D constructions, Computational Geometry: Theory and Applications, v.13 n.1, p.3-19, May 1999 [doi>10.1016/S0925-7721(99)00006-1 ]
• 12: V. J. Milenkovic. Shortest path geometric rounding. Algorithmica, 27(1):57--86, 2000.
• 13: V. J. Milenkovic. Densest translational lattice packing of non-convex polygons. Computational Geometry: Theory and Applications, 22:205--222, 2002.
• 14: B. Mourrain, J.-P. Técourt, and M. Teillaud. Sweeping an arrangement of quadrics in 3d. In Proceeding of the 19th European Workshop on Computational Geometry, pages 31--34, 2003.
• 15: Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006 [doi>10.1016/j.comgeo.2004.02.007]
• 16: H. Stetter and W. Auzinger. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Conference in Numerical Analysis, volume 86 of International Series on Numerical Mathematics, pages 11--30. Birkhauser, 1988.
• 17: 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
• 18: N. Wolpert. Jacobi curves: computing the exact topology of arrangements of non-singular algebraic curves. In Proceedings of the 11th ACM Symposium on Algorithms, pages 532--543, 2003.
• 19: Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

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

Keywords:
arrangements, robust computational geometry