Publications with Boris Aronov
- On the number of minimal 1-Steiner trees.
B. Aronov, M. Bern, and D. Eppstein.
Disc. & Comp. Geom. 12: 29–34, 1994.Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of nd.
- Distance-sensitive point location made easy.
B. Aronov, M. De Berg, D. Eppstein, M. Roeloffzen, and B. Speckmann.
30th European Workshop on Computational Geometry (EuroCG 2014), Dead Sea, Israel, March 2014.
arXiv:1602.00767
Comp. Geom. Theory & Applications 54: 17–31, 2016.We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.
- Better late than never: the complexity of arrangements of polyhedra.
B. Aronov, S. W. Bae, O. Cheong, D. Eppstein, C. Knauer, and R. Seidel.
41st European Workshop on Computational Geometry (EuroCG 2025), Liblice, Czech Republic, pp. 62:1–62:4.
arXiv:2506.03960.
My 1994 paper "On the number of minimal 1-Steiner trees" with Aronov and Bern, in some preliminary manuscript versions, included a bound of \(O(m^{\lceil d/2\rceil}n^{\lfloor d/2\rfloor})\) on the complexity of an arrangement of \(m\) convex polytopes given as intersections of a total of \(n\) halfspaces, interpolating between the upper bound theorem for polytopes and the complexity of hyperplane arrangements. However, the manuscript and the proof were lost. This paper re-proves the result, with better care for the degenerate cases.