{"id":12755,"date":"2021-11-20T18:39:07","date_gmt":"2021-11-20T23:39:07","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12755"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-257-isomorphic-triangulations-with-minimal-number-of-steiner-points","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-257-isomorphic-triangulations-with-minimal-number-of-steiner-points\/","title":{"rendered":"TR-257: Isomorphic Triangulations with Minimal Number of Steiner Points"},"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-257: Isomorphic Triangulations with Minimal Number of Steiner Points\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-1994\/\">Technical Report<\/a> <strong>TR-257<\/strong><br>\nDecember 1994<\/p>\n\n\n\n<h2 id=\"isomorphic-triangulations-with-minimal-number-of-steiner-points\" class=\"wp-block-heading tr_t1\">Isomorphic Triangulations with Minimal Number of Steiner Points<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Evangelos Kranakis &amp; Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<p>We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of two simple n vertex polygons P,Q with k, l reflex vertices, respectively. The \ffirst algorithm computes an isomorphism by introducing at most O((k + l)2) Steiner points and has running time O(n + (k + l)2). The second algorithm computes an isomorphism by introducing at most O(kl) Steiner points and has running time O(n + kl log n). The number of Steiner points introduced by the second algorithm is also optimal. This solves an open problem \ffirst proposed by Goodman and Pollack and subsequently elaborated by Aronov, Seidel and Souvaine (see [1]).<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR257.pdf\">TR-257.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-257 December 1994 Isomorphic Triangulations with Minimal Number of Steiner Points Evangelos Kranakis &amp; Jorge Urrutia Abstract We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of two simple n vertex polygons P,Q with k, l reflex vertices, respectively. The \ffirst algorithm computes an isomorphism by introducing at most [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11914,"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-12755","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12755","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=12755"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12755\/revisions"}],"predecessor-version":[{"id":12756,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12755\/revisions\/12756"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11914"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12755"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}