AF: Small: Topological Approximation Techniques in Computational Geometry
AF:小:计算几何中的拓扑近似技术
基本信息
- 批准号:1718994
- 负责人:
- 金额:$ 30.25万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2017
- 资助国家:美国
- 起止时间:2017-09-15 至 2021-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
In mathematics, several theorems in discrete geometry theorems are established by elegant proofs that a solution exists, without saying how to find one. For example, the memorably named Ham Sandwich theorem says (in three dimensions) that if you have ham, bread, and cheese, you can cut all three in half with one straight cut (even if you left the cheese in the refrigerator.) These theorems can actually be important for algorithms -- one would like to compute a hyperplane in d-dimensions that splits d-data sets evenly to divide the work. This project explores special cases of these problems that can produce algorithms that construct exact or approximate solutions, which are important for data analysis. Because the challenging problems can often be stated very simply, in terms of colored points, this research will involve undergraduates, graduate students, and even a summer course for high school students.This proposal deals with finding more geometric and effective proofs (leading to efficient algorithms) for some of the fundamental theorems of convex and discrete geometry -- such as colored versions of Caratheodory and Tverberg's theorems, ham sandwich and other partitioning results. The most elegant proofs of such theorems often involve topological methods -- using some fixed point theorem, Sperner's lemma, Borsuk-Ulam or more general characteristic class arguments. By giving proofs that do not depend on topology, this project can create faster algorithms for partitioning.
在数学中,离散几何定理中的几个定理是通过优雅的证明来建立的,证明了一个解的存在,而没有说明如何找到一个解。 例如,令人难忘的火腿三明治定理(在三维空间中)说,如果你有火腿,面包和奶酪,你可以用一个直切将三者切成两半(即使你把奶酪留在冰箱里)。 这些定理实际上对算法很重要--人们想计算一个d维的超平面,它平均地分割d维数据集来分配工作。 该项目探讨了这些问题的特殊情况,这些问题可以产生构造精确或近似解的算法,这对数据分析很重要。由于具有挑战性的问题往往可以非常简单地陈述,就色点而言,本研究将涉及本科生,研究生,甚至是高中生的暑期课程。本提案涉及寻找更多的几何和有效的证明(导致有效的算法)的一些基本定理的凸和离散几何-如彩色版本的Caratheodory和Tverberg的定理,火腿三明治和其他分割结果。这些定理的最优雅的证明往往涉及拓扑方法-使用一些不动点定理,Sperner引理,Borsuk-Ulam或更一般的特征类参数。 通过给出不依赖于拓扑的证明,该项目可以创建更快的分区算法。
项目成果
期刊论文数量(16)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Computing melodic templates in oral music traditions
计算口头音乐传统中的旋律模板
- DOI:10.1016/j.amc.2018.09.071
- 发表时间:2019
- 期刊:
- 影响因子:4
- 作者:Bereg, Sergey;Díaz-Báñez, José-Miguel;Kroher, Nadine;Ventura, Inmaculada
- 通讯作者:Ventura, Inmaculada
Computing the k-resilience of a synchronized multi-robot system
计算同步多机器人系统的 k-弹性
- DOI:10.1007/s10878-018-0297-3
- 发表时间:2018
- 期刊:
- 影响因子:1
- 作者:Bereg, Sergey;Caraballo, Luis-Evaristo;Díaz-Báñez, José-Miguel;Lopez, Mario A.
- 通讯作者:Lopez, Mario A.
New lower bounds for Tverberg partitions with tolerance in the plane
具有平面容差的 Tverberg 分区的新下限
- DOI:10.1016/j.dam.2020.02.007
- 发表时间:2020
- 期刊:
- 影响因子:1.1
- 作者:Bereg, Sergey;Haghpanah, Mohammadreza
- 通讯作者:Haghpanah, Mohammadreza
On some matching problems under the color-spanning model
- DOI:10.1016/j.tcs.2018.08.008
- 发表时间:2019-09
- 期刊:
- 影响因子:0
- 作者:S. Bereg;Feifei Ma;Wencheng Wang;Jian Zhang;B. Zhu
- 通讯作者:S. Bereg;Feifei Ma;Wencheng Wang;Jian Zhang;B. Zhu
Failure and Communication in a Synchronized Multi-drone System
同步多无人机系统中的故障和通信
- DOI:10.1007/978-3-030-67899-9_33
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Bereg, Sergey;Diaz-Banez, Miguel;Horn, Paul;Lopez, Mario;Urrutia, Jorge
- 通讯作者:Urrutia, Jorge
{{
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 }}
Sergey Bereg其他文献
On Covering Problems of Rado
- DOI:
10.1007/s00453-009-9298-z - 发表时间:
2009-03-17 - 期刊:
- 影响因子:0.700
- 作者:
Sergey Bereg;Adrian Dumitrescu;Minghui Jiang - 通讯作者:
Minghui Jiang
Competitive Algorithms for Maintaining a Mobile Center
- DOI:
10.1007/s11036-006-4470-z - 发表时间:
2006-03-31 - 期刊:
- 影响因子:2.000
- 作者:
Sergey Bereg;Binay Bhattacharya;David Kirkpatrick;Michael Segal - 通讯作者:
Michael Segal
An optimal algorithm for closest pair maintenance (extended abstract)
最近对维护的最佳算法(扩展摘要)
- DOI:
10.1145/220279.220296 - 发表时间:
1995 - 期刊:
- 影响因子:0.8
- 作者:
Sergey Bereg - 通讯作者:
Sergey Bereg
Constructing red-black spanners for mixed-charging vehicular networks
- DOI:
10.1016/j.tcs.2024.114932 - 发表时间:
2025-01-01 - 期刊:
- 影响因子:
- 作者:
Sergey Bereg;Yuya Higashikawa;Naoki Katoh;Junichi Teruyama;Yuki Tokuni;Binhai Zhu - 通讯作者:
Binhai Zhu
On Characterizations of Rigid Graphs in the Plane Using Spanning Trees
- DOI:
10.1007/s00373-008-0836-2 - 发表时间:
2009-05-23 - 期刊:
- 影响因子:0.600
- 作者:
Sergey Bereg - 通讯作者:
Sergey Bereg
Sergey Bereg的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
相似国自然基金
昼夜节律性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 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: Graph Analysis: Integrating Metric and Topological Perspectives
合作研究:AF:小:图分析:整合度量和拓扑视角
- 批准号:
2310412 - 财政年份:2023
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Graph Analysis: Integrating Metric and Topological Perspectives
合作研究:AF:小:图分析:整合度量和拓扑视角
- 批准号:
2310411 - 财政年份:2023
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Expanding the Reach of Topological Data Analysis
AF:小:扩大拓扑数据分析的范围
- 批准号:
2049010 - 财政年份:2020
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Expanding the Reach of Topological Data Analysis
AF:小:扩大拓扑数据分析的范围
- 批准号:
2007961 - 财政年份:2020
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research:Geometric and topological algorithms for analyzing road network data
AF:小型:协作研究:用于分析道路网络数据的几何和拓扑算法
- 批准号:
1618247 - 财政年份:2016
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Geometric and Topological Algorithms for Analyzing Road Network Data
AF:小型:协作研究:用于分析道路网络数据的几何和拓扑算法
- 批准号:
1618605 - 财政年份:2016
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Extending algorithms for topological notions of similarity
AF:小:相似性拓扑概念的扩展算法
- 批准号:
1614562 - 财政年份:2016
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Geometric and Topological Algorithms for Analyzing Road Network Data
AF:小型:协作研究:用于分析道路网络数据的几何和拓扑算法
- 批准号:
1618469 - 财政年份:2016
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Analyzing Complex Data with a Topological Lens
AF:小:用拓扑透镜分析复杂数据
- 批准号:
1526513 - 财政年份:2015
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant
AF: Small: Approximation Algorithms and Topological Graph Theory
AF:小:近似算法和拓扑图论
- 批准号:
1423230 - 财政年份:2014
- 资助金额:
$ 30.25万 - 项目类别:
Standard Grant