非精确点集的计算几何优化算法研究

Computational geometry has been widely used in many areas such as graphics, GIS， CAD and so on. In traditional computational geometry, the input data are assumed to be exact. However, in reality, the input data could be imprecise. For example, the data with measurement error or anonymized data in privacy preserving data mining. If we use traditional computational geometry algorithms over imprecise data directly, it could lead to wrong results. To solve above problem, we study the computational geometry optimization algorithms based on imprecise point set. In this project, we use four models for imprecise region: line segment, square, circle, discrete point set. Based on those four models, we study optimization algorithms of four fundamental computational geometry problems and analyze their complexities: (1) the largest (or smallest) perimeter (or area) convex hull; (2) the largest (or smallest) minimum spanning tree; (3) the largest closest pair of points; (4) the largest (or smallest) discrete (or continuous) Fréchet distance between trajectories. For those optimization algorithms with high complexity or NP-hard, we will give efficient approximation algorithm. The results of our algorithms can guarantee the correctness for implementing computational geometry algorithms based on imprecise point set theoretically.

计算几何算法广泛应用于计算机图形学、地理信息学（GIS）、计算机辅助设计（CAD）等领域。传统的计算几何算法适用于精确的输入数据。但是在很多应用中，输入的数据是非精确的，比如带有测量误差的数据，出于隐私保护目的而被模糊化的敏感数据。对非精确数据直接套用传统的计算几何算法会导致错误的结果。本项目针对上述问题，研究非精确点集的计算几何优化算法。基于四种点的非精确区域模型：直线段、正方形、圆形、离散点集，我们拟研究如下四个基本几何问题的最优解算法并分析其复杂度：（1）最大（或最小）周长（或面积）凸包；（2）最大（或最小）最小生成树；（3）最大最近点对；（4）最大（或最小）轨迹间的离散（或连续）Fréchet距离。对于最优解算法复杂度高或者NP-难的问题，我们将给出高效的近似解算法。研究成果为这些基本几何算法在具体应用上的实现提供了理论上的保证。

计算几何算法广泛应用于计算机图形学、地理信息学（GIS）、计算机辅助设计（CAD）等领域。传统的计算几何算法适用于精确的输入数据。但是在很多应用中，输入的数据是非精确的，比如带有测量误差的数据，出于隐私保护目的而被模糊化的敏感数据。对非精确数据直接套用传统的计算几何算法会导致错误的结果。本项目针对上述问题，研究非精确点集的计算几何优化算法。基于四种点的非精确区域模型：直线段、正方形、圆形、离散点集，我们研究了如下四个基本几何问题的最优解算法并分析其复杂度：（1）最大（或最小）周长（或面积）凸包；（2）最大（或最小）最小生成树；（3）最大最近点对；（4）最大（或最小）轨迹间的离散（或连续）Fréchet 距离。对于最优解算法复杂度高或者NP-难的问题，我们给出高效的近似解算法。研究成果为这些基本几何算法在具体应用中的实现提供了理论上的保证，并把这些研究成果应用到数据挖掘和隐私保护领域。受项目资助，在国际高水平期刊上发表SCI论文5篇，在国际高水平会议上发表EI论文19篇，