Design, analysis and implementation of discrete algorithms for graph and computational geometry problems

拟议的研究是在算法的设计、分析和实现领域，这是理论计算机科学的一个子领域。我们专注于计算几何和图论中出现的一些问题。这些问题包括(A)几何路径问题-如何在各种约束(最短、单调下降、最小化链接数量、多准则)下在几何区域(表面、平面区域、在障碍物中的三维空间)中找到两点之间的路径(B)图形分隔符-计算平面(或类平面)图形的顶点/边分隔符(C)可见性优化问题(在放射治疗中的应用)-需要看到多面体(肿瘤)，避免/最小化一组多面体(健康器官)，(D)开发用于解决图形和几何问题的通用外部存储器算法技术(E)开发用于解决各种计算模型中的问题的算法技术-外部存储器模型、并行计算模型、定价信息模型、流和具有非常有限额外空间的模型(F)基于离散化的近似算法-我们提出了基于离散化的方案来解决几何路径问题。大多数情况下，在实际环境中出现的空间问题通过使用某种形式的离散化的启发式方法来解决。我们建议根据我们的结果研究这些问题，并希望根据其精度和复杂性为近似算法提供可证明的界。(G)使用几何参数分析几何算法的复杂性-传统上，几何算法的复杂性是关于输入参数(线段数、顶点、面等)来分析的，但在实践中，运行时通常对几何参数非常敏感-角度、距离、胖度。因此，算法的设计需要考虑这些参数；这是我们在最短路径方面的工作中提出的。我们建议扩展几何算法的设计和分析，以包括几何参数(H)寻找方法使几何概念可以在网络上以交互方式呈现。

The proposed research is in the field of design, analysis and implementation of algorithms, a subfield within theoretical computer science. We focus on  problems arising in computational geometry and graph theory. The problems include (a) Geometric path problems - how to find a path between two points in a geometric domain (surface, planar region, three dimensional space amidst obstacles) under various constraints (shortest, monotone descending, minimizing the number of links, multiple criteria) (b) Graph separators - computing vertex/edge separators of planar (or planar like) graphs (c) Visibility optimization problems (with applications in radiation therapy) - need to see a polyhedra (tumor), avoiding/minimizing a set a polyhedra (healthy organs), from a minimum set of locations (possible position of laser guns placed outside the body) (d) Developing generic external memory algorithmic techniques for solving graph and geometric problems (e) Developing algorithmic technqiues for solving problems in variety of computational models - external memory model, parallel computing model, priced information model, streaming and models with very limited extra space (f) Approximation algorithms based on discretization - we have proposed discretization based schemes to solve geometric path problems. Most often spatial problems arising in practical settings are solved by heuristics using some form of discretization. We propose to study these problems, in light of our results, and hope to provide approximation algorithms with provable bounds in terms of their accuracy and complexity (g) Analyzing complexity of geometric algorithms using geometric parameters - traditionally the complexity of geometric algorithms is analyzed with respect to input parameters (number of segments, vertices, faces, etc.), but often in practice, the run-time is very sensitive to geometric parameters - angle, distance, fatness. So the design of the algorithm needs to take these parameters into account; this came up in our work on shortest paths. We propose to expand the design and analysis of geometric algorithms to include geometric parameters (h) Finding ways to make geometrical concepts presentable on the web in an interactive manner.