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: "Algorithms for Projecting Points to Give the Most Uniform Distribution with Applications to Hashing" Algorithmica. 9. 572-590 (1993)

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