{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T16:50:21Z","timestamp":1693414221716},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[1994,1]]},"abstract":"The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics and geometric and solid modeling. Previous algorithms are based on techniques from elimination theory or subdivision and iteration. The former is, however, restricted to low-degree curves. This is mainly due to issues of efficiency and numerical stability. In this article we use elimination theory and express the resultant of the equations of intersection as matrix determinant. The matrix itself rather than its symbolic determinant, a polynomial, is used as the representation. The problem of intersection is reduced to that of computing the eigenvalues and eigenvectors of a numeric matrix. The main advantage of this approach lies in itsefficency and robustness<\/jats:italic>. Moreover, the numerical accuracy of these operations is well understood. For almost all cases we are able to compute accurate answers in 64-bit IEEE floating-point arithmetic.<\/jats:p>","DOI":"10.1145\/174462.174617","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:00Z","timestamp":1027769340000},"page":"73-100","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Algorithms for intersecting parametric and algebraic curves I"],"prefix":"10.1145","volume":"13","author":[{"given":"Dinesh","family":"Manocha","sequence":"first","affiliation":[{"name":"Univ. of North Carolina, Chapel Hill"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[{"name":"Univ. of California, Berkeley"}]}],"member":"320","published-online":{"date-parts":[[1994,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"ANDERSON E. BAI Z. BIS('HIW C. DEMMFL J. D()N(;ARRA J. D~: CROZ J. GREENBAUM A. HAMMARLIN~; S. AN1) SOltENSb:N D. 1992. LAPACK User's Guide Release 1.0. SIAM Philadelphia Pa. ANDERSON E. BAI Z. BIS('HIW C. DEMMFL J. D()N(;ARRA J. D~: CROZ J. GREENBAUM A. HAMMARLIN~; S. AN1) SOltENSb:N D. 1992. LAPACK User's Guide Release 1.0. SIAM Philadelphia Pa.","DOI":"10.2172\/10136133"},{"key":"e_1_2_1_2_1","unstructured":"BARTELS R. H. BEaVT~ J. C. ANI~ BArSK~ B. A. 1987. An Intrtm'uction to Splines for Use in Computer (Iraphies and Geometric Modeling. Morgan Kaufmann San Mateo Calif. BARTELS R. H. BEaVT~ J. C. ANI~ BArSK~ B. A. 1987. An Intrtm'uction to Splines for Use in Computer (Iraphies and Geometric Modeling. Morgan Kaufmann San Mateo Calif."},{"key":"e_1_2_1_3_1","volume-title":"Part I. In Proceedings of the 6th SIAM Coati,fence on Parallel Processing for Scientific Computing, SIAM","author":"BAL Z.","year":"1993"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/152613.152617"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation. ACM","author":"COLLINS G. E.","year":"1992"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 1989 IEEE Control Systems Society Workshop on Computer-Aided Control System Design. IEEE, New York","author":"DEMMEL J.","year":"1989"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"ELBER G. AND COHEN E. 1990. Hidden curve removal for free form surfaces. Comput. Graph. 24 4 95 1(14. 10.1145\/97880.97890 ELBER G. AND COHEN E. 1990. Hidden curve removal for free form surfaces. Comput. Graph. 24 4 95 1(14. 10.1145\/97880.97890","DOI":"10.1145\/97880.97890"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"FAROUKI R. T. AND RAdAN V. T. 1987. On the numerical condition of polynomials in bernstein tbrm. ('omput. Aided (h o. Des. 4 3 191 216. 10.1016\/0167-8396(87)90012-4 FAROUKI R. T. AND RAdAN V. T. 1987. On the numerical condition of polynomials in bernstein tbrm. ('omput. Aided (h o. Des. 4 3 191 216. 10.1016\/0167-8396(87)90012-4","DOI":"10.1016\/0167-8396(87)90012-4"},{"key":"e_1_2_1_9_1","volume-title":"Lecture Notes in Computer Science","volume":"51","author":"GARROW B. S.","year":"1977"},{"key":"e_1_2_1_10_1","unstructured":"GOLUB G. H. AND VAN LOAN C F. 1989. Matrix Computations. John Hopkins Press Baltimore Md. GOLUB G. H. AND VAN LOAN C F. 1989. Matrix Computations. John Hopkins Press Baltimore Md."},{"key":"e_1_2_1_11_1","unstructured":"GOBBERG I. LANCASTER P. AND R()I)MAN L. 1982 Matrix Pol.vnomials. Academic Press New York GOBBERG I. LANCASTER P. AND R()I)MAN L. 1982 Matrix Pol.vnomials. Academic Press New York"},{"key":"e_1_2_1_12_1","first-page":"327","article-title":"Vector elimination: A technique for the imphcitization, inversion and intersection of planar parametric rational polynomial curves. ('omput. Aided Gee","author":"GOLDMAN R.","year":"1984","journal-title":"Des."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/108541.108546"},{"key":"e_1_2_1_14_1","unstructured":"HOFFMAN Nx C. M. 1989. Geometric and Solid Modeling. Morgan Kaufmann San Mateo Calif. HOFFMAN Nx C. M. 1989. Geometric and Solid Modeling. Morgan Kaufmann San Mateo Calif."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"KOPPAKAR P. A. ANI) Mt~laq~ S. P. 1983. A new class of algorithms fi)r the processing of parametric curves. (!omput. Aided Des. 1 5 1 41 45. KOPPAKAR P. A. ANI) Mt~laq~ S. P. 1983. A new class of algorithms fi)r the processing of parametric curves. (!omput. Aided Des. 1 5 1 41 45.","DOI":"10.1016\/S0010-4485(83)80050-5"},{"key":"e_1_2_1_16_1","first-page":"150","article-title":"A theoretical development fi)r the computer generation and display of piecewise polynmnial surfaces","volume":"2","author":"LANE","year":"1980","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."},{"key":"e_1_2_1_17_1","first-page":"3","volume-title":"Proceedings of London Mathematical Nociety","author":"MACUALAY F.","year":"1902"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"271","volume-title":"Proceedings of International Symp,,sium on Symboh'c and Algebraic Computations","author":"MANOCHA","year":"1990","DOI":"10.1145\/96877.96947"},{"key":"e_1_2_1_19_1","unstructured":"MANOCHA. D. 1992. Algebraic and numeric techniques fiw modeling and robotics. Ph.D. thesis Computer Science Div. Dept. of Electrical Engineering and Computer Science Univ. of Califi~rnia Berkeley Calif. MANOCHA. D. 1992. Algebraic and numeric techniques fiw modeling and robotics. Ph.D. thesis Computer Science Div. Dept. of Electrical Engineering and Computer Science Univ. of Califi~rnia Berkeley Calif."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"MANOCHA D. AND CANNY I. F. 1992. Detecting cusps and inflection points in curves. Computer Aided (;eomctric Design 9:1 24. 10.1016\/0167-8396(92)90050-Y MANOCHA D. AND CANNY I. F. 1992. Detecting cusps and inflection points in curves. Computer Aided (;eomctric Design 9:1 24. 10.1016\/0167-8396(92)90050-Y","DOI":"10.1016\/0167-8396(92)90050-Y"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(89)90126-7"},{"key":"e_1_2_1_23_1","unstructured":"SALMON G. 1885. Lessons Introductory to the Modern Higher Algebra. G. E. Stechert and Co. New York. SALMON G. 1885. Lessons Introductory to the Modern Higher Algebra. G. E. Stechert and Co. New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(89)90015-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(86)90025-7"},{"key":"e_1_2_1_26_1","unstructured":"SEDERBERG T. W. 1983. Implicit and parametric curves and surfaces. Ph.D. thesis Purdue Univ. West Lafayette Ind. SEDERBERG T. W. 1983. Implicit and parametric curves and surfaces. Ph.D. thesis Purdue Univ. West Lafayette Ind."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(86)80013-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(89)90024-1"},{"key":"e_1_2_1_29_1","unstructured":"STURMFELS B. 1991. Sparse elimination theory. In D. Eisenbud and L. Robbiano editors Computational Algebraic Geometry and Commutative Algebra. Cambridge University Press. STURMFELS B. 1991. Sparse elimination theory. In D. Eisenbud and L. Robbiano editors Computational Algebraic Geometry and Commutative Algebra. Cambridge University Press."},{"key":"e_1_2_1_30_1","unstructured":"WALKER R. J. 1950. Algebraic Curves. Princeton University Press New Jersey. WALKER R. J. 1950. Algebraic Curves. Princeton University Press New Jersey."},{"key":"e_1_2_1_31_1","unstructured":"WILKINSON J. H. 1965. The Algebraic Eigenvalue Problem. Oxford University Press Oxford U.K. WILKINSON J. H. 1965. The Algebraic Eigenvalue Problem. Oxford University Press Oxford U.K."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/BF01386381","article-title":"The evaluation of the zeros of ill-conditioned polynomials. Parts i and ii","volume":"1","author":"WILKINSON J. H.","year":"1959","journal-title":"Num. Math."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/174462.174617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,23]],"date-time":"2023-04-23T17:28:02Z","timestamp":1682270882000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/174462.174617"}},"subtitle":["simple intersections"],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1145\/174462.174617"],"URL":"http:\/\/dx.doi.org\/10.1145\/174462.174617","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[1994,1]]},"assertion":[{"value":"1994-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}