A STUDY ON GEOMETRIC TRANSFORMATION PRESERVING GRID POINTS AND ITS APPLICATIONS

保留网格点的几何变换及其应用研究

• 批准号: 04650331
• 负责人: ASANO Tetsuo
• 金额: $ 1.28万
• 依托单位: OSAKA ELECTRO-COMMUNICATION UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1992
• 资助国家: 日本
• 起止时间: 1992 至 1993
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-04650331/
• 关键词: Computational Geometry; Algorithm; Computational Complexity; Computer Graphics; Integer Programming; アルゴリズム設計; グリッド幾何; 幾何学的変換; 整数計画問題; ユークリッドの互除法

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.The 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.

在这项研究中，我们开发了有效的算法，用于在最佳时间内报告给定凸多边形内的所有网格点，并将该算法应用于二维整数规划。我们还用C语言实现了这些算法并评估了它们的实际效率。结果非常令人满意。我们进一步将类似的想法扩展到其他一些问题：多个亮度级别的图片的数字半色调以及检测数字图片中指定曲线的所有可能的数字分量。

项目成果

T.Asano,T.Tokuyama: "Circuit Partitioning Algorithms Based on Geometry Model" “Algorithmic Aspects of VLSI Layout",Ed.by D.T.Lee and M.Sarrafzadeh. 199-212 (1993)

T.Asano、T.Tokuyama：“基于几何模型的电路划分算法”“VLSI 布局的算法方面”，D.T.Lee 和 M.Sarrafzadeh 编，199-212 (1993)

T.Asano T.Tokuyama: "Algorithms for Projecting Points to Give the Most Uniform Distribution with Applications to Hashing" Algorithmica. 9. 572-590 (1993)

T.Asano T.Tokuyama：“投影点给出最均匀分布的算法及其应用于散列”算法。

""Algorithms for Projecting Points to Give the Most Unifrom Distribution with Applications to Hashing"" Algorithmica. vol.9. 572-590 (1993)

“用于投影点以给出最均匀分布的算法及其应用于散列”Algorithmica。

T.Asano and T.Tokuyama: ""Partial Construction of an Arrangement of Lines and its Application to Optimal Partitioning of Bichromatic Point Set"" Trans.of IEICE of Japan. (to appear).

T.Asano 和 T.Tokuyama：“线排列的部分构造及其在双色点集最优划分中的应用”，日本 IEICE 翻译。

T.Asano,T.Tokuyama: "Partial Construction of an Arrangement of Lines and its Application to Optimal Partitioning of Bichromatic Point Set" 電子情報通信学会論文誌(E). (採録決定).

T.Asano，T.Tokuyama：“线排列的部分构造及其在双色点集最优划分中的应用”IEICE Transactions（E）（已接受）。