AF:Small:Geometric graph algorithms

研究者研究的算法结合了联合收割机和几何学。该提案的一个组成部分是关于不重叠的圆集，但在切点相交，就像硬币在桌面上推在一起一样。 研究人员将寻找有效的算法来构建圆包装，并使用它们来找到“Lombardi图纸”，这是一种信息可视化形式，其中图形边缘表示为圆弧。 这些图纸类似于肥皂泡，PI计划使用它们来描述肥皂泡可能具有的邻近模式。该提案的第二个组成部分涉及通过边连接附近的对象对而由几何对象形成的图;这些图在数据聚类、物理模拟中的碰撞检测和建筑设计中有许多应用。 研究人员将开发用于维护动态点的相互最近邻的有效数据结构，并研究树状非欧几里德度量空间中的最近邻，以前已知的方法不适用于此。在该奖项的第三个组成部分中，研究人员将研究用于构建制图的有效算法，地理数据的可视化，其中地理区域以程式化的形状和表示数字信息（如人口）的扭曲区域显示。 此外，他还将研究图的紧凑三维可视化，即具有轴平行边的三维多面体的顶点和边的集合，并研究轴平行多面体图的Hamilton圈的Barnette猜想。以及这些问题在信息可视化，科学计算和工程中的应用，这一提议的更广泛影响包括算法的开源实现和通过创建相关维基百科文章来公开传播知识。

The investigator studies algorithms for problems that combine graph theory with geometry.One component of the proposal concerns sets of circles that do not overlap, but meet at points of tangency like coins pushed together on the surface of a table. The investigator will seek out efficient algorithms for constructing circle packings and use them to find "Lombardi drawings", a form of information visualization in which graph edges are represented as circular arcs. These drawings resemble soap bubbles and the PI plans to use them to characterize the patterns of adjacency that soap bubbles can have.A second component of the proposal concerns the graphs formed from geometric objects by linking nearby pairs of objects by edges; these graphs have many applications in data clustering, collision detection in physical simulation, and architectural design. The investigator will develop efficient data structures for maintaining mutual nearest neighbors of dynamic points, and study nearest neighbors in tree-like non-Euclidean metric spaces for which previously known methods are inapplicable.In a third component of the award, the investigator will study efficient algorithms for constructing cartograms, visualizations of geographic data in which geographic regions are shown with stylized shapes and distorted areas that represent numeric information such as population. In addition he will study compact three-dimensional visualizations of graphs as the sets of vertices and edges of three-dimensional polyhedra with axis-parallel edges and to study Barnette's conjecture on Hamiltonian cycles for the graphs of axis-parallel polyhedra.As well as the applications of these problems in information visualization, scientific computing, and engineering, the broader impacts of this proposal include open-source implementations of algorithms and the public dissemination of knowledge via the creation of relevant Wikipedia articles.