幾何計算/最適化2026/4/1arXiv:2604.10058

凸集合間の成長距離を高速計算するためのレイ交差アルゴリズム

A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets

凸集合間の成長距離を、ミンコフスキー差集合上のレイ交差問題に帰着させ、内外の多面体近似を反復構築して解く高速アルゴリズムを提案した。

詳しい要約

1. どんなもの？

- 凸集合間の growth distance を高速に計算するアルゴリズムを提案。 - growth distance は、2つのコンパクト凸集合が中心点周りにスケーリングされたときに交差する最小のスケーリング係数。 - 集合の交差と分離を統一的に測る指標。 - サポート関数で表現可能な凸集合を対象。 - ロボティクスにおける motion planning や rigid-body simulation への応用を示す。

2. 先行研究と比べてどこがすごい？

- 従来の最小距離とは異なり、交差と分離を統一的に扱える growth distance を効率的に計算。 - オープンソース実装が多様な凸集合で state-of-the-art 性能を達成。 - 既存手法との詳細な比較は要旨からは不明。

3. 技術・手法の肝は？

- growth distance 問題を Minkowski difference set 上の等価な ray intersection 問題に帰着。 - 内側と外側の多面体近似を反復的に構築して ray intersection 問題を解く。 - アルゴリズムは primal/dual feasibility や monotone convergence などの特性を満たす。

4. どうやって有効だと検証した？

- 広範なベンチマーク結果を提供し、オープンソース実装が多様な凸集合で state-of-the-art 性能を示すことを確認。 - ロボティクス応用（motion planning と rigid-body simulation）で有効性を実証。

5. 議論はある？

- 要旨からは不明。

6. 次に読むべき論文は？

- 要旨で参照/比較されている研究は明記されていない。 - 同分野の関連手法として、GJK (Gilbert-Johnson-Keerthi) アルゴリズムや EPA (Expanding Polytope Algorithm) などが挙げられる。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Akshay Thirugnanam, Koushil Sreenath

分類: cs.RO, cs.CG

原文アブストラクト

In this paper, we discuss an efficient algorithm for computing the growth distance between two compact convex sets with representable support functions. The growth distance between two sets is the minimum scaling factor such that the sets intersect when scaled about some center points. Unlike the minimum distance between sets, the growth distance provides a unified measure for set intersection and separation. We first reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. Then, we propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. We show that our algorithm satisfies several key properties, such as primal and dual feasibility and monotone convergence. We provide extensive benchmark results for our algorithm and show that our open-source implementation achieves state-of-the-art performance across a wide variety of convex sets. Finally, we demonstrate robotics applications of our algorithm in motion planning and rigid-body simulation.

arXivで原文を読む →arXiv概要ページ

← 論文一覧