跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-17 23:35各信源进度 →

统计口径与数据新鲜度

统计 2026-11-17 07:32 — 2026-11-18 07:32(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-17 23:35库内论文最新更新时间:2026-11-17 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.19992

Two-Robot Evacuation from a Unit Disk in the Segment Visibility Model

Evangelos Kranakis

原文摘要

Under segment visibility, two robots discover a target as soon as it belongs to the segment joining their positions, even if neither robot has physically reached it. We study two unit-speed robots starting at the center of a unit disk that must both reach an exit (target) placed at an unknown point of its boundary. In our model robots are permitted to leave the disk while searching. We give a three-phase tangent-and-arc algorithm whose exact worst-case evacuation time is 2\sqrt{3}+π/3 \approx 4.511299$. We also prove a matching lower bound for the class of descending horizontal full-slice sweeps, allowing asymmetric robot trajectories. The proof uses an exterior path-length inequality and a feasible minimum-half-width symmetrization. Determining the optimal time over all segment-visibility algorithms remains open.

cs.DC

版本更新 · v2arXiv:2604.02491

Online Drone Coverage of Targets on a Line

Stefan Dobrev, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende

原文摘要

We study the online target coverage problem for a mobile drone equipped with a camera with fixed scanning half-angle $α\in (0, π/2)$. Targets appear online at arbitrary positions along the $x$-axis, and upon each arrival the drone must move to a feasible position whose visibility interval covers both the newly revealed target and all previously arrived targets. The objective is to minimize the total Euclidean length of the drone's trajectory, evaluated against an optimal offline trajectory via the competitive ratio. We establish exact competitive ratios across the range $α\in (0, π/2)$ for three natural baseline algorithms,\textsc{Straight-Up}, \textsc{Cone-Apex}, and \textsc{Greedy}. We then analyze fixed-angle steering strategies and derive the optimal fixed-angle algorithm $β^*$-\textsc{Hedge}, which improves upon the baselines for $α\in (π/6, π/3)$ and peaks at $5/4$ when $α= π/4$. Going further, we introduce a family of memoryless, state-based linear interpolation algorithms $\mathcal{A}_λ$ (generalizing the \textsc{Midpoint} rule at $α= π/4$) and prove that the optimized algorithm $\mathcal{A}_{λ^*}$ strictly outperforms $β^*$-\textsc{Hedge} throughout $α\in (0, π/3)$, achieving a tight competitive ratio of $\sqrt{3/2} \approx 1.2247$ at $α= π/4$ while matching the optimal bound $\cscα$ for $β^*$-\textsc{Hedge} on $[π/3, π/2)$. Finally, we establish a universal lower bound on the competitive ratio of any deterministic or randomized online algorithm (against an oblivious adversary) across the entire domain $α\in (0, π/2)$. This lower bound attains its maximum at $α= π/4$ with value $(1 + \sqrt{2})/2 \approx 1.2071$, narrowing the optimal competitive ratio at $α= π/4$ to the interval $[(1+\sqrt{2})/2,\, \sqrt{3/2}]$.

cs.DS

新论文 · v1arXiv:2611.03161

Searching the Plane in the Segment Visibility Model

Evangelos Kranakis

原文摘要

We study deterministic search by $n \geq 2$ unit-speed robots starting at the origin of the Euclidean plane. We introduce the concept of \emph{segment visibility} whereby a stationary target $x$ at distance $d=\|x\|>0$ is discovered at the first instant $t$ when $x$ belongs to the segment joining a pair of robots at time $t$. Discovery time is compared with the omniscient optimum $d$. We distinguish two knowledge models according to whether the robots know $d$ in advance. For $n=2$ robots, in the \emph{known-$d$} model, we give a symmetric four-phase algorithm and prove that its competitive ratio is optimal: $1+\sqrt3+π/6$; the matching lower bound follows from the known-distance two-robot shoreline-search theorem through an explicit reduction to segment detection. For $n=2$ robots, in the \emph{unknown-$d$} model, a three-circle construction and a quantitative initial-path estimate yield the stronger lower bound $\sqrt3+π/6+\sqrt{17}/4 \approx3.286425990$, giving an explicit positive cost for not knowing the radius; we also analyze a feasible antipodal-diameter logarithmic-spiral algorithm with optimized ratio $8.928516954\ldots$, thus proving that the competitive ratio when $d$ is unknown is at least $ \sqrt3+π/6+\sqrt{17}/4 $ and at most $8.928516954\ldots.$ For $n \geq 3$ robots, the competitive ratio of finding the target is exactly $\sec (π/n)$ regardless of whether or not $d$ is known to the robots.

cs.DM · cs.DC