Topology determination and isolation for implicit plane curves

ABSTRACT

A method is proposed to generate an isolation for a plane curve, which is a set of boxes covering the curve, having the same topology as the curve, and approximating the curve to any given precision. The method uses symbolic computation to guarantee correctness and uses interval analysis whenever possible to enhance efficiency. This leads to a quite effective hybrid method for plane curve isolation.

REFERENCES

• 1: 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]
• 2: Jin-San Cheng , Xiao-Shan Gao , Chee-Keng Yap, Complete numerical isolation of real zeros in zero-dimensional triangular systems, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277562]
• 3: Hoon Hong, An efficient method for analyzing the topology of plane real algebraic curves, Mathematics and Computers in Simulation, v.42 n.4-6, p.571-582, Nov. 1996
• 4: Ralph Martin , Huahao Shou , Irina Voiculescu , Adrian Bowyer , Guojin Wang, Comparison of interval methods for plotting algebraic curves, Computer Aided Geometric Design, v.19 n.7, p.553-587, July 2002 [doi>10.1016/S0167-8396(02)00146-2]
• 5: Raimund Seidel , Nicola Wolpert, On the exact computation of the topology of real algebraic curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064111]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms