Research on Geometric Data Processing via Parametric Optimization

点击翻译按钮获取中文摘要

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.