Progressive Convex Hull Simplification

arXiv:2604.14468v1 Announcement Type: new Abstract：凸包は衝突検出、レール交点計算、距離計算など多様なタスクの用途において、有効な Tight Bounding Proxies（緊密な境界代理）として役立ちます。しかし、多面体凸包の複雑さは、その入力とともに線形的に増加します。我々は、指定された半空間の数を減らしながら追加される体積や表面積を最小化するという、保守的に凸包を簡略化するという問題に対処します。 Dual representation（Dual表現）を用いて、効率的な O(n log n) グリディアル最適化を提案します。比較において、既存の手法は効率、緊密性、または安全性に欠けることを示します。我々の手法を多様な入力形状およびダウンストリームアプリケーションドメインに対して実証し、その有効性を示しました。

arXiv:2604.14468v1 Announce Type: new Abstract: Convex hulls are useful as tight bounding proxies for a variety of tasks including collision detection, ray intersection, and distance computation. Unfortunately, the complexity of polyhedral convex hulls grows linearly with their input. We consider the problem of conservatively simplifying a convex hull to a specified number of half-spaces while minimizing added volume or surface area. By working in the dual representation, we propose an efficient $O(n \log n)$ greedy optimization. In comparisons, we show that existing methods either exhibit poor efficiency, tightness or safety. We demonstrate the success of our method on a variety of input shapes and downstream application domains.