Arrow Research search

Author name cluster

Boris Aronov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
1 author row

Possible papers

19

SODA Conference 2021 Conference Paper

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

  • Pankaj K. Agarwal
  • Boris Aronov
  • Tzvika Geft
  • Dan Halperin

Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O (2 k n 2 )-time algorithm, where n = | A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O ( n ) time.

Details

MFCS Conference 2020 Conference Paper

Dynamic Time Warping-Based Proximity Problems

  • Boris Aronov
  • Matthew J. Katz
  • Elad Sulami

Dynamic Time Warping (DTW) is a well-known similarity measure for curves, i. e. , sequences of points, and especially for time series. We study several proximity problems for curves, where dynamic time warping is the underlying similarity measure. More precisely, we focus on the variants of these problems, in which, whenever we refer to the dynamic time warping distance between two curves, one of them is a line segment (i. e. , a sequence of length two). These variants already reveal some of the difficulties that occur when dealing with the more general ones. Specifically, we study the following three problems: (i) distance oracle: given a curve C in ℝ^d, preprocess it to accommodate distance computations between query segments and C, (ii) segment center: given a set 𝒞 of curves in ℝ^d, find a segment s that minimizes the maximum distance between s and a curve in 𝒞, and (iii) segment nearest neighbor: given 𝒞, construct a data structure for segment nearest neighbor queries, i. e. , return the curve in 𝒞 which is closest to a query segment s. We present solutions to these problems in any constant dimension d ≥ 1, using L_∞ for inter-point distances. We also consider the approximation version of the first problem, using L₁ for inter-point distances. That is, given a length-m curve C in ℝ^d, we construct a data structure of size O(m log m) that allows one to compute a 2-approximation of the distance between a query segment s and C in O(log³ m) time. Finally, we describe an interesting experimental study that we performed, which is related to the first problem above.

Details

SODA Conference 2019 Conference Paper

Constructive Polynomial Partitioning for Algebraic Curves in R 3 with Applications

  • Boris Aronov
  • Esther Ezra
  • Joshua Zahl

In 2015, Guth proved that, for any set of k -dimensional varieties in ℝ 3 and for any positive integer D, there exists a polynomial of degree at most D whose zero-set divides ℝ 3 into open connected “cells, ” so that only a small fraction of the given varieties intersect each cell. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for curves (or even lines) in ℝ 3. We present an efficient algorithmic construction for this setting. Given a set of n input curves and a positive integer D, we efficiently construct a decomposition of space into O ( D 3 log 3 D ) open cells, each of which meets at most O ( n / D 2 ) curves from the input. The construction time is O ( n 2 ), where the constant of proportionality depends on D and the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation, whose running time is O ( n 4/3 polylog n ). As an application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently studied by Aronov et al. (2017) and De Berg (2017). Our main result is an algorithm that cuts n triangles into O ( n 3/2+ ε ) pieces that are depth cycle free, for any ε > 0. The algorithm runs in O ( n 3/2+ ε ) time, which is nearly worst-case optimal. We also sketch several other applications of our effective partitioning for curves in ℝ 3.

Details

FOCS Conference 2001 Conference Paper

On the Complexity of Many Faces in Arrangements of Circles

  • Pankaj K. Agarwal
  • Boris Aronov
  • Micha Sharir

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.

Details

FOCS Conference 1993 Conference Paper

The Union of Convex Polyhedra in Three Dimensions

  • Boris Aronov
  • Micha Sharir

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k/sup 3/+knlog/sup 2/ k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k/sup 3/+knlog/sup 3/ k) expected time. >

Details