Mathematical Foundations of Algorithms for Data Visualization

点击翻译按钮获取中文摘要

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.