Fundamentals and Applications of Connect-the-Dots Methods

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

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.