AF: Small: Subdivision Methods: Correctness and Complexity

AF:小:细分方法:正确性和复杂性

基本信息

  • 批准号:
    1527193
  • 负责人:
  • 金额:
    $ 24.64万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2015
  • 资助国家:
    美国
  • 起止时间:
    2015-09-01 至 2019-08-31
  • 项目状态:
    已结题

项目摘要

Subdivision-based algorithms can solve problems from a wide variety of applications in mathematics, computer science, and the sciences. For example, these types of algorithms are used in computer graphics, mathematical biology, computational geometry, mathematical modeling, robotics, machine learning, and mathematical computation. Subdivision-based algorithms are popular because they are relatively easy to describe and implement on a computer, and they are often efficient in practice. The work in this project is to quantify and improve the effectiveness of these types of algorithms. By studying the efficiency and providing algorithms to approximate solutions to problems which are typically considered intractable, the results of this project provide techniques which can be applied to practical problems throughout the sciences.Subdivision-based algorithms recursively and adaptively subdivide a given domain into smaller regions until, in each smaller region, the behavior of a problem-specific feature can be determined. Subdivision-based algorithms are frequently used because they are parallelizable, recursive, and adaptive. More precisely, they use weak local tests and perform more subdivisions only near difficult features. These features that make subdivision-based algorithms practical, however, also make them challenging to study. For example, local tests make global topological correctness difficult and adaptive (non-uniform) subdivisions make the number of subdivisions difficult to bound. This project addresses both of the important questions of complexity and correctness for subdivision-based algorithms in the following two ways: (1) Using continuous amortization as a uniform method to compute the complexity of subdivision-based algorithms. (2) Developing topologically certified subdivision-based algorithms for geometric applications on algebraic varieties. This project extends the technique of continuous amortization to many different types of algorithms including iterative and two-dimensional subdivisions; additionally, the project develops subdivision-based algorithms to approximate previously intractable problems such as the medial axis and intersections of surfaces.
基于细分的算法可以解决数学、计算机科学和科学中广泛应用的问题。例如,这些类型的算法用于计算机图形学、数学生物学、计算几何、数学建模、机器人学、机器学习和数学计算。基于细分的算法很受欢迎,因为它们相对容易在计算机上描述和实现,而且在实践中通常是有效的。本项目的工作是量化和改进这些类型的算法的有效性。通过研究效率和提供算法来近似解决通常被认为是棘手的问题,该项目的结果提供了可以应用于整个科学中的实际问题的技术。基于细分的算法递归地自适应地将给定域细分为更小的区域,直到在每个更小的区域中可以确定特定于问题的特征的行为。基于细分的算法经常被使用,因为它们是可并行化、递归和自适应的。更准确地说,它们使用弱局部测试,并且只在困难的特征附近执行更多细分。然而,这些使基于细分的算法变得实用的特征也使它们的研究具有挑战性。例如,局部测试使全局拓扑正确性变得困难,而自适应(非均匀)细分使细分的数量难以限制。该项目从以下两个方面解决了基于细分的算法的复杂性和正确性问题:(1)使用连续摊销作为计算基于细分的算法的复杂度的统一方法。(2)为代数簇上的几何应用开发了基于拓扑证明的细分算法。该项目将连续摊销技术扩展到许多不同类型的算法,包括迭代和二维细分;此外,该项目还开发了基于细分的算法来近似以前难以解决的问题,如曲面的中轴和相交。

项目成果

期刊论文数量(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 }}

Michael Burr其他文献

Subalgebra and Khovanskii bases equivalence
子代数和 Khovanskii 基等价
  • DOI:
    10.48550/arxiv.2402.06057
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Colin Alstad;Michael Burr;Oliver Clarke;Timothy Duff
  • 通讯作者:
    Timothy Duff
Computability in Dynamical Systems
动力系统中的可计算性
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Michael Burr;Christian Wolf
  • 通讯作者:
    Christian Wolf
Childhood epidemiology of anaphylaxis and epinephrine prescriptions in Wales: 1994–1999
  • DOI:
    10.1016/s0091-6749(02)81323-9
  • 发表时间:
    2002-01-01
  • 期刊:
  • 影响因子:
  • 作者:
    Satyapal Rangaraj;David Tuthill;Michael Burr;Mazin Alfaham
  • 通讯作者:
    Mazin Alfaham

Michael Burr的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Michael Burr', 18)}}的其他基金

Certification Algorithms for Polynomial System Solving
多项式系统求解的认证算法
  • 批准号:
    1913119
  • 财政年份:
    2019
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
  • 批准号:
    10099896
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Collaborative R&D
"Small performances": investigating the typographic punches of John Baskerville (1707-75) through heritage science and practice-based research
“小型表演”:通过遗产科学和基于实践的研究调查约翰·巴斯克维尔(1707-75)的印刷拳头
  • 批准号:
    AH/X011747/1
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Research Grant
Fragment to small molecule hit discovery targeting Mycobacterium tuberculosis FtsZ
针对结核分枝杆菌 FtsZ 的小分子片段发现
  • 批准号:
    MR/Z503757/1
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Research Grant
Bacteriophage control of host cell DNA transactions by small ORF proteins
噬菌体通过小 ORF 蛋白控制宿主细胞 DNA 交易
  • 批准号:
    BB/Y004426/1
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Research Grant
Windows for the Small-Sized Telescope (SST) Cameras of the Cherenkov Telescope Array (CTA)
切伦科夫望远镜阵列 (CTA) 小型望远镜 (SST) 相机的窗口
  • 批准号:
    ST/Z000017/1
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Research Grant
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Standard Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
  • 批准号:
    2317251
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Standard Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 24.64万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了