Research on data rounding based on discrete systems.

该研究基于图和超图的离散数学概念，追求模拟数据相对于质量度量的高质量数字化(舍入)。这种研究在数字半色调以及其他许多数字化应用中具有重要的应用。特别是，我们考虑与超图相关的差异距离，并研究与输入最多具有差异距离的全局环境空间。最重要的输出是在全局环境空间的组合结构的数学研究的范畴。我们猜想，对于由连通图的最短路度量生成的超图，全局环绕空间确实是单形的。我们对路、圈、网状图、串并图、均匀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.