日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

経路計画arXiv:1102.3165

重み付き3次元領域における最短経路の近似アルゴリズム

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

シェア:XThreadsFacebookLINEはてブBluesky

重み付き四面体分割で表された3次元領域において、始点から全頂点への最短経路を1+ε倍以内のコストで多項式時間で近似計算する初のアルゴリズムを提案した。

著者: Lyudmil Aleksandrov, Hristo Djidjev, Anil Maheshwari, Joerg-Rudiger Sack

分類: cs.CG, cs.DS, cs.GR, cs.RO

原文アブストラクト

We present the first polynomial time approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\D$, consisting of $n$ tetrahedra with positive weights, and a real number $\eps\in(0,1)$, our algorithm constructs paths in $\D$ from a fixed source vertex to all vertices of $\D$, whose costs are at most $1+\eps$ times the costs of (weighted) shortest paths, in $O(\C(\D)\frac{n}{\eps^{2.5}}\log\frac{n}{\eps}\log^3\frac{1}{\eps})$ time, where $\C(\D)$ is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov, Maheshwari and Sack [JACM 2005] to three dimensions.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3Google DeepMind、ロボット向けAIを発表新製品・発表
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI