Fundamentals and Applications of Connect-the-Dots Methods

点连线方法的基础知识和应用

• 批准号: 0700152
• 负责人: Xiaoming Huo
• 金额: $ 24.87万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0700152&HistoricalAwards=false
• 关键词: Fundamentals; Applications; Connect; Dots; Methods

A fundamental class of problems is collectively named Connect-the-Dots (CTD). CTD problems have the following common components: (1) a random point set, (2) a prescribed functional class, and (3) a goal of finding a maximum subset of the point set that a function from the functional class can pass through. Example problems include maximizing the number of points on a monotone or convex function, or on a surface of bounded curvature. The principal project goal is to develop the computational and probabilistic underpinnings for a new family of statistical tests and solution procedures for CTD. The PIs propose to implement these as tools in MATLAB, making them freely available on the internet. There are two related aspects of the CTD problems: computational and statistical. The computational aspect is to design efficient numerical algorithms to search for the maximum subset and its associated function. This involves finding extensions of low computational complexity algorithms to high dimensions, searching for efficient algorithms for several functional classes, and investigating possibilities of nearly-exact algorithms. Preliminary work indicates that dynamic programming plays a key role, often in a highly non-trivial way. The statistical aspect concerns properties of the maximum subset, such as (1) the limit distribution of the size of the maximum subset of a random point cloud, (2) the `typical' shape of the maximum subset or associated function, and (3) convergence properties and rates. The computational results aid in the statistical work by permitting empirical investigation.If successful, the proposed work may have impact in many scientific fields: (1) CTD problems are related to the Longest Increasing Subsequence and Random Traveling Salesman problems, which have been studied in probability; (2) CTD problems have a link with Geometric Discrepancy Theory -- a new branch in pure mathematics; (3) CTD problems are related to Filament Detection in image processing, and more generally are a class of pattern recognition problems; (4) CTD problems have applications in Vision, which has grown into an interdisciplinary field between computer science and psychology; (5) CTD can potentially be utilized to analyze and develop Human Interactive Proofs, which are increasingly popular in Internet security applications. (6) CTD problems are related to random matrices (RM), which have been an emerging research topic in statistics. (7) CTD problems have surprising links to applications such as disk scheduling and airplane boarding. (8) CTD problems have connections with problems in statistical physics.

一类基本的问题统称为连接点（CTD）。CTD问题具有以下常见组件：（1）随机点集，（2）规定的函数类，以及（3）找到函数类中的函数可以通过的点集的最大子集的目标。示例问题包括最大化单调或凸函数或有界曲率表面上的点的数量。主要项目目标是为CTD的一系列新的统计测试和解决方案程序开发计算和概率基础。PI建议在MATLAB中实现这些工具，使它们在互联网上免费提供。CTD问题有两个相关的方面：计算和统计。计算方面是设计有效的数值算法来搜索最大子集及其相关函数。这涉及到寻找低计算复杂度的算法扩展到高维，寻找几个功能类的有效算法，并调查近精确算法的可能性。初步的工作表明，动态规划起着关键作用，往往是在一个高度非平凡的方式。统计方面涉及最大子集的性质，例如（1）随机点云的最大子集的大小的极限分布，（2）最大子集或相关函数的“典型”形状，以及（3）收敛性质和速率。计算结果有助于统计工作的实证研究，如果成功的话，所提出的工作可能会在许多科学领域产生影响：（1）CTD问题与最长递增子序列和随机旅行商问题有关，这两个问题已经在概率中得到了研究：（2）CTD问题与几何离散理论--纯数学中的一个新的分支有关;（3）CTD问题与图像处理中的细丝检测有关，更一般地说是一类模式识别问题：（4）CTD问题在视觉中有应用，它已经发展成为计算机科学和心理学之间的交叉领域;（5）CTD可以用于分析和开发在互联网安全应用中日益流行的人机交互证明。(6)CTD问题与随机矩阵（RM）有关，它已成为统计学中的一个新兴研究课题。(7)CTD问题与磁盘调度和登机等应用程序有着惊人的联系。(8)CTD问题与统计物理学中的问题有联系。