Research on Geometric Data Processing via Parametric Optimization

这学期我们发表了十七篇论文。建立了参数优化框架，为多维参数搜索提供了一种新的范式。我们还研究了超平面排列的组合学，这是理论的基础：作为新的结果，我们给出了三维排列层次的复杂性分析，并给出了新的高效算法来搜索排列的k级峰。此外，我们还研究了参数优化在量子计算中的应用。作为参数优化的应用，我们研究了数据挖掘、数字半色调和图像分割。在理论研究的基础上，对数据挖掘的应用进行了系统的构建。这些研究成果发表在ACM STOC、ACM SCG、ACM-SIAM SODA、ISAAC、SIAM Journal on Computing、ACM Transaction和Discrete & Computational Geometry等授权期刊和会议上。我们还在与这个项目有关的国际/国家会议和讲习班上作了几次演讲。

We have published seventeen refereed papers during the term. We established the framework of parametric optimization, and give a new paradigm for the multi-dimensional parametric searching. We also work on the combinatorics of hyperplane arrangement, which is foundation of the theory : As new results, we give complexity analysis of levels of three dimensional arrangements, and also give new efficient algorithms for searching peaks of k-level of an arrangement. Moreover, we have investigated use of parametric optimization in quantum computation. As applications of parametric optimization, we have investigated data mining, digital halftoning, and image segmentation. Besides theoretical results, we have done system construction in data mining application. These research results were published in authorized journals and conferences such as ACM STOC,ACM SCG,ACM-SIAM SODA,ISAAC,SIAM Journal on Computing, ACM Transaction, and Discrete & Computational Geometry.We have also given several talks in International/National conferences and workshops on the topics related to this project.