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

项目编号: 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;

成为VIP会员查看完整内容
0

相关内容

【CVPR2022】多机器人协同主动建图算法
专知会员服务
45+阅读 · 2022年4月3日
NeurIPS 2021 | 用简单的梯度下降算法逃离鞍点
专知会员服务
23+阅读 · 2021年12月6日
【博士论文】吉布斯分布的局部、动态与快速采样算法
专知会员服务
28+阅读 · 2021年11月26日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
专知会员服务
21+阅读 · 2021年7月31日
专知会员服务
21+阅读 · 2021年6月26日
专知会员服务
17+阅读 · 2021年5月16日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
74+阅读 · 2020年12月6日
交替方向乘子法(ADMM)算法原理详解
PaperWeekly
3+阅读 · 2022年1月21日
基于深度学习的单视图三维重建算法学习路线
极市平台
6+阅读 · 2022年1月12日
用狄拉克函数来构造非光滑函数的光滑近似
PaperWeekly
0+阅读 · 2021年10月23日
常见的距离算法和相似度计算方法
极市平台
18+阅读 · 2020年7月31日
最全综述:基于深度学习的三维重建算法
极市平台
12+阅读 · 2020年3月17日
求解稀疏优化问题——半光滑牛顿方法
极市平台
39+阅读 · 2019年11月30日
机器学习计算距离和相似度的方法
极市平台
10+阅读 · 2019年9月20日
最全综述 | 图像分割算法
计算机视觉life
13+阅读 · 2019年6月20日
RCNN算法分析
统计学习与视觉计算组
10+阅读 · 2018年1月12日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Sensitivity of sparse codes to image distortions
Arxiv
0+阅读 · 2022年4月15日
小贴士
相关主题
相关VIP内容
【CVPR2022】多机器人协同主动建图算法
专知会员服务
45+阅读 · 2022年4月3日
NeurIPS 2021 | 用简单的梯度下降算法逃离鞍点
专知会员服务
23+阅读 · 2021年12月6日
【博士论文】吉布斯分布的局部、动态与快速采样算法
专知会员服务
28+阅读 · 2021年11月26日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
专知会员服务
21+阅读 · 2021年7月31日
专知会员服务
21+阅读 · 2021年6月26日
专知会员服务
17+阅读 · 2021年5月16日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
74+阅读 · 2020年12月6日
相关资讯
交替方向乘子法(ADMM)算法原理详解
PaperWeekly
3+阅读 · 2022年1月21日
基于深度学习的单视图三维重建算法学习路线
极市平台
6+阅读 · 2022年1月12日
用狄拉克函数来构造非光滑函数的光滑近似
PaperWeekly
0+阅读 · 2021年10月23日
常见的距离算法和相似度计算方法
极市平台
18+阅读 · 2020年7月31日
最全综述:基于深度学习的三维重建算法
极市平台
12+阅读 · 2020年3月17日
求解稀疏优化问题——半光滑牛顿方法
极市平台
39+阅读 · 2019年11月30日
机器学习计算距离和相似度的方法
极市平台
10+阅读 · 2019年9月20日
最全综述 | 图像分割算法
计算机视觉life
13+阅读 · 2019年6月20日
RCNN算法分析
统计学习与视觉计算组
10+阅读 · 2018年1月12日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
微信扫码咨询专知VIP会员