Studies on Realistic Solutions to Theoretically Hard Problems

理论难题的现实解决方案研究

• 批准号: 10205207
• 负责人: ASANO Tetsuo
• 金额: $ 9.15万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205207/
• 关键词: Algorithm; Computational Geometry; Asymptotic analysis; データ構造; クラスタリング; 画像処理; 画像検索; 計算複雑度; 近似アルゴリズム; 印刷

In this study we have been engaged in several problems which were thought to be computationally Hard within the traditional framework of asymptotic analysis popular in the theory of algorithms. More concretely, we have studied the problem of designing optimal dot patterns for printing and that of clustering. For the former problem, we have noticed that the discrepancy theory can be applied to the problem. The discrepancy theory has been rigorously studied and is full of important theoretical results. Combining it with the notion of matching in the graph theory, we have succeeded in improving the performance of the solutions obtained. Since we also had satisfactory experimental results, we intend to submit the result to some journal. For the problem of clustering, we have applied an algorithmic approach to image query system On image database with good experimental results that exceed results by traditional Approaches. We are planning to summarize the results in a paper to be submitted to some International journal in near future.

在这项研究中，我们一直在从事的几个问题，被认为是计算困难的传统框架内流行的渐近分析理论的算法。更具体地说，我们研究了设计最佳印刷网点图案和聚类问题。对于前一个问题，我们已经注意到差异理论可以应用于该问题。差异理论已经得到了严格的研究，并充满了重要的理论成果。结合图论中匹配的概念，我们成功地提高了所获得的解决方案的性能。由于我们也有令人满意的实验结果，我们打算将结果提交给一些期刊。对于聚类问题，我们将一种算法方法应用于图像数据库上的图像查询系统，取得了较好的实验结果，优于传统方法的结果。我们计划在不久的将来将结果总结在一篇论文中提交给一些国际期刊。

项目成果

S. C. Nandy, T. Harayama, T. Asano: "Dynamically maintaining the widest k-dense corridor"Theoretical Computer Science. 255. 627-639 (2001)

S.C. Nandy、T. Harayama、T. Asano：“动态维持最宽的 k 密集走廊”理论计算机科学。

T. Asano: "Effective Use of Geometric Information for Clustering and Related Topics"IEICE Trans. on Fundamentals. (2000)

T. Asano：“有效利用几何信息进行聚类及相关主题”IEICE Trans。

今井、室田、浅野、茨木、小島: "離散構造とアルゴリズムV" 近代科学社, 250 (1998)

Imai、Murota、Asano、Ibaraki、Kojima：“离散结构和算法 V”Kindai Kagakusha，250（1998）

T. Asano, D. Z. Chen, N. Katoh, and T. Tokuyama: "Efficient Algorithms for Optimization-based Image Segmentation"11, 2. 145-166 (2001)

T. Asano、D. Z. Chen、N. Katoh 和 T. Tokuyama：“基于优化的图像分割的高效算法”11, 2. 145-166 (2001)

T.Asano: "Digital Halftoning Algorithm Based on Randon Space-Filling Curve" IEICE Trans.on Fundamentals. (1999)

T.Asano：“基于随机空间填充曲线的数字半色调算法”IEICE Trans.on 基础知识。