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

图和计算几何问题的离散算法的设计、分析和实现

• 批准号: 195732-2006
• 负责人: Maheshwari, Anil
• 金额: $ 2.04万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2006
• 资助国家: 加拿大
• 起止时间: 2006-01-01 至 2007-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=338389
• 关键词: Design; analysis; implementation; discrete; algorithms

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.

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