On the complexity of the free space of a translating square in ℝ 3 \mathbb{R}^{3}

Gabriel Nivasch · 2025

Read On the complexity of the free space of a translating square in ℝ 3 \mathbb{R}^{3} by Gabriel Nivasch (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22386.txt.

Introduction

Gabriel Nivasch studies how complex the free space can be for a box shaped robot that slides without turning among still polyhedral obstacles in three dimensions. Free space means all placements where the box touches no obstacle interior. Earlier work set looser upper bounds for general polyhedral robots and for box robots.

Nivasch proves the bound for a box is on the order of n squared, where n counts obstacle vertices. He proves the same bound for convex polygons whose edges come in parallel pairs. These results settle the worst case growth question for boxes and for all convex polygons.

Catalog record

CREATORGabriel Nivasch
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22386

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the complexity of the free space of a translating square in ℝ 3 \mathbb{R}^{3} Gabriel Nivasch Abstract Consider a polyhedral robot B B that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in ℝ 3 \mathbb{R}^{3} . The free space ℱ \mathcal{F} of B B is the set of all positions in which B B is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of O ⁡ ( n 2 ​ log ⁡ n ) O(n^{2}\log n) for the combinatorial complexity of ℱ \mathcal{F} , where n n is the total number of vertices of the obstacles, and the complexity of B B is assumed constant. Halperin and Yap (1993) showed that, if B B is either a “flat” convex polygon or a three-dimensional box, then a tighter bound of O ⁡ ( n 2 ​ α ​ ( n ) ) O(n^{2}\alpha(n)) holds. Here α ⁡ ( n ) \alpha(n) is the inverse Ackermann function. In this paper we prove that if B B is a square (or a rectangle or a parallelogram), then the complexity of ℱ \mathcal{F} is O ⁡ ( n 2 ) O(n^{2}) . We conjecture that this bound holds more generally if B B is any convex polygon whose edges come in parallel pairs. For such polygons B B , the only triple contacts whose number we were not able to bound by O ⁡ ( n 2 ) O(n^{2}) are those made by three mutually non-parallel edges of B B . Similarly, for the case where B B is a cube (or a box or a parallelepiped), we bound by O ⁡ ( n 2 ) O(n^{2}) all triple contacts except those made by three mutually non-parallel edges of B B . Keywords: motion planning, computational geometry, Minkowski sum, lower envelope 1 Introduction One of the most basic problems studied in algorithmic motion planning is that of moving a rigid “robot” B among fixed obstacles. There are many possible instances of the problem, depending on the dimension of the ambient space ( \mathbb{R}^{2} , \mathbb{R}^{3} , etc.), the shape of the robot, and the type of motion allowed (e.g. whether the robot is allowed to rotate or just to translate). Usually we are given an initial placement of the robot, as well as a desired final placement, and the objective is to find a continuous motion that takes the robot from the initial placement to the final one, while avoiding the obstacles at all times (or determine that no such motion exists). Each placement of the robot can be parametrized by a k -tuple of real numbers, where k is the number of degrees of freedom of the robot. The configuration space is thus a k -dimensional space, each point of which corresponds to a placement of the robot. The free space of the robot is the subset of the configuration space that corresponds to all placements that are free (or legal ), in the sense that the robot does not intersect any obstacle. In the case where both the robot and the obstacles are polyhedra in \mathbb{R}^{3} and the robot can only translate, the configuration space is also three-dimensional, and the free space has polyhedral boundaries, consisting of vertices, edges, and faces. A basic parameter in the analysis of many motion planning algorithms is the combinatorial complexity of the free space, meaning the total number of vertices, edges and faces in the boundary of the free space. Hence, a natural question is to determine the worst-case complexity of the free space in different scenarios. See the survey chapter by Halperin et al. [ 2 ] for more background on algorithmic motion planning. In this paper we consider the case in which the robot is either a “flat” convex polygon or a convex polyhedron that can only translate, and the obstacles are polyhedra in \mathbb{R}^{3} . We denote the total number of vertices of the obstacles by n . Then the total number of edges and faces of the obstacles is \Theta(n) as well. The number of vertices of the robot is assumed constant. As will be explained below in more detail, the complexity of \mathcal{F} is asymptotically determined by the number of triple contacts between the robot and obstacles, i.e. the number of free placements in which three distinct robot features (vertices, edges, or faces) simultaneously make contact with three distinct obstacle features. Hence, a trivial upper bound for the complexity of the free space is O(n^{3}) . Aronov and Sharir [ 1 ] improved the upper bound to O(n^{2}\log n) . Halperin and Yap [ 3 , 4 ] studied the cases where the robot is a “flat” convex polygon and a three-dimensional box. For both these cases they derived an upper bound of O(n^{2}\alpha(n)) , where \alpha(n) is the very slow-growing inverse Ackermann function. The inverse-Ackermann factor arises from consideration of upper and lower envelopes of segments. Halperin and Yap [ 4 ] also proved that if the robot is a rectangle and the obstacles are n lines , then the complexity of \mathcal{F} is O(n^{2}) . Figure 1: Configuration that achieves \Omega(n^{2}\alpha(n)) triple contacts with a triangular robot. The robot is parallel to the xz -plane. There is a configuration of n/2 obstacle edges parallel to the xy -plane that form \Omega(n\alpha(n)) lower-envelope intersections, in which the edges are given slightly different z -coordinates ( a ). There are another n/2 obstacle edges parallel to the y -axis with different z -coordinates ( b ). Regarding lower bounds for the complexity of \mathcal{F} , a lower bound of \Omega(n^{2}) is easy to obtain for any robot. For some types of robots (e.g. a triangle) one can obtain a lower bound of \Omega(n^{2}\alpha(n)) (Aronov and Sharir [ 1 ] ). See Figure 1 . For the two-dimensional case, in which B is a convex polygon free to translate in \mathbb{R}^{2} and the obstacles are polygons with a total of n vertices, the complexity of \mathcal{F} is O(n) (Kedem et al. [ 6 ] ). Note that, by affine transformations, the cases where B is a square, or any rectangle or parallelogram, are all equivalent. Similarly, the cases where B is a cube or a box or a parallelepiped are all equivalent. 1.1 Our results In this paper we prove the following: Theorem 1 . Let B be a square robot that is free to translate in \mathbb{R}^{3} amidst polyhedral obstacles that have a total of n vertices. Then the complexity of the free space of B is O(n^{2}) . As mentioned before, Halperin and Yap proved this bound only when the obstacles are infinite lines. Figure 2: A fully-parallel polygon. We also study a more general class of polygonal robots. We call a convex polygon fully parallel if its edges come in parallel pairs (not necessarily of the same length). See Figure 2 . It is easy to see that the lower bound of \Omega(n^{2}\alpha(n)) shown in Figure 1 can be achieved with any polygonal robot that is not fully parallel, as well as with any polyhedral robot that can be projected to form a non-fully-parallel polygon. On

Read the complete text