{"id":12727,"date":"2021-11-17T19:11:12","date_gmt":"2021-11-18T00:11:12","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12727"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-237-scalable-and-architecture-independent-parallel-geometric-algorithms-with-high-probability-optimal-time","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-237-scalable-and-architecture-independent-parallel-geometric-algorithms-with-high-probability-optimal-time\/","title":{"rendered":"TR-237: Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time"},"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-237: Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time\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-237<\/strong><br>\nMarch 1994<\/p>\n\n\n\n<h2 id=\"scalable-and-architecture-independent-parallel-geometric-algorithms-with-high-probability-optimal-time\" class=\"wp-block-heading tr_t1\">Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Frank Dehne &amp; Katia Guimaraes<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly distributed random input data. Our methods apply to multicomputers with arbitrary interconnection network or bus system. The following problems are studied in this paper: (1) lower envelope of line segments, (2) visibility of parallelepipeds, (3) convex hull, (4) maximal elements, (5) Voronoi diagram, (6) all-nearest neighbors, (7) largest empty circle, and (8) largest empty hyperrectangle. Problems 2-8 are studied for d-dimensional space, d=O(1). We implemented and tested the lower envelope algorithm and convex hull algorithm (for d=3 and d=4) on a CM5. The results indicate that our methods are of considerable practical relevance.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR237.pdf\">TR-237.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-237 March 1994 Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time Frank Dehne &amp; Katia Guimaraes Abstract We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly distributed random input data. Our [&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-12727","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12727","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=12727"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12727\/revisions"}],"predecessor-version":[{"id":12728,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12727\/revisions\/12728"}],"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=12727"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12727"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}