{"id":12725,"date":"2021-11-17T19:09:32","date_gmt":"2021-11-18T00:09:32","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12725"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-236-exact-and-approximate-computational-geometry-solutions-of-an-unrestricted-point-set-stereo-matching-problem","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-236-exact-and-approximate-computational-geometry-solutions-of-an-unrestricted-point-set-stereo-matching-problem\/","title":{"rendered":"TR-236: Exact and Approximate Computational Geometry Solutions of an Unrestricted Point Set Stereo Matching Problem"},"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-236: Exact and Approximate Computational Geometry Solutions of an Unrestricted Point Set Stereo Matching Problem\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-236<\/strong><br>\nMarch 1994<\/p>\n\n\n\n<h2 id=\"exact-and-approximate-computational-geometry-solutions-of-an-unrestricted-point-set-stereo-matching-problem\" class=\"wp-block-heading tr_t1\">Exact and Approximate Computational Geometry Solutions of an Unrestricted Point Set Stereo Matching Problem<\/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>In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like the Marr-Poggio algorithm, this means that we study how to solve the un- restricted basic subproblems created within such approaches, possibly yielding an improved overall performance of such methods.We present an O(n2+4k) time and O(n4) space algorithm for exact unrestricted stereo matching, where n represents the number of points in each set and k the number of depth levels considered. We generalize the notion of a \u000e-approximate solution for point set congruence to the stereo matching problem and present an O((e\/d)kn2+2k) time and O((e\/d)n2) space approximate algorithm for unrestricted stereo matching (\u000f represents measurement inaccuracies in the image). We introduce new Computational Geometry tools for stereo matching: the translation square arrangement, approximate translation square arrangement and approximate stereo matching tree.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR236.pdf\">TR-236.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-236 March 1994 Exact and Approximate Computational Geometry Solutions of an Unrestricted Point Set Stereo Matching Problem Frank Dehne &amp; Katia Guimaraes Abstract In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context [&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-12725","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12725","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=12725"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12725\/revisions"}],"predecessor-version":[{"id":12726,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12725\/revisions\/12726"}],"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=12725"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12725"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}