Mathematical Foundations of Algorithms for Data Visualization

最近的工作表明，一种基本的、抽象的算法是数据可视化技术的广泛集合的基础。这种替代算法已经部分刻画了特征，但尚未实现。最初的特征是在多面体的颜色中出现的情况的数量，这些多面体是平铺一个区域的。每种颜色对应于数据的离散状态，例如高于或低于阈值或者是集合中的特定元素(例如，骨骼、肌肉或病变)。通用可视化算法的广泛适用性提供了很大的希望。本项目将通过应用Polya理论(经De Bruijn改进)的群论结果，并通过应用拓扑学、代数几何和组合学的技术来确定几何替换的类别，从而进一步开发替换算法。替代算法的专门化可以使用几何替换的类别。拟议活动的智力价值这一交叉学科项目是第一次共同努力发展数据可视化技术的数学基础。它结合了计算机科学家(研究图形学和可视化)和纯数学家(研究拓扑学和几何学)的专业知识。该项目将建立数据可视化学科的第一个理论基础；这一成果将加速新的可视化技术的进一步发展。这一新理论的分类结果将表明在各种各样的数据集中需要探索许多新的特征检测方法。广泛的影响大多数科学、工程和医学领域的研究人员必须越来越多地分析从实验数据采集和数值模拟中产生的二维、三维甚至更高维的数据集。例如，海洋/大气数据中的温度、湿度、盐度和速度；天体物理学和生物化学中的密度、速度、电矢量场和磁场矢量场；以及医学中的CT和MRI数据集。将当前的可视化技术扩展到处理矢量值、多维、多尺度和张量值的数据集，否则将需要个人努力来设计适当的算法(基于偶尔的个人洞察，随后费力地列举出现的可能情况)，相反，将使枚举任务变得自动化。这将使科学家、工程师和临床医生更快地享受到适合他们需求的定制可视化工具的开发，从而使他们受益。

AbtractRecent work has shown that a fundamental, abstract algorithm underlies a broad collection of data-visualization techniques. This substitope algorithm has been partially characterized but not yet implemented. The initial characterization was of the number of cases that arise in colorings of polytopes that tile a domain. Each color corresponds to a discrete state of the data, such as being above or below a threshhold or being a particular element of a set (e.g., bone, muscle, or lesion). The broad applicability of a universal visualization algorithm offers a great deal of promise. This project will further develop the substitope algorithm by applying group-theoretic results from Polya theory (with improvements by de Bruijn), and by applying techniques from topology, algebraic geometry, and combinatorics to determine the classes of geometric substitutions can be employed by specializations of the substitope algorithm.Intellectual Merit of the Proposed ActivityThis inter-disciplinary project is the first concerted effort to develop the mathematical underpinnings of data-visualization techniques. It combines the expertise of a computer scientist (whose research is in graphics and visualization) with that of a pure mathematician (whose research is in topology and geometry).The project will establish the first theoretical underpinning of the discipline of data visualization; this accomplishment will accelerate further development of new visualization techniques. The taxonomy that results from this new theory will indicate many new avenues to be explored for feature detection in a wide variety of datasets.Broader ImpactsResearchers in most fields of science, engineering, and medicine must increasingly analyze two-dimensional, three-dimensional, and even higher-dimensional datasets that arise from experimental data acquisition and from numerical simulation. Examples include temperature, humidity, salinity, and velocity in ocean/atmospheric data; density, velocity, electric and magnetic vector fields in astrophysics and in biochemistry; and CT and MRI datasets in medicine. Extending current visualization techniques to handle vector-valued, multi-dimensional, multi-scale, and tensor-valued datasets that would otherwise require individual efforts to devise the appropriate algorithms (based on the occasional individual insight followed by laborious enumeration of possible cases that arise) will instead have the enumeration task become automated. This will benefit scientists, engineers, and clinicians by allowing them to enjoy the development of custom visualization tools suited to their requirements much more rapidly.