{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:32Z","timestamp":1787340692801,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1990,10]]},"abstract":"<jats:p>An operation that is frequently needed during the creation and manipulation of geometric models is the sorting of points along an algebraic curve. Given a segment $\\overset{\\lower0.5em\\hbox{$\\smash{\\scriptscriptstyle\\frown}$}}{AB}$ of an algebraic curve, a set of points on the curve is sorted from A to B along $\\overset{\\lower0.5em\\hbox{$\\smash{\\scriptscriptstyle\\frown}$}}{AB}$ by putting them into the order that they would be encountered in traveling continuously from A to B along $\\overset{\\lower0.5em\\hbox{$\\smash{\\scriptscriptstyle\\frown}$}}{AB}$. A new method for sorting points along a plane or space algebraic curve is presented. Key steps in this method are the decomposition of a plane algebraic curve into convex segments and point location in this decomposition. This new method can sort points on an arbitrary algebraic curve (including points spread over several connected components) and it is particularly efficient because of its preprocessing, both of which make it superior to conventional methods. The complexity of the new method is analyzed, and execution times of various sorting methods on a number of algebraic curves are presented. The theory developed for sorting can also be used to locate points on an arbitrary segment of an algebraic curve and to decide whether two points lie on the same connected component.<\/jats:p>","DOI":"10.1137\/0219065","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:33:47Z","timestamp":1109226827000},"page":"925-967","source":"Crossref","is-referenced-by-count":5,"title":["Sorting Points Along an Algebraic Curve"],"prefix":"10.1137","volume":"19","author":[{"given":"John K.","family":"Johnstone","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chanderjit L.","family":"Bajaj","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/040.1\/713043"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(88)90011-8"},{"key":"R3","volume-title":"The design and analysis of computer algorithms","author":"Aho A.","year":"1975"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/964967.801152"},{"key":"R5","unstructured":"T. Asano, T. Asano, H. Imai,  Partitioning a polygonal region into trapezoids, Tech. Report Res. Mem., RMI84-03, Department of Mathematics, Engineering, and Instrumentation Physics, University of Tokyo, Tokyo, Japan,  1984"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90002-9"},{"key":"R7","series-title":"Inst. Math. Appl. Conf. Ser. New Ser.","first-page":"3","volume-title":"The mathematics of surfaces, III (Oxford, 1989)","volume":"23","author":"Bajaj C.","year":"1989"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(88)90010-6"},{"key":"R9","unstructured":"C. Bajaj, A. Royappa,  GANITH: An algebraic geometry package, Tech. Report, CSD-TR-914, Department of Computer Science, Purdue University, West Lafayette, IN"},{"key":"R10","volume-title":"The Complexity of Robot Motion Planning","author":"Canny J. F.","year":"1987"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87806-9.50009-8"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/357337.357340"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07407-4_17"},{"key":"R14","volume-title":"Differential geometry of curves and surfaces","author":"do Carmo M.","year":"1976"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12689-9_105"},{"key":"R17","first-page":"347","volume-title":"Geometric modeling","author":"Hoffmann Christoph","year":"1987"},{"key":"R18","unstructured":"J. K. Johnstone, Ph.D. Thesis,  The sorting of points along an algebraic curve, Department of Computer Science, Cornell University, Ithaca, NY,  1987"},{"key":"R19","unstructured":"J. M. Keil, Ph.D. Thesis,  Decomposing polygons into simpler components, Department of Computer Science, University of Toronto, Toronto, Ontario, Canada,  1983"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"R21","volume-title":"A Catalog of Special Plane Curves","author":"Lawrence J. D.","year":"1972"},{"key":"R22","volume-title":"Principles of Interactive Computer Graphics","author":"Newman W. M.","year":"1979"},{"key":"R23","unstructured":"J. O'Rourke,  The complexity of computing minimum convex covers for polygons,  Proc. 20th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL,  1982,  75\u201384"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R25","unstructured":"J. R. Sack,  An  $O(n \\log n)$ algorithm for decomposing simple rectilinear polygons into convex quadrilaterals,  Proc. 20th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL,  1982,  64\u201374"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0217010"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/357346.357348"},{"key":"R28","volume-title":"Algebraic curves","author":"Walker R. J.","year":"1950"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0219065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:44:24Z","timestamp":1787337864000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0219065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,10]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1990,10]]}},"alternative-id":["10.1137\/0219065"],"URL":"https:\/\/doi.org\/10.1137\/0219065","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,10]]}}}