Calculating approximate curve arrangements using rounded arithmetic

ABSTRACT

We present here an algorithm for the curve arrangement problem: determine how a set of planar curves subdivides the plane. This algorithm uses rounded arithmetic and generates an approximate result. It can be applied to a broad class of planar curves, and it is based on a new definition of approximate curve arrangements. This result is an important step towards the creation of practical computer programs for reasoning about algebraic curves of high degree.

REFERENCES

• 1: Dennis S. Arnon , George E. Collins , Scott McCallum, An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space, Journal of Symbolic Computation, v.5 n.1-2, p.163-187, February/April 1988 [doi>10.1016/S0747-7171(88)80011-7]
• 2: 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]
• 3: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
• 4: G. E. Collins. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Lecture Notes in Computer Science, No. 85, Springer-Verlag, New York, 1975.
• 5: M. Coste, Thoms's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, Journal of Symbolic Computation, v.5 n.1-2, p.121-129, February/April 1988 [doi>10.1016/S0747-7171(88)80008-7]
• 6: Herbert Edelsbrunner and Ernst Peter Mucke. Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms. Technical Report UIUCDCS-R-87-1393, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, December 1987.
• 7: Daniel H. Greene and F. Frances Yao. Finiteresolution computational geometry. In 27th Annual Symposium on the Foundations of Computer Science, pages 143-152, IEEE, October 1986.
• 8: C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
• 9: Christoph M. Hoffmann. The Problem of Accuracy and Robustness in Geometric Computation. Technical Report CSD-TR-771, Computer Sciences Department, Purdue University, April 1988.
• 10: Christoph M. Hoffmann , John E. Hopcroft , Michael S. Karasick, Robust Set Operations on Polyhedral Solids, Cornell University, Ithaca, NY, 1987
• 11: M. S. Karasick, On the representation and manipulation of rigid solids, McGill University, Montreal, Que., Canada, 1989
• 12: M. Karsick, D. Lieber, and L. Nackman. Ejficient Delaunay Triangulation using Rational Arithmetic. IBM Research Report RC 14455, IBM Thomas J. Watson Research ,Center, P.O. Box 218, Yorktown Heights, NY 10598, To appear in 1989.
• 13: Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
• 14: Victor J. Milenkovic. Verifiable Implementations of Geometric Algorithms using Finite Precision Arithmetic. Technical Report CMU-CS-88-168, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, July 1988.
• 15: T. Ottmann , G. Theimt , C. Ullrich, Numerical stability of geometric algorithms, Proceedings of the third annual symposium on Computational geometry, p.119-125, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41970]
• 16: M. 0. Rabin. Probabilistic algorithms in finite fields. SIAM J. Comp., 9(2):273-280, May 1980.
• 17: D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
• 18: J. Schwartz and M. Sharir. On the 'piano movers' problem, ii. general techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math., 4:298-301, 1983.
• 19: Mark Segal , Carlo H. Séquin, Consistent calculations for solids modeling, Proceedings of the first annual symposium on Computational geometry, p.29-38, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323238]
• 20: Segal Segal , Carlo H. Sequin, Partitioning Polyhedral Objects into Nonintersecting Parts, IEEE Computer Graphics and Applications, v.8 n.1, p.53-67, January 1988 [doi>10.1109/38.490]
• 21: K. Sugihara. An approach to error-free solid modeling. In IMA Summer Program on Robotics, Institute for Mathematics and Applications, University of Minnesota, 1987.
• 22: A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1948. 2nd edition, 1951.
• 23: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory