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.