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

项目名称： 非精确点集的计算几何优化算法研究

项目编号： No.11271351

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 罗军

作者单位： 中国科学院深圳先进技术研究院

项目金额： 50万元

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

中文关键词： 计算几何；非精确数据；隐私保护；数据挖掘；

英文摘要： 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

英文关键词： computational geometry；imprecise data；privacy preserving；data mining；