Let \(\mathscr{W} \subset \mathbb{R}^2\) be a planar polygonal environment with n vertices, and let \([k] = \{1, \ldots, k\}\) denote \(k\) unit-square robots translating in \(\mathscr{W}\). Given source and target placements \(s_1, t_1, \ldots, s_k, t_k, \in \mathscr{W}\) for each robot, we wish to compute a collision-free motion plan \(\boldsymbol \pi\), i.e., a coordinated motion for each robot \(i\) along a continuous path from \(s_i\) to \(t_i\), so that robot \(i\) does not leave \(\mathscr{W}\) or collide with any other robot \(j\). Moreover, we additionally require that \(\boldsymbol \pi\) minimizes the sum of the path lengths; this variant is known as min-sum motion planning.

Let W ⊂ ℝ2 be a planar polygonal environment (i.e., a polygon potentially with holes) with a total of n vertices, and let A, B be two robots, each modeled as an axis-aligned unit square, that can translate inside W. Given source and target placements sA,tA,sB, tB ∈ W of A and B, respectively, the goal is to compute a collision-free-motion plan π*, i.e., a motion plan that continuously moves A from sA to tA and B from sB to tB so that A and B remain inside W and do not collide with each other during the motion. Furthermore, if such a plan exists, then we wish to return a plan that minimizes the sum of the lengths of the paths traversed by the robots. Given W,sA,tA,sB,tB and a parameter ɛ > 0, we present an n2ɛ-°(1) log n-time (1 + ɛ)-approximation algorithm for this problem. We are not aware of any polynomial-time algorithm for this problem, nor do we know whether the problem is NP-Hard. Our result is the first polynomial-time (1 + ɛ)-approximation algorithm for an optimal motion-planning problem involving two robots moving in a polygonal environment.

Let be a set of n axis-aligned cubes of arbitrary sizes in ℝ3 in general position. Let ≔ be their union, and let κ be the number of vertices on ∂; κ can vary between O(1) and O(n2). We show that cl(ℝ3 \ ) can be decomposed into O(κ log4 n) axis-aligned boxes with pairwise-disjoint interiors. Given a boundary representation of , such a decomposition can be computed in O(n log2 n + κ log6 n) time. We also show that a decomposition of size O(σ log4 n + κ log2 n), where σ is the number of input cubes that appear on ∂, can be computed in O(n log2 n + σ log8 n + κ log6 n) time. The complexity and runtime bounds improve to O(n log n) if all cubes in are congruent.

Let P be a set of n (non-negatively) weighted points in Rd. We consider the problem of computing a subset of (at most) k diverse and high-valued points of P that lie inside a query range, a problem relevant to many areas such as search engines, recommendation systems, and online stores. The diversity and value of a set of points are measured as functions (say average or minimum) of their pairwise distances and weights, respectively. We study both bicriteria and constrained optimization problems. In the former, we wish to return a set of k points that maximize a weighted sum of their value and diversity measures, and in the latter, we wish to return a set of at most k points that maximize their value and satisfy a diversity constraint. We obtain three main types of results in this paper: Near-linear time (0.5-ε)-approximation algorithms for the bicriteria optimization problem in the offline setting. Near-linear size indexes for the bicriteria optimization problem that for a query rectangle return a (0.5-ε)-approximate solution in time O(k polylog(n)). The indexes can be constructed in O(n polylog(n)) time. Near-linear size indexes for answering constrained optimization range queries. For a query rectangle, a 0.5O(d)-approximate solution can be computed in O(k polylog(n)) time. If we allow some of the returned points to lie at most ε outside of the query rectangle then an (1-ε)-approximate solution can be computed in O(k polylog(n)) time. The indexes are constructed in O(n polylog(n)) and nO(1/εd) time, respectively.