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年实现的里程碑：-虽然凸形船体的概念是众所周知的，并进行了研究，但从未研究过将其扩展到有障碍物的环境。我们介绍了这个问题，说明了它的复杂性，并介绍了计算它的第一个算法-我们研究了模块化机器人的通信协议。给定机器人的配置，我们感兴趣的是它们的通信，以便它们可以到达另一个目标形状。虽然这个问题被证明是PSPACE困难的（证明目前正在审查中），但我们给出了一个特定情况下的建设性算法，在这种情况下，您可以在外部添加5个帮助机器人。

项目成果

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

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

High Dimensional Consistent Digital Segments

高维一致数字段

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

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.

Computing the geodesic centers of a polygonal domain

计算多边形域的测地线中心

• 发表时间: 2019
• 期刊: Computational Geometry: Theory and Applications
• 作者: S. W. Bae;M. Korman;and Y. Okamoto
• 通讯作者: and Y. Okamoto