{"id":12849,"date":"2021-11-22T18:36:46","date_gmt":"2021-11-22T23:36:46","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12849"},"modified":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","slug":"tr-96-16-maximal-length-common-non-intersecting-paths","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/","title":{"rendered":"TR-96-16: Maximal Length Common Non-Intersecting Paths"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-96-16: Maximal Length Common Non-Intersecting Paths\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\">Technical Report<\/a> TR-96-16<br>\nMay 1996<\/p>\n\n\n\n<h2 id=\"maximal-length-common-non-intersecting-paths\" class=\"wp-block-heading tr_t1\">Maximal Length Common Non-Intersecting Paths<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div class=\"tr_abstract\">\n<p>Given a set Pn of n points on the plane labeled with the integers {1&#8230; n} an increasing path of Pn is a sequence of points i1 &lt; &#8230; &lt; ik such that the polygonal path obtained by connecting ij to ij+1, j = 1&#8230; k-1 is non-self intersecting. We show that any point set on the plane admits an increasing path of length at least p2n. We also study the problem of \fnding the longest common increasing path of two convex point sets on the plane and give an O(n2 log n) time algorithm to \fnd such a path.<\/p>\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-96-16.pdf\">TR-96-16.pdf<\/a><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-96-16 May 1996 Maximal Length Common Non-Intersecting Paths Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia Abstract Given a set Pn of n points on the plane labeled with the integers {1&#8230; n} an increasing path of Pn is a sequence of points i1 &lt; &#8230; &lt; ik such that the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12155,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12849","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12849","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12849"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12849\/revisions"}],"predecessor-version":[{"id":12850,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12849\/revisions\/12850"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12155"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12849"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12849"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}