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问题与随机矩阵有关，是统计学中一个新兴的研究课题。(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.