Research on data rounding based on discrete systems.

本研究追求高品质数字化的产生基于图和超图的离散数学概念，在质量测量方面对模拟数据进行四舍五入。这样的研究对于作为图像处理中的主要主题的数字半色调以及其他许多数字化应用具有重要的应用。特别地，我们考虑了超图的差异距离，并研究了与输入的差异距离至多为1的全局图空间。最重要的输出在数学研究的范畴的组合结构的空间的整体。本文提出了一个猜想，即对于由连通图的最短路度量生成的超图，其全局连通空间确实是一个单纯形。我们已经对路、圈、网孔、串并行图、一致k-树等几类图证明了这一猜想，并设计了计算这类超图全局连通图的多项式时间算法。此外，我们还研究了由子式定义的图上的几个性质/算法，因为我们的猜想似乎可以在这样的图上用图-子式理论得到证明。在此期间，我们发表了10篇国际期刊论文和几篇学术论文，并研究了在数字半色调应用中重要的矩阵子矩阵所对应的超图的偏差的上/下界。我们已经做了一些数字半调实例的实验，使用我们的方法。

The research pursue the generation of high-quality digitization (rounding) of analogue data with respect to quality measures based on discrete mathematical concept of graphs and hypergraphs.Such research has important applications to digital halftoning that is a major topic in image processing, as well as other many digitization applications.In particular, we consider discrepancy distances associated with hypergraphs and investigate on the space of global roundings that have the discrepancy distance at most one from the input.The most important outputs are given in the category of mathematical investigation of the combinatorial structure of the space of global roundings. We have given a conjecture that for the hypergraph generated from the shortest path metric of a connected graph, the space of global roundings is indeed a simplex. We have affirmatively proven this conjecture for several classes of graphs such as paths, cycles, mesh, series-parallel graphs, uniform k-trees, and so on.As byproducts, we have designed efficient polynomial-time algorithm for enumerating global roundings for such hypergraphs. Also we have proven a similar property for several range spaces considered in computational geometry.Moreover, we have investigated several properties/algorithms on graphs defined by minors, since it seems that our conjecture will be proven on such graphs by using graph-minor theory. We have published 10 international journal papers and several cnference papers during the period.We have also investigated lower/upper bounds of discrepancies of hypergraphs corresponding to submatrices of a matrix that are important in application to digital halftoning. We have done some experiments on digital halftoning instances by using our methodology.