{"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":"2021-11-22T18:36:46","modified_gmt":"2021-11-22T23:36:46","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":"

Carleton University
\nTechnical Report<\/a> TR-96-16
\nMay 1996<\/p>\n

Maximal Length Common Non-Intersecting Paths<\/h2>\n
\n
\n
\n
\n
\n
\n
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Given a set Pn of n points on the plane labeled with the integers {1… n} an increasing path of Pn is a sequence of points i1 < … < ik such that the polygonal path obtained by connecting ij to ij+1, j = 1… 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

TR-96-16.pdf<\/a><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

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… n} an increasing path of Pn is a sequence of points i1 < … < ik such that the […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12155,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-96-16: Maximal Length Common Non-Intersecting Paths - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-96-16 May 1996 Maximal Length Common Non-Intersecting Paths Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc,\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/\",\"name\":\"TR-96-16: Maximal Length Common Non-Intersecting Paths - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-22T23:36:46+00:00\",\"dateModified\":\"2021-11-22T23:36:46+00:00\",\"description\":\"Carleton University Technical Report TR-96-16 May 1996 Maximal Length Common Non-Intersecting Paths Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1996\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-96-16: Maximal Length Common Non-Intersecting Paths\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-96-16: Maximal Length Common Non-Intersecting Paths - School of Computer Science","description":"Carleton University Technical Report TR-96-16 May 1996 Maximal Length Common Non-Intersecting Paths Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc,","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/","name":"TR-96-16: Maximal Length Common Non-Intersecting Paths - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-22T23:36:46+00:00","dateModified":"2021-11-22T23:36:46+00:00","description":"Carleton University Technical Report TR-96-16 May 1996 Maximal Length Common Non-Intersecting Paths Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-16-maximal-length-common-non-intersecting-paths\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1996","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/"},{"@type":"ListItem","position":5,"name":"TR-96-16: Maximal Length Common Non-Intersecting Paths"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12849"}],"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\/49"}],"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}