About

Boris Aronov is a Professor in the Department of Computer Science and Engineering at NYU Tandon School of Engineering. His research interests include computational algorithms, discrete and combinatorial geometry, and algorithms. Aronov has a distinguished academic background, having earned a Bachelor of Arts in Computer Science and Mathematics from Queens College, City University of New York in 1984, followed by a Master of Science and a Doctor of Philosophy in Computer Science from the Courant Institute, New York University, in 1986 and 1989 respectively. His extensive publication record features numerous contributions to the fields of computational geometry and algorithms, demonstrating his active engagement in advancing theoretical and applied aspects of these disciplines.

Research topics

• Geometry
• Combinatorics
• Mathematics
• Computer Science
• Discrete mathematics
• Mathematical analysis

Selected publications

• A General Technique for Searching in Implicit Sets via Function Inversion

  Algorithmica · 2026-04-13

  preprintOpen access1st author
  PublisherOA PDFDOI

• Compatible Triangulations of Simple Polygons

  ArXiv.org · 2026-03-01

  articleOpen access

  Let $P$ and $Q$ be simple polygons with $n$ vertices each. We wish to compute triangulations of $P$ and $Q$ that are combinatorially equivalent, if they exist. We consider two versions of the problem: if a triangulation of $P$ is given, we can decide in $O(n\log n + nr)$ time if $Q$ has a compatible triangulation, where $r$ is the number of reflex vertices of $Q$. If we are already given the correspondence between vertices of $P$ and $Q$ (but no triangulation), we can find compatible triangulations of $P$ and $Q$ in time $O(M(n))$, where $M(n)$ is the running time for multiplying two $n\times n$ matrices.

  PublisherOA PDF

• Compatible Triangulations of Simple Polygons

  arXiv (Cornell University) · 2026-03-01

  preprintOpen access

  Let $P$ and $Q$ be simple polygons with $n$ vertices each. We wish to compute triangulations of $P$ and $Q$ that are combinatorially equivalent, if they exist. We consider two versions of the problem: if a triangulation of $P$ is given, we can decide in $O(n\log n + nr)$ time if $Q$ has a compatible triangulation, where $r$ is the number of reflex vertices of $Q$. If we are already given the correspondence between vertices of $P$ and $Q$ (but no triangulation), we can find compatible triangulations of $P$ and $Q$ in time $O(M(n))$, where $M(n)$ is the running time for multiplying two $n\times n$ matrices.

  PublisherDOI

• Better Late than Never: the Complexity of Arrangements of Polyhedra

  ArXiv.org · 2025-06-04

  preprintOpen access1st authorCorresponding

  Let $\mathcal{A}$ be the subdivision of $\mathbb{R}^d$ induced by $m$ convex polyhedra having $n$ facets in total. We prove that $\mathcal{A}$ has combinatorial complexity $O(m^{\lceil d/2 \rceil} n^{\lfloor d/2 \rfloor})$ and that this bound is tight. The bound is mentioned several times in the literature, but no proof for arbitrary dimension has been published before.

  PublisherOA PDFDOI

