Design and analysis of algorithms for problems in computational geometry
计算几何问题的算法设计与分析
基本信息
- 批准号:RGPIN-2021-03823
- 负责人:
- 金额:$ 4.01万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2021
- 资助国家:加拿大
- 起止时间:2021-01-01 至 2022-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
I study computational problems within the framework of the design and analysis of algorithms. The solution to a problem requires designing an efficient algorithm and supporting data structures, analyzing their complexities, and providing correctness proofs. My long term research objectives are to design, analyze and implement algorithms for problems that require spatial information and (a) are fundamental, (b) have practical significance, (c) are theoretically-challenging and have the potential to raise new questions, (d) contribute to an understanding of a methodology or concept, (e) lead to the development of generic techniques and tools that apply to other problems, and (f) are of interest to students, members of our research lab, and to many of my collaborators worldwide. To have a flavour of my research, let us consider the following abstract algorithmic problem inspired by mobile networks. Consider a set of points (mobile nodes) where each point moves along a vector, and we want to maintain a fixed connection network between them. During the entire motion of points, the links (i.e., the range) connecting the points may shrink or expand, but the connections remain fixed. Two natural optimization problem arise: Minimum Moving Spanning Tree Problem: Find a fixed connection network between moving points that minimizes the total length of the links required at any point in time during the entire motion. We show that this problem is intractable and provide an efficient algorithm for computing a spanning tree whose length is within a factor of 2 of an optimal tree. Minimum Moving Bottleneck Tree Problem: Find a fixed connection network between moving points that minimizes the longest link length. We provide an efficient algorithm for computing an optimal tree. In network architectures containing mobile nodes, the existing methods that maintain a connected network update the topology dynamically. Such networks' stability becomes an essential factor since costs are associated with establishing new connections and handing over ongoing sessions. Our approach of maintaining spanning trees of good quality ensures that we have a fixed connection network even when the nodes are moving. It altogether avoids the need for reconfiguration and provides stability. In the short term, my research focus primarily will be on algorithmic and combinatorial problems arising in geometric spanning trees, matchings, and paths. We will outline several exciting and important research problems. The common theme in addressing these problems is understanding the geometric and combinatorial structure of the input spatial configuration and exploiting them to design efficient data structures and algorithms. We expect that the Undergraduate, Masters, Doctoral, and Postdoctoral students with appropriate maturity level, effort, and guidance can solve them. The research training will prepare them to tackle challenging computational problems of the 21st century.
我在算法设计和分析的框架内研究计算问题。问题的解决需要设计有效的算法和支持数据结构,分析其复杂性,并提供正确性证明。我的长期研究目标是为需要空间信息的问题设计、分析和实现算法,(A)是基本的,(B)具有实际意义,(C)在理论上具有挑战性,并有可能提出新的问题,(D)有助于理解一种方法或概念,(E)导致开发适用于其他问题的通用技术和工具,以及(F)学生、我们研究实验室的成员和我在世界各地的许多合作者感兴趣。为了让我的研究有一点味道,让我们考虑一下受移动网络启发的以下抽象算法问题。考虑一组点(移动节点),其中每个点都沿着一个向量移动,我们希望在它们之间保持一个固定的连接网络。在点的整个运动过程中,连接点的链接(即范围)可能会收缩或扩展,但连接保持不变。两个自然优化问题产生了:最小移动生成树问题:找到移动点之间的固定连接网络,使整个运动过程中任何时间点所需的链接总长度最小。我们证明了这个问题是棘手的,并为计算长度在最优树的2的因子内的生成树提供了一个有效的算法。最小移动瓶颈树问题:寻找移动点之间的固定连接网络,使最长链路长度最小化。我们提供了一种计算最优树的有效算法。在包含移动节点的网络体系结构中,现有的维护连接网络的方法动态更新拓扑。这种网络的稳定性成为一个重要因素,因为建立新连接和切换正在进行的会话的成本是相关的。我们维护高质量的生成树的方法确保了即使在节点移动时也有固定的连接网络。它完全避免了重新配置的需要,并提供了稳定性。在短期内,我的研究重点将主要集中在几何生成树、匹配和路径中出现的算法和组合问题。我们将概述几个令人兴奋和重要的研究问题。解决这些问题的共同主题是理解输入空间配置的几何和组合结构,并利用它们来设计有效的数据结构和算法。我们期待本科生、硕士生、博士后和博士后具有适当的成熟度、努力和指导来解决这些问题。研究培训将使他们为解决21世纪具有挑战性的计算问题做好准备。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Maheshwari, Anil其他文献
Switching to Directional Antennas with Constant Increase in Radius and Hop Distance
- DOI:
10.1007/s00453-012-9739-y - 发表时间:
2014-06-01 - 期刊:
- 影响因子:1.1
- 作者:
Bose, Prosenjit;Carmi, Paz;Maheshwari, Anil - 通讯作者:
Maheshwari, Anil
Space-efficient geometric divide-and-conquer algorithms
- DOI:
10.1016/j.comgeo.2006.03.006 - 发表时间:
2007-08-01 - 期刊:
- 影响因子:0.6
- 作者:
Bose, Prosenjit;Maheshwari, Anil;Vahrenhold, Jan - 通讯作者:
Vahrenhold, Jan
Workplace Well-being: An Experimental Investigation into Benefits of Consciousness-based Architecture
- DOI:
10.51327/kyon6624 - 发表时间:
2022-01-01 - 期刊:
- 影响因子:1.4
- 作者:
Maheshwari, Anil;Werd, Margaret;Lipman, Jonathan - 通讯作者:
Lipman, Jonathan
Maheshwari, Anil的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Maheshwari, Anil', 18)}}的其他基金
Design and analysis of algorithms for problems in computational geometry
计算几何问题的算法设计与分析
- 批准号:
RGPIN-2021-03823 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design and Analysis of Algorithms for Problems in Computational Geometry
计算几何问题的算法设计与分析
- 批准号:
RGPIN-2016-06229 - 财政年份:2020
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design and Analysis of Algorithms for Problems in Computational Geometry
计算几何问题的算法设计与分析
- 批准号:
RGPIN-2016-06229 - 财政年份:2019
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design and Analysis of Algorithms for Problems in Computational Geometry
计算几何问题的算法设计与分析
- 批准号:
RGPIN-2016-06229 - 财政年份:2018
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design and Analysis of Algorithms for Problems in Computational Geometry
计算几何问题的算法设计与分析
- 批准号:
RGPIN-2016-06229 - 财政年份:2017
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design and Analysis of Algorithms for Problems in Computational Geometry
计算几何问题的算法设计与分析
- 批准号:
RGPIN-2016-06229 - 财政年份:2016
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design, analysis and implementation of geometric and graph algorithms
几何和图形算法的设计、分析和实现
- 批准号:
195732-2011 - 财政年份:2015
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design, analysis and implementation of geometric and graph algorithms
几何和图形算法的设计、分析和实现
- 批准号:
195732-2011 - 财政年份:2014
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design, analysis and implementation of geometric and graph algorithms
几何和图形算法的设计、分析和实现
- 批准号:
195732-2011 - 财政年份:2013
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design, analysis and implementation of geometric and graph algorithms
几何和图形算法的设计、分析和实现
- 批准号:
195732-2011 - 财政年份:2012
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
Scalable Learning and Optimization: High-dimensional Models and Online Decision-Making Strategies for Big Data Analysis
- 批准号:
- 批准年份:2024
- 资助金额:万元
- 项目类别:合作创新研究团队
Intelligent Patent Analysis for Optimized Technology Stack Selection:Blockchain BusinessRegistry Case Demonstration
- 批准号:
- 批准年份:2024
- 资助金额:万元
- 项目类别:外国学者研究基金项目
利用全基因组关联分析和QTL-seq发掘花生白绢病抗性分子标记
- 批准号:31971981
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
基于SERS纳米标签和光子晶体的单细胞Western Blot定量分析技术研究
- 批准号:31900571
- 批准年份:2019
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
利用多个实验群体解析猪保幼带形成及其自然消褪的遗传机制
- 批准号:31972542
- 批准年份:2019
- 资助金额:57.0 万元
- 项目类别:面上项目
基于Meta-analysis的新疆棉花灌水增产模型研究
- 批准号:41601604
- 批准年份:2016
- 资助金额:22.0 万元
- 项目类别:青年科学基金项目
基于个体分析的投影式非线性非负张量分解在高维非结构化数据模式分析中的研究
- 批准号:61502059
- 批准年份:2015
- 资助金额:19.0 万元
- 项目类别:青年科学基金项目
多目标诉求下我国交通节能减排市场导向的政策组合选择研究
- 批准号:71473155
- 批准年份:2014
- 资助金额:60.0 万元
- 项目类别:面上项目
大规模微阵列数据组的meta-analysis方法研究
- 批准号:31100958
- 批准年份:2011
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
基于物质流分析的中国石油资源流动过程及碳效应研究
- 批准号:41101116
- 批准年份:2011
- 资助金额:23.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Design and Analysis of Algorithms for Structured Optimization
结构化优化算法的设计与分析
- 批准号:
2307328 - 财政年份:2023
- 资助金额:
$ 4.01万 - 项目类别:
Standard Grant
Matched Design with Sensitivity Analysis for Observational Survival Data in Cardiovascular Patient Management using EMR Data
使用 EMR 数据对心血管患者管理中的观察性生存数据进行匹配设计和敏感性分析
- 批准号:
10731172 - 财政年份:2023
- 资助金额:
$ 4.01万 - 项目类别:
Analysis of algorithms for resouce allocation: an approach from market design and discrete convex analysis
资源分配算法分析:市场设计和离散凸分析的方法
- 批准号:
22KJ0717 - 财政年份:2023
- 资助金额:
$ 4.01万 - 项目类别:
Grant-in-Aid for JSPS Fellows
CAREER: Molecular mechanisms, algorithms and software for design and analysis of genome perturbation experiments
职业:用于设计和分析基因组扰动实验的分子机制、算法和软件
- 批准号:
2238831 - 财政年份:2023
- 资助金额:
$ 4.01万 - 项目类别:
Continuing Grant
The effects of study design characteristics on dementia assessment: Recommendations for future epidemiologic studies
研究设计特征对痴呆症评估的影响:对未来流行病学研究的建议
- 批准号:
10460806 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Design and Analysis of Algorithms for High-Performance Scientific Computing
高性能科学计算算法的设计与分析
- 批准号:
RGPIN-2019-05692 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Design, analysis and Theory of Algorithms
算法设计、分析与理论
- 批准号:
RGPIN-2017-06551 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Using factorial design to examine efficacies of technology-based augmentations for improving treatment adherence and skills utilization in a self-help CBT program for binge eating.
使用析因设计来检验基于技术的增强措施在针对暴食症的自助 CBT 计划中提高治疗依从性和技能利用率的功效。
- 批准号:
10507528 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Implementing best practices in software design for Network Level Analysis
实施网络级分析软件设计的最佳实践
- 批准号:
10839638 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
A data-driven bioinformatics platform for the design and analysis of multiplexed antibody-based cytometry experiments in cancer research
数据驱动的生物信息学平台,用于设计和分析癌症研究中基于多重抗体的细胞计数实验
- 批准号:
10528837 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别: