Determining the topology of real intersection of algebraic surfaces
-
摘要: 提出一个关于计算曲面实交集拓扑的有效算法, 其中曲面由有限多个实系数三元多项式所定义. 这个算法使用了实交集至多两个投影的拓扑信息. 在此过程中, 必须使得有限多个曲面满足一定的条件,这些条件通过线性坐标变换可以得到,并且应用一些方法来检测这些条件是否满足.Abstract: This paper gave an algorithm for computing in an efficient way the topology of the real intersection of algebraic surfaces, which are defined by a finite family of trivariate polynomials with coefficients in $\R$. The algorithm is based on the computation of the graphs which are the intersection of at most two projections. For this purpose, some conditions, which be obtained by some linearly change of coordinates were fultiued, and some methods for checking these conditions were presented.
-
Key words:
- algebraic surface /
- generic position /
- topology /
- subresultants sequence
-
[1] {1}BAJAJ C, HOFFMANN C M. Tracing surfaces intersection[J]. Comput Aided Geom Design, 1988(5): 285-307.{2}KEYSER J, CULVER T, MANOCHA D, et al. Efficient and exact manipulation of algebraic points and curves[J]. Comput Aided Geom Design, 2000(32): 649-662.{3} KEYSER J, CULVER T, MANOCHA D, et al. A library for efficient and exact manipulation of algebraic points and curves[C]//Proc 15th Annu ACM Sympos Comput Geom, 1999: 360-369.{4}SHARIR M. Arrangements and Their Applications[M]//SACK J. Handbook of Computational Geometry. North Holland: Elsevier, 2000: 49-119.{5}HALPERIN D, SHARIR M. Arrangements and Their Applications in Robotics: Recent Developments[C]//Proceedings of the Workshop on Algorithmic Foundations of Robotics. 1995: 495-511.{6}GONZALEZ-VEGA L, NECULA I. Efficient topology determination of implicitly defined algebraic plane curves[J]. Comput Aided Geom Design, 2002, 19(9): 719-743.{7}ALCAZ{A}R J G, SENDRA J R. Computation of the topology of algebraic space curves[J]. J Symbolic Comput, 2005,39(6): 719-744.{8} DAOUDA N D, BERNARD M, OLIVIER R. On the computation of the topology of a non-reduced implicit space curve[C]//Proceedings of the 21st International Symposium On Symbolic and Alyebraic Computation. New York: ACM, 2008: 47-54.{9} SHEN L Y, CHENG J S, JIA X H, Homeomorphic approximation of the intersection curve of two rational surfaces[J]. Computer Aided Goemetric Design, 2012, 29(8): 613-625.{10} BASU S, POLLACK R, ROY M F. Algorithms in real algebraic geometry [M]//Algorithms and Computation in Mathematics 10. Berlin: Springer-Verlag, 2003.{11}CHEN Y F. Lectures on Computer Algebra[M]. Beijing: Higher Education Press, 2009.{12}WOLPERT N. An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics[D]. Saarbr"ucken: Universit"ades Saarlandes 2002.{13}SCHOMER E, WOLPERT N. An exact and efficient approach for computing a cell in an arrangement of quadrics[J]. Computational Geometry: Theory and Applications, 2006, 33(1-2): 65-97.{14}COX D, LITTLE J, O'SHEA D. Ideals,Varieties,and Algorithms[M]. Berlin: Springer-Verlag. 2004.{15}COLLINS G E. Quantifier elimination for real closed fields by cylindrical algebraic decomposition[J]. Automata Theory and Formal Languages, 1975(33): 134-183.{16}ARNON D S, COLLINS G E, MCCALLUM S. Cylindrical algebraic decomposition I: The basic algorithm[J]. SIAM J Comput, 1984, 13(4): 865-877.{17} RUPPRECHT D. An algorithm for computing certified approximate GCD of n univariate polynomials[J]. J Pure Appl Algebra, 1999, 139: 255-284.
点击查看大图
计量
- 文章访问数: 1208
- HTML全文浏览量: 21
- PDF下载量: 2062
- 被引次数: 0