{"id":15105,"date":"2022-06-18T19:18:19","date_gmt":"2022-06-18T23:18:19","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15105"},"modified":"2026-06-08T14:56:36","modified_gmt":"2026-06-08T18:56:36","slug":"tr-229-optimal-parallel-algorithms-for-direct-dominance-problems","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1993\/tr-229-optimal-parallel-algorithms-for-direct-dominance-problems\/","title":{"rendered":"TR-229: Optimal Parallel Algorithms for Direct Dominance 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-229: Optimal Parallel Algorithms for Direct Dominance 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-1993\/\">Technical Report<\/a>&nbsp;<strong>TR-229<\/strong><br>October 1993<\/p>\n\n\n\n<h2 id=\"optimal-parallel-algorithms-for-direct-dominance-problems\" class=\"wp-block-heading\">Optimal Parallel Algorithms for Direct Dominance Problems<\/h2>\n\n\n\n<p>Amitava Datta, 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 present optimal parallel solutions to direct dominance problems for planar point sets and provide an application. The algorithms presented here are deterministic and designed to run on the concurrent read exclusive write parallel random-access machine (CREW PRAM). In particular, we provide algorithms for counting the number of points that are directly dominated by each point of an n-point set and for reporting these point sets. The counting algorithm runs in 0(log n) time using 0( n) processors; the reporting algorithm runs in 0(log n) time using 0( n + k \/ log n) processors, where k is the size of the output. The algorithms are therefore optimal. As an application of our results, we present an algorithm for the maximum empty rectangle problem, which is work optimal in the expected case.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-229.pdf\">TR-229.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-229October 1993 Optimal Parallel Algorithms for Direct Dominance Problems Amitava Datta, Anil Maheshwari , J\u00f6rg-R\u00fcdiger Sack Abstract We present optimal parallel solutions to direct dominance problems for planar point sets and provide an application. The algorithms presented here are deterministic and designed to run on the concurrent read exclusive write parallel random-access machine [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11912,"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-15105","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15105","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=15105"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15105\/revisions"}],"predecessor-version":[{"id":24444,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15105\/revisions\/24444"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11912"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15105"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15105"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}