Pankaj K. Agarwal

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

Let $K$ be a compact, centrally-symmetric, strictly-convex region in ${\mathbb R}^3$, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as $\|\cdot\|_K$. Let ${\mathcal{K}}$ be a set of $n$ homothetic copies of $K$. This paper contains two main sets of results: (i) For a storage parameter $s\in[n,n^3]$, ${\mathcal{K}}$ can be preprocessed in $O^*(s)$ expected time into a data structure of size $O^*(s)$, so that for a query homothet $K_0$ of $K$, an intersection-detection query (determine whether $K_0$ intersects any member of ${\mathcal{K}}$, and if so, report such a member) or a nearest-neighbor query (return the member of ${\mathcal{K}}$ whose $\|\cdot\|_K$-distance from $K_0$ is smallest) can be answered in $O^*(n/s^{1/3})$ time; all $k$ homothets of ${\mathcal{K}}$ intersecting $K_0$ can be reported in additional $O(k)$ time. In addition, the data structure supports insertions/deletions in $O^*(s/n)$ amortized expected time per operation. Here the $O^*(\cdot)$ notation hides factors of the form $n^\varepsilon$, where $\varepsilon>0$ is an arbitrarily small constant, and the constant of proportionality depends on $\varepsilon$. (ii) Let $\mathcal{G}(\mathcal{K})$ denote the intersection graph of ${\mathcal{K}}$. Using the above data structure, breadth-first or depth-first search on $\mathcal{G}(\mathcal{K})$ can be performed in $O^*(n^{3/2})$ expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of ${\mathcal{K}}$ can be solved in $O^*(n^{62/39})$ expected time. Dijkstra's shortest-path algorithm, as well as Prim's MST algorithm, on a $\|\cdot\|_K$-proximity graph on $n$ points in ${\mathbb R}^3$, with edges weighted by $\|\cdot\|_K$, can also be performed in $O^*(n^{3/2})$ time.

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ${\mathbb R}^d$ into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the vertical decomposition of substructures of arrangements for $d = 3, 4$. For example, we obtain sharp bounds on the complexity of the vertical decomposition of the complement of the union of a set of semi-algebraic regions of constant complexity in ${\mathbb R}^3$, and of the minimization diagram of a set of trivariate functions. These results lead to efficient algorithms for a variety of problems involving vertical decompositions, including algorithms for constructing the decompositions themselves and for constructing $(1/r)$-cuttings of substructures of arrangements. They also lead to a data structure for answering point-enclosure queries amid semi-algebraic sets in ${\mathbb R}^3$ and ${\mathbb R}^4$.

Pankaj K. Agarwal, Boris Aronov, Tzvika Geft et al.

Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning problem: Given a set $A$ of parts, find a subset $S\subset A$, referred to as a subassembly, such that $S$ can be rigidly translated to infinity along a prescribed direction without colliding with $A\setminus S$. While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning, which additionally requires each of the two subassemblies, $S$ and $A\setminus S$, to be connected. We show that this problem is NP-complete, settling an open question posed by Wilson et al. (1995) a quarter of a century ago, even when $A$ consists of unit-grid squares (i.e., $A$ is polyomino-shaped). Towards this result, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. On the positive side, we give an $O(2^k n^2)$-time fixed-parameter tractable algorithm (requiring low degree polynomial-time pre-processing) for an assembly $A$ consisting of polygons in the plane, where $n=|A|$ and $k=|S|$. We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in $O(n)$-time.

Pankaj K. Agarwal, Kyle Fox, Oren Salzman

We study a path-planning problem amid a set $\mathcal{O}$ of obstacles in $\mathbb{R}^2$, in which we wish to compute a short path between two points while also maintaining a high clearance from $\mathcal{O}$; the clearance of a point is its distance from a nearest obstacle in $\mathcal{O}$. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let $n$ be the total number of obstacle vertices and let $\varepsilon \in (0,1]$. Our algorithm computes in time $O(\frac{n^2}{\varepsilon ^2} \log \frac{n}{\varepsilon})$ a path of total cost at most $(1+\varepsilon)$ times the cost of the optimal path.

Doron Shaharabani, Oren Salzman, Pankaj K. Agarwal et al.

We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction - the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.