Optimal detection of intersections between convex polyhedra

DOI10.1137/1.9781611973730.109MaRDI QIDQ5363018zbMATH OpenOpenAlexFDO

Authors Stefan Langerman, Luis Barba

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.1001

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: For a polyhedron $P$ in $mathbb{R}^d$, denote by $|P|$ its combinatorial complexity, i.e., the number of faces of all dimensions of the polyhedra. In this paper, we revisit the classic problem of preprocessing polyhedra independently so that given two preprocessed polyhedra $P$ and $Q$ in $mathbb{R}^d$, each translated and rotated, their intersection can be tested rapidly. For $d=3$ we show how to perform such a test in $O(log|P|+log|Q|)$ time after linear preprocessing time and space. This running time is the best possible and improves upon the last best known query time of $O(log|P|log|Q|)$ by Dobkin and Kirkpatrick (1990). We then generalize our method to any constant dimension $d$, achieving the same optimal $O(log|P|+log|Q|)$ query time using a representation of size $O(|P{|}^{lfloord/2floor+varepsilon})$ for any $varepsilon>0$ arbitrarily small. This answers an even older question posed by Dobkin and Kirkpatrick 30 years ago. In addition, we provide an alternative $O(log|P|+log|Q|)$ algorithm to test the intersection of two convex polygons $P$ and $Q$ in the plane.

Recommendations

• A dual approach to detect polyhedral intersections in arbitrary dimensions
• Fast detection of polyhedral intersection
• Reporting intersecting pairs of convex polytopes in two and three dimensions
• scientific article; zbMATH DE number 3926242
• scientific article; zbMATH DE number 1830727

Cited in

(18)

• Reporting intersecting pairs of convex polytopes in two and three dimensions
• Exact join detection for convex polyhedra and other numerical abstractions
• scientific article; zbMATH DE number 3926242 (Why is no real title available?)
• scientific article; zbMATH DE number 4098718 (Why is no real title available?)
• scientific article; zbMATH DE number 176573 (Why is no real title available?)
• scientific article; zbMATH DE number 1318519 (Why is no real title available?)
• A local search algorithm for ray-convex polyhedron intersection
• Approximate polytope membership queries
• scientific article; zbMATH DE number 1830727 (Why is no real title available?)
• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• Approximate convex intersection detection with applications to width and Minkowski sums
• A complete and efficient algorithm for the intersection of a general and a convex polyhedron
• Using sentinels to detect intersections of convex and nonconvex polygons
• Asymmetric convex intersection testing
• A dynamic piecewise-linear geometric index with worst-case guarantees
• A dual approach to detect polyhedral intersections in arbitrary dimensions
• Fast detection of polyhedral intersection
• Space sweep solves intersection of convex polyhedra

This page was built for publication: Optimal detection of intersections between convex polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363018)