{"created":"2023-07-27T06:58:05.085205+00:00","id":55710,"links":{},"metadata":{"_buckets":{"deposit":"0cd2db9a-abdc-479e-8bfc-c7dc5df7aaa9"},"_deposit":{"created_by":18,"id":"55710","owners":[18],"pid":{"revision_id":0,"type":"depid","value":"55710"},"status":"published"},"_oai":{"id":"oai:kanazawa-u.repo.nii.ac.jp:00055710","sets":["2812:2813:2840"]},"author_link":["97040"],"item_9_biblio_info_8":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1995-03-26","bibliographicIssueDateType":"Issued"},"bibliographicPageStart":"2p.","bibliographicVolumeNumber":"1992 – 1993","bibliographic_titles":[{"bibliographic_title":"平成5(1993)年度 科学研究費補助金 一般研究(C) 研究成果報告書概要"},{"bibliographic_title":"1993 Fiscal Year Final Research Report Summary","bibliographic_titleLang":"en"}]}]},"item_9_creator_33":{"attribute_name":"著者別表示","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{}],"nameIdentifiers":[{},{}]}]},"item_9_description_21":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"コンピュータの画面に代表されるようなグリッド平面上では、直線はグリッド点の系列として、塗りつぶし図形はグリッド点の集合として表現される。直線や2次曲線をいかにグリッド点の系列として表現するかについては多くの研究がなされているが、問題の計算複雑度に関する理論的な解析はあまりなされていないのが現状である。本研究の目的は、グリッド平面上に任意の閉図形が与えられたとき、その内部に含まれるグリッド点を効率よく列挙するアルゴリズムを開発することであった。\n最初に、グリッド点を保存する幾何学的変換に基づいて効率のよいアルゴリズムを考案し、計算機実験を行なってその有効性を確認した。基本的なアイディアは、グリッド点をグリッド点に写す変換を用いて素朴な方法で効率よくグリッド点を列挙できる部分(密な部分)とグリッド点が疎な部分に分割するという操作を後者の部分が十分小さくなるまで繰り返すというものである。この繰り返し回数は与えられた図形のディメンジョンの対数をとったものになるから、効率のよい実行が可能になる訳である。また、この変換法をうまく用いて2変数の整数計画問題に対する効率のよいアルゴリズムも与えた。これについても計算機実験を行なった。計算機実験に用いたプログラムのリストの一部(主要部分のみ)は報告書に含めておいた。\nさらに他方面への応用例として、画像のディジタル・ハーフトーニングの問題さらにはディジタル画像から直線や円のような基本図形の成分を検出する問題についても考察し、効率のよいアルゴリズムを得ることに成功した。これらの問題に対して従来から様々な方法が提案されているが、問題の計算複雑度が厳密に解析されたことがなかった。その意味で本研究は重要な一石を投じたものと思われる。","subitem_description_type":"Abstract"},{"subitem_description":"In this research we have developed efficient algorithms for reporting all the grid points within a given convex polygon in optimal time and also applied the algorithm for two-dimensional integer programming. We have also implemented those algorithms using C language and evaluated their practical efficiencies.\nThe results were quite satisfactory. We further extended the similar idea to some other problems : digital halftoning of pictures of multiple brightness levels and that of detecting all possible digital components of a specified curve in a digital picture.","subitem_description_type":"Abstract"}]},"item_9_description_22":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"研究課題/領域番号:04650331, 研究期間(年度):1992 - 1993","subitem_description_type":"Other"},{"subitem_description":"出典：「グリッド点を保存する幾何学的変換とその応用に関する研究」研究成果報告書　課題番号04650331\n（KAKEN：科学研究費助成事業データベース（国立情報学研究所）） \n（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-04650331/046503311993kenkyu_seika_hokoku_gaiyo/）を加工して作成","subitem_description_type":"Other"}]},"item_9_description_5":{"attribute_name":"提供者所属","attribute_value_mlt":[{"subitem_description":"金沢大学 / 大阪電気通信大学","subitem_description_type":"Other"}]},"item_9_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.24517/00061985","subitem_identifier_reg_type":"JaLC"}]},"item_9_relation_28":{"attribute_name":"関連URI","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"https://kaken.nii.ac.jp/search/?qm=90113133"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://kaken.nii.ac.jp/search/?qm=90113133","subitem_relation_type_select":"URI"}},{"subitem_relation_name":[{"subitem_relation_name_text":"https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-04650331/"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-04650331/","subitem_relation_type_select":"URI"}},{"subitem_relation_name":[{"subitem_relation_name_text":"https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-04650331/046503311993kenkyu_seika_hokoku_gaiyo/"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-04650331/046503311993kenkyu_seika_hokoku_gaiyo/","subitem_relation_type_select":"URI"}}]},"item_9_version_type_25":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2021-12-03"}],"displaytype":"detail","filename":"TE-PR-ASANO-T-kaken 1995-2p.pdf","filesize":[{"value":"92.7 kB"}],"format":"application/pdf","licensetype":"license_11","mimetype":"application/pdf","url":{"label":"TE-PR-ASANO-T-kaken 1995-2p.pdf","url":"https://kanazawa-u.repo.nii.ac.jp/record/55710/files/TE-PR-ASANO-T-kaken 1995-2p.pdf"},"version_id":"6f01f219-9df9-4958-9a23-2ae5b2bdd479"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"research report","resourceuri":"http://purl.org/coar/resource_type/c_18ws"}]},"item_title":"グリッド点を保存する幾何学的変換とその応用に関する研究","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"グリッド点を保存する幾何学的変換とその応用に関する研究"},{"subitem_title":"A study on geometric transformation preserving grid points and its applications","subitem_title_language":"en"}]},"item_type_id":"9","owner":"18","path":["2840"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-12-03"},"publish_date":"2021-12-03","publish_status":"0","recid":"55710","relation_version_is_last":true,"title":["グリッド点を保存する幾何学的変換とその応用に関する研究"],"weko_creator_id":"18","weko_shared_id":-1},"updated":"2023-07-27T14:05:55.306141+00:00"}