跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.12170 · v1

Optimal Proximity Black Hole Search with Programmable Matter

首次提交 2026-11-09 18:23
版本更新 2026-11-09 18:23
雷达观测 2026-11-10 15:22
arXiv ↗PDF ↗

摘要

The concept of programmable matter (PM) envisions objects composed of tiny, mobile particles capable of self-arrangement, which allows them to change shape, color, and move. We initiate the study of the Black Hole Search problem within the context of PM. The problem involves a dangerous and unnoticeable location, the black hole, that, without a trace, destroys any particle visiting it. In our setting, particles move inside a convex area embedded in a triangular grid, where one vertex is a black hole. The objective is for the particles to identify a restricted set of vertices containing the black hole while ensuring that at least one particle survives. We present an algorithm utilizing three particles capable of assuming just two colors to identify the dangerous region where the black hole resides. Furthermore, we demonstrate that this algorithm is Pareto optimal in terms of number of particles and number of colors required, and asymptotically optimal in terms of number of epochs, where an epoch refers to the minimal time window within which each particle completed an activation cycle at least once.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-09 18:23 · 最新观测版本

Optimal Proximity Black Hole Search with Programmable Matter

The concept of programmable matter (PM) envisions objects composed of tiny, mobile particles capable of self-arrangement, which allows them to change shape, color, and move. We initiate the study of the Black Hole Search problem within the context of PM. The problem involves a dangerous and unnoticeable location, the black hole, that, without a trace, destroys any particle visiting it. In our setting, particles move inside a convex area embedded in a triangular grid, where one vertex is a black hole. The objective is for the particles to identify a restricted set of vertices containing the black hole while ensuring that at least one particle survives. We present an algorithm utilizing three particles capable of assuming just two colors to identify the dangerous region where the black hole resides. Furthermore, we demonstrate that this algorithm is Pareto optimal in terms of number of particles and number of colors required, and asymptotically optimal in terms of number of epochs, where an epoch refers to the minimal time window within which each particle completed an activation cycle at least once.

查看此版本解读 →查看此版本原文 ↗