{"id":15056,"date":"2022-06-16T20:29:31","date_gmt":"2022-06-17T00:29:31","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15056"},"modified":"2026-06-08T15:34:48","modified_gmt":"2026-06-08T19:34:48","slug":"tr-213-parallel-algorithms-for-rectilinear-link-distance-problems","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/tr-213-parallel-algorithms-for-rectilinear-link-distance-problems\/","title":{"rendered":"TR-213: Parallel Algorithms for Rectilinear Link Distance Problems"},"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-213: Parallel Algorithms for Rectilinear Link Distance Problems\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/\">Technical Report<\/a>&nbsp;<strong>TR-213<\/strong><br>September 1992<\/p>\n\n\n\n<h2 id=\"parallel-algorithms-for-rectilinear-link-distance-problems\" class=\"wp-block-heading\">Parallel Algorithms for Rectilinear Link Distance Problems<\/h2>\n\n\n\n<p>Andrzej Lingas, Anil Maheshwari , J\u00f6rg-R\u00fcdiger Sack<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>We provide optimal parallel solutions to several link distance problems set in trapezoided rectilinear polygons. All parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random- access machine (EREW PRAM). Let P be a trapezoided rectilinear simple polygon with n vertices. In O(log n) time using 0( n\/log n) processors we can optimally compute<\/p>\n\n\n\n<p>1. minimum rectilinear link paths, or shortest paths in the L1 metric from any point in P to all vertices of P,<br>2. minimum rectilinear link paths from any segment inside P to all vertices of P,<br>3. the rectilinear window (histogram) partition of P,<br>4. both covering radii and vertex intervals for any diagonal of P,<br>5. a data structure to support rectilinear link distance queries between any two points in P (queries can be answered optimally in O(logn) time by a uniprocessor).<\/p>\n\n\n\n<p>Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best known sequential algorithm for this problem which used O(n logn) time and space. We develop techniques for solving link distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques for example to almost optimally compute the link diameter, the link center and the central diagonal of a rectilinear polygon.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-213.pdf\">TR-213.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-213September 1992 Parallel Algorithms for Rectilinear Link Distance Problems Andrzej Lingas, Anil Maheshwari , J\u00f6rg-R\u00fcdiger Sack Abstract We provide optimal parallel solutions to several link distance problems set in trapezoided rectilinear polygons. All parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random- access machine (EREW PRAM). [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11910,"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-15056","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15056","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=15056"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15056\/revisions"}],"predecessor-version":[{"id":24478,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15056\/revisions\/24478"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11910"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15056"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}