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
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=365472
• 关键词: 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)寻找方法，使几何概念以交互的方式在网络上呈现。