• Eight-Partitioning Points in 3D, and Efficiently Too

  Discrete & Computational Geometry · 2025-06-12 · 1 citations

  articleOpen access1st author

  Abstract An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in $$\mathbb {R}^3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:math> consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in $$\mathbb {R}^3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:math> admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in $$\mathbb {R}^3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:math> admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in $$\mathbb {R}^3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:math> (with prescribed normal direction of one of the planes) in time $$O (n^{7/3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>7</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).

  PublisherOA PDFDOI

• A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $$\mathbb {R}^2$$

  Algorithmica · 2025-08-29

  articleOpen access1st author

  Abstract Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of $$\mathbb {R}^2$$ and let $$\mathcal {D}=\{D_1,\ldots,D_n\}$$ be a set of geodesic disks with respect to the metric d . We prove that $$\mathcal {G}^{\times }(\mathcal {D})$$ , the intersection graph of the disks in $$\mathcal {D}$$ , has a clique-based separator consisting of $$O(n^{3/4+\varepsilon })$$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q - Coloring that runs in time $$2^{O(n^{3/4+\varepsilon })}$$ , assuming the boundaries of the disks $$D_i$$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $$O(n^{7/4+\varepsilon })$$ storage and can report the hop distance between any two nodes in $$\mathcal {G}^{\times }(\mathcal {D})$$ in $$O(n^{3/4+\varepsilon })$$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.

  PublisherOA PDFDOI

• A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains

  DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025-01-01

  preprintOpen access

  We study the problem of computing the L₁-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain 𝕄 ⊂ ℝ², that is, computing the quantity ‖f-g‖₁ = ∫_𝕄 |f(x,y)-g(x,y)| dx dy. If f and g are defined by linear interpolation over triangulations 𝐓_f and 𝐓_g, respectively, of 𝕄 with a total of n triangles, we show that ‖f-g‖₁ can be computed in Õ(n^α) time, where α = max{(ω+1)/2, 8/5}, ω is the matrix multiplication exponent, and Õ notation hides factors of the form n^ε for any ε > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of 𝐓_f and 𝐓_g is κ, then the runtime of our algorithm is Õ(κ^{α-1}n^{2-α}).

  PublisherOA PDFDOI

• On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

  ACM Transactions on Algorithms · 2025-01-10

  articleOpen access

  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 sub-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 obtain the following results. — We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when \(A\) consists of unit-grid squares (i.e., \(A\) is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, 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 preprocessing) 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.

  PublisherDOI

• Publisher Correction: Eight-Partitioning Points in 3D, and Efficiently Too

  Discrete & Computational Geometry · 2025-07-24

  articleOpen access1st author
  PublisherOA PDFDOI

• Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

  ACM Transactions on Algorithms · 2025-03-11

  articleOpen access

  Let \(\mathcal{T}\) be a set of \(n\) flat (planar) semi-algebraic regions in \(\mathbb{R}^{3}\) of constant complexity (e.g., triangles, disks), which we call plates . We wish to preprocess \(\mathcal{T}\) into a data structure so that for a query object \(\gamma\) , which is also a plate, we can quickly answer various intersection queries , such as detecting whether \(\gamma\) intersects any plate of \(\mathcal{T}\) , reporting all the plates intersected by \(\gamma\) , or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in \(\mathbb{R}^{3}\) ( arcs , for short), or (ii) the input objects are arcs and the query objects are plates in \(\mathbb{R}^{3}\) . Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if \(\mathcal{T}\) is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses \(O^{*}(n^{4/3})\) storage (where the \(O^{*}(\cdot)\) notation hides factors of the form \(n^{\varepsilon}\) , for an arbitrarily small \(\varepsilon&gt;0\) ) and answers an arc-intersection query in \(O^{*}(n^{2/3})\) time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter \(s\in[n^{4/3},n^{t_{q}}]\) , where \({t_{q}}\geq 3\) is the number of real parameters needed to specify a query arc, the query time can be decreased to \(O^{*}((n/s^{1/{t_{q}}})^{\tfrac{2/3}{1-1/{t_{q}}}})\) by increasing the storage to \(O^{*}(s)\) . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.

  PublisherDOI

Recent grants

• AF: Small: Exploring Algebraic Methods in Computational and Combinatorial Geometry

  NSF · $348k · 2012–2018

• Understanding Geometric Arrangements: Unions and Beyond

  NSF · $200k · 2008–2012

• BSF:2014170: SINR-Governed Wireless Networks: Geometric Analysis and Algorithms

  NSF · $40k · 2015–2021

• NSF-BSF:AF:Small:Algorithmic Tools for Proximity Problems among Curves

  NSF · $399k · 2021–2026

• AF: Small: Mysteries of Geometric Arrangements

  NSF · $450k · 2011–2017

Frequent coauthors

• Micha Sharir

  Tel Aviv University

  128 shared

• David A. Brown

  University of Massachusetts Dartmouth

  66 shared

• Marc van Kreveld

  49 shared

• Pankaj K. Agarwal

  42 shared

• Frank Staals

  38 shared

• Maarten Löffler

  38 shared

• Mark de Berg

  University of Minnesota

  28 shared

• Esther Ezra

  28 shared