Geometric Algorithms for Portable devices

便携式设备的几何算法

• 批准号: 17K12635
• 负责人: Korman Matias
• 金额: $ 2.5万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2017
• 资助国家: 日本
• 起止时间: 2017-04-01 至 2020-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-17K12635/
• 关键词: Algorithms; Computational Geometry; Distributed algorithms; NP-completeness; Data Structures; Simple Polygons; Routing; Sensor Networks; Computer Science; Time-Space Trade-off; Combinatorial Geometry; Ad-Hoc Networks; Ad-hoc Networks; Geometr

Due to a change in location, we decided to interrupt the grant halfway through the year. Nonetheless, several of the milestones were achieved, even those planned for 2020 and 2021:-Although the concept of convex hull is well known and studied, its extension to environment with obstacles was never studied. We introduced the problem, showed its complexity and introduced the first algorithm for computing it-We studied the communication protocol for modular robots. Given a configuration of robots, we are interested in them communication so that they can reach another target shape. Although the problem turned out to be PSPACE hard (proof currently under review), we gave a constructive algorithm for the particular case in which you can add 5 helping robots in the exterior.

由于位置的变化，我们决定中断一年中的一半。但是，达到了一些里程碑，即使是计划在2020年和2021年计划的里程碑： - 尽管凸船的概念是众所周知的，并且研​​究了凸面的概念，但从未研究过它的障碍。我们引入了问题，显示了它的复杂性，并引入了用于计算IT的第一种算法 - 我们研究了模块化机器人的通信协议。给定机器人的配置，我们对它们的通信感兴趣，以便它们可以达到另一个目标形状。尽管事实证明问题很难（目前正在审查），但我们为特定情况提供了一种建设性算法，您可以在外部添加5个帮助机器人。

项目成果

Stabbing segments with rectilinear objects

用直线物体刺穿线段

• DOI: 10.1016/j.amc.2017.04.001
• 发表时间: 2017
• 期刊: Applied Mathematics and Computation
• 影响因子: 4
• 作者: Claverol Merce;Garijo Delia;Korman Matias;Seara Carlos;Silveira Rodrigo I.
• 通讯作者: Silveira Rodrigo I.

High Dimensional Consistent Digital Segments

高维一致数字段

• DOI: 10.1137/17m1136572
• 发表时间: 2018
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Chiu Man-Kwun;Korman Matias
• 通讯作者: Korman Matias

Rectilinear link diameter and radius in a rectilinear polygonal domain

直线多边形域中的直线链接直径和半径

• DOI: 10.1016/j.comgeo.2020.101685
• 发表时间: 2021
• 期刊: Computational Geometry
• 作者: Arseneva Elena;Chiu Man-Kwun;Korman Matias;Markovic Aleksandar;Okamoto Yoshio;Ooms Aur?lien;van Renssen Andr?;Roeloffzen Marcel
• 通讯作者: Roeloffzen Marcel

Computing the L1 geodesic diameter and center of a polygonal domain

计算多边形域的 L1 测地线直径和中心

• DOI: 10.1007/s00454-016-9841-z
• 发表时间: 2017
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: S. W. Bae;M. Korman;J. S. B. Mitchell;Y. Okamoto;V. Polishchuk;and H. Wang. . ;pages 1-28;2016
• 通讯作者: 2016

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

• DOI: 10.4230/lipics.esa.2019.3
• 发表时间: 2019-01-01
• 期刊: 27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019)
• 作者: Akitaya, Hugo A.;Damian, Mirela;van Renssen, Andre
• 通讯作者: van Renssen, Andre