**Research Interests:**
Computational and Combinatorial Geometry Algorithms

**Queens College, City University of New York** 1984

Bachelor of Arts, Computer Science and Mathematics

**Courant Institute, New York University **1986

Master of Science, Computer Science

**Courant Institute, New York University **1989

Doctor of Philosophy, Computer Science

### Journal Articles

B. Aronov, V. Dujmović, P. Morin, A. Ooms and L.F. Schultz Xavier da Silveira, "More Turán-type theorems for triangles in convex point sets," *Electronic Journal of Combinatorics*, 26(1) (2019).

B. Aronov and M.J. Katz, "Batched point location in SINR diagrams via algebraic tools," *ACM Transactions on Algorithms,* 14(4) 41:1{41:29 (2018).

B. Aronov, P. Bose, E.D. Demaine, J. Gudmundsson, J. Iacono, S. Langerman, and M. Smid, "Data structures for halfplane proximity queries and incremental Voronoi diagrams," *Algorithmica *80(11):3316-3334 (2018).

B. Aronov and M. Sharir, "Almost tight bounds for eliminating depth cycles in three dimensions," *Discrete Comput. Geom., *59(3) 725-741 (2018).

B. Aronov, M. Korman, S. Pratt, A. van Renssen, and M. Roelozen, "Time-space trade-o algorithms for triangulating a simple polygon," *Journal on Computational Geometry,* 8(1):105-124 (2017).

B. Aronov, O. Cheong, M.G. Dobbins, and X. Goaoc, "The number of holes in the union of translates of a convex set in three dimensions," *Discrete Comput. Geom.,* 57(1): 104-124 (2017).

P.K. Agarwal, B. Aronov, S. Har-Peled, J.M. Phillips, K. Yi, and W. Zhang, "Nearest neighbor searching under uncertainty II" *ACM Transactions on Algorithms, *13(1):Article 3 (November 2016).

B. Aronov, A. Driemel, M.J. van Kreveld, M. Löffler, and F. Staals, "Segmentation of trajectories on nonmonotone criteria," *ACM Transactions on Algorithms, *12(2):Article 26 (February 2016).

G. Moroz and B. Aronov, "Computing the distance between piecewise-linear bivariate functions," *ACM Transactions on Algorithms, *12(1):Article 3 (February 2016).

B. Aronov, M. de Berg, D. Eppstein, M. Roelozen, and B. Speckmann, "Distance-sensitive planar point location," *Computational Geometry: Theory & Applications,* 54 (April 2016):17-31.

B. Aronov, M. Dulieu, and F. Hurtado, "Mutual witness proximity graphs," *Information Processing Letters,* 114(10):519-523 (2014).

B. Aronov, M. de Berg, E. Ezra, and M. Sharir, "Improved bound for the union of locally fat objects in the plane," *SIAM J. Computing, *43(2):543-572 (2014).

R. Karasev, A. Hubard, and B. Aronov, "Convex equipartitions: the spicy chicken theorem," *Geometriae Dedicata,* 170(1):263-279 (2014).

B. Aronov, M. Dulieu, and F. Hurtado, "Witness rectangle graphs," *Graphs and Combinatorics, *30(4):827-846 (2014).

P.K. Agarwal, B. Aronov, M. van Kreveld, M. Löffler, and R. Silveira, "Computing correlation between piecewise-linear functions," *SIAM J. Computing,* 42(5):1867{1887 (2013).

B. Aronov, M. Dulieu, R. Pinchasi, and M. Sharir, "On the union complexity of diametral disks," *Electr. J. Comb.* 20(2):P53 (2013).

B. Aronov, M. Dulieu, and F. Hurtado, "Witness Gabriel graphs," *Computational Geometry: Theory & Applications,* 46:894-908 (2013).

B. Aronov and M. Dulieu, "How to cover a point set with a V-shape of minimum width," *Computational Geometry: Theory & Applications, *46(3):298-309 (2013).

B. Aronov, D. Garijoy, Y. Núñez-Rodríguez, D. Rappaport, C. Seara, and J. Urrutia, *"Minimizing the error of linear separators on linearly inseparable data," *Disc. Applied Math., *160:1441-1452 (2012).*

B. Aronov and M. de Berg, "Unions of fat convex polytopes have short skeletons," *Discrete Comput. Geom., *48(1):53-64 (2012).

B. Aronov, K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo, R. Silveira, and B. Speckmann, "Connect the dot: Computing feed-links for network extension," *Journal of Spatial Information Science (JOSYS), *No. 3, 3-31 (2011).

B. Aronov, M. Dulieu, and F. Hurtado, "Witness (Delaunay) graphs," *Computational Geometry: Theory & Applications, *44(6-7):329-344 (2011).

B. Aronov, M.J. van Kreveld, M. Löffler, and R.I. Silveira, "Peeling meshed potatoes," *Algorithmica,* 60(2):349-367(2011).

B. Aronov, O. Cheong, X. Goaoc, and G. Rote, "Lines pinning lines," *Discrete Comput. Geom., *45(2):230-260 (2011).

B. Aronov, E. Ezra, and M. Sharir, "Small-size -nets for axis-parallel rectangles and boxes," *SIAM J. Computing,* 39(2010), 3248-3282.

B. Aronov and M. Sharir, "Approximate halfspace range counting," *SIAM J. Computing,* 39(2010), 2704-2725.

B. Aronov, T. Asano, and S. Funke, "Optimal triangulation of a points and segments," *International Journal of Computational Geometry and Applications, *20(2010) 89-104.

B. Aronov, P. Carmi, and M.J. Katz, "Minimum-cost load-balancing partitions," *Algorithmica,* 34 (2009) 318-336.

B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, C. Seara, and S. Smorodinsky, "Small weak epsilon-nets", *Computational Geometry: Theory & Applications, *42 (2009),455-462.

B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. Haverkort, M. Smid, and A. Vigneron, "Sparse geometric graphs with small dilation," *Computational Geometry: Theory & Applications, *40 (2008) 207-219.

B. Aronov and S. Har-Peled, "On approximating the depth and related problems," *SIAM J. Computing,* 38 (2008) 899-921.

B. Aronov, M. de Berg, and C. Gray, "Ray shooting and intersection searching amidst fat convex polyhedra in 3-space," *Computational Geometry: Theory & Applications, *41 (2008), 68-76.

B. Aronov, T. Asano, Y. Kikuchi, S.C. Nandy, S. Sasahara, and T. Uno, "A generalization of magic squares with applications to digital halftoning," *Theory of Computing Systems,* 42 (2008) 143-156.

P.K. Agarwal, B. Aronov, and V. Koltun, "Efficient algorithms for bichromatic separability," *ACM Transactions on Algorithms,* 2 (2006), 209-227.

B. Aronov, H. Brönnimann, A.Y. Chang, and Y.-J. Chiang, "Cost prediction for ray shooting in octrees," *Computational Geometry: Theory & Applications, *34 (2006), 159-181.

B. Aronov, T. Asano, N. Katoh, K. Mehlhorn, and T. Tokuyama, "Polyline fitting of planar points under min-sum criteria,"* International Journal of Computational Geometry and Applications, *16 (2006) 97-116.

P.K. Agarwal, B. Aronov, V. Koltun, and M. Sharir "Lines avoiding unit balls in three dimensions," *Discrete and Computational Geometry, *34 (2005), 231-250.

B. Aronov and S. Smorodinsky, "Geometric permutations induced by line transversals through a fixed point," *Discrete and Computational Geometry,* 34 (2005), 285-294.

B. Aronov, H. Brönnimann, A.Y. Chang, and Y.-J. Chiang, "Cost-driven octree construction schemes: an experimental study," *Computational Geometry: Theory & Applications, *31 (2005) 127-148.

B. Aronov, A. Efrat, V. Koltun, and M. Sharir, \On the union of -round objects in three and four dimensions," *Discrete and Computational Geometry,* 36 (2006), 511-526.

B. Aronov, V. Koltun, and M. Sharir, "Cutting triangular cycles of lines in space," *Discrete and Computational Geometry, *33 (2005), 231-247.

B. Aronov, V. Koltun, and M. Sharir, "Incidences between points and circles in three and higher dimensions," *Discrete and Computational Geometry,* 33 (2005), 185-206.

B. Aronov, R. Schienbauer, and M. Sharir, "On the number of views of translates of a cube and related problems," *Computational Geometry: Theory & Applications, *27:179-192 (2004).

B. Aronov, J. Pach, M. Sharir, and G. Tardos, "Distinct distances in three and higher dimensions," *Combinatorics, Probability and Computing,* 13:283-293 (2004).

B. Aronov and M. Sharir, "Cell complexities in hyperplane arrangements," *Discrete and Computational Geometry, *32:107-115 (2004).

B. Aronov, M. van Kreveld, R. van Oostrum, and K. Varadarajan, "Facility location on a polyhedral surface," *Discrete and Computational Geometry, *30:357-372 (2003).

P.K. Agarwal, B. Aronov, and M. Sharir, "On the complexity of many faces in arrangements of pseudo-segments and circles," in *Discrete and Computational Geometry* *- The Goodman-Pollack Festschrift* (B. Aronov, S. Basu, J. Pach, and M. Sharir, eds), in the series: Algorithms and Combinatorics, volume 25, Springer Verlag, Berlin, 2003, 1-24.

B. Aronov and M. Sharir, "Cutting circles into pseudo-segments and improved bounds for incidences," *Discrete and Computational Geometry, *28:475-490 (2002).

B. Aronov, "A lower bound on Voronoi diagram complexity," *Information Processing Letters, *83:183-185 (2002).

B. Aronov, J.E. Goodman, and R. Pollack, "A Helly-type theorem for higher-dimensional transversals." *Computational Geometry: Theory and Applications,* 21:177-183 (2002).

B. Aronov, L. J. Guibas, M. Teichmann, and L. Zhang, "Visibility queries and maintenance in simple polygons," *Discrete and Computational Geometry, *27:461-483 (2002).

P.K. Agarwal, B. Aronov, and M. Sharir, "Exact and approximation algorithms for minimum-width cylindrical shells," *Discrete and Computational Geometry,* 26:307-320 (2001).

B. Aronov, J.E. Goodman, R. Pollack, and R. Wenger, "A Helly-type theorem for hyperplane transversals to well-separated convex sets," *Discrete and Computational Geometry, *25:507-517 (2001).

B. Aronov and T.K. Dey, "Polytopes in arrangements," *Discrete and Computational Geometry, *25:51-63 (2001).

B. Aronov, A. Efrat, D. Halperin, and M. Sharir, "On the number of regular vertices of the union of Jordan regions," *Discrete and Computational Geometry, *25:203-220 (2001).

P.K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir, "Approximation algorithms for minimum-width annuli and shells," *Discrete and Computational Geometry,* 24:687-705 (2000).

B. Aronov, J.E. Goodman, R. Pollack, and R. Wenger, "On the Helly number for hyperplane transversals to unit balls," *Discrete and Computational Geometry, *24:171-176 (2000).

B. Aronov, M. de Berg, F. van der Stappen, P. Švestka, and J. Vleugels, "Motion planning for multiple robots," *Discrete and Computational Geometry, *22:505-525 (1999).

B. Aronov, J.E. Goodman, R. Pollack, and R. Wenger, "On the Helly number for hyperplane transversals to unit balls," *Discrete and Computational Geometry,* 24:171-176 (2000).

B. Aronov, M. de Berg, F. van der Stappen, P. Švestka, and J. Vleugels, "Motion planning for multiple robots," *Discrete and Computational Geometry, *22:505-525 (1999).

P.K. Agarwal, B. Aronov, and M. Sharir, "Motion planning for a convex polygon in a polygonal environment." *Discrete and Computational Geometry, *22:201-221 (1999).

B. Aronov and S. Fortune, "Approximating minimum-weight triangulations in three dimensions," *Discrete and Computational Geometry,* 21:527-549 (1999).

P.K. Agarwal, B. Aronov, and M. Sharir, "Line transversals of balls and smallest enclosing cylinder in three dimensions," *Discrete and Computational Geometry,* 21:373-388 (1999).

B. Aronov, A.R. Davis, T.K. Dey, S.P. Pal, and D.C. Prasad, "Visibility with multiple reflections," *Discrete and Computational Geometry, *20:61-78 (1998).

B. Aronov, A.R. Davis, T.K. Dey, S.P. Pal, and D.C. Prasad, "Visibility with one reflection," *Discrete and Computational Geometry, *19:553-574 (1998).

P.K. Agarwal, B. Aronov, T.M. Chan, and M. Sharir, "On levels in arrangements of lines, segments, planes, and triangles," *Discrete and Computational Geometry, *19:315-331 (1998).

P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir, "Quasi-planar graphs have a linear number of edges,"* Combinatorica, *17:1-9 (1997).

F. Aurenhammer, F. Homann, and B. Aronov, "Minkowski-type theorems and least-squares clustering," *Algorithmica,* 20:61-76 (1998).

B. Aronov and M. Sharir, "The common exterior of convex polygons in the plane," Computational *Geometry: Theory and Applications, *8(1997):139-149.

P.K. Agarwal, B. Aronov, J. O'Rourke, and C.A. Schevon, "Star unfolding of a polytope with applications," *SIAM J. Computing, *26:1689-1713 (1997).

B. Aronov and M. Sharir, "On translational motion planning of a convex polyhedron in 3-space," *SIAM J. Computing, *26:1785-1803 (1997).

B. Aronov and M. Sharir, "On translational motion planning of a convex polyhedron in 3-space," *SIAM J. Computing, *26:1785-1803 (1997).

P.K. Agarwal, B. Aronov, and M. Sharir, "Computing envelopes in four dimensions with applications," *SIAM J. Computing, *26:1714-1732 (1997).

B. Aronov and J. Matoušek, "On stabbing triangles by lines in 3-space," *Comment. Math. Univ. Carolinae* 36(1):109-113 (1995).

P. Agarwal, B. Aronov, N. Alon, and S. Suri, "Can visibility graphs be represented compactly?" *Discrete and Computational Geometry, *12:347-365 (1994).

B. Aronov, P. Erdős, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, and L.J. Schulman, "Crossing families," *Combinatorica, *14(2):127-134 (1994).

B. Aronov, M. Bern, and D. Eppstein, "On the number of minimal 1-Steiner trees,"* Discrete and Computational Geometry, *12(1):29-34 (1994).

B. Aronov and M. Sharir, "Castles in the air revisited," *Discrete and Computational Geometry, *12(2):119-150 (1994).

B. Aronov, J. Matoušek, and M. Sharir, "On the sum of squares of cell complexities in hyperplane arrangements," *Journal of Combinatorial Theory,* Series A, 65:311-321 (1994).

B. Aronov, D.Q. Naiman, J. Pach, and M. Sharir, "An invariant property of balls in arrangements of hyperplanes," *Discrete and Computational Geometry, *10:421-425 (1993).

B. Aronov, R. Seidel, and D. Souvaine, "On compatible triangulations of simple polygons," *Computational Geometry: Theory and Applications, *3:27-35 (1993).

P.K. Agarwal, B. Aronov, M. Sharir, and S. Suri, "Selecting distances in the plane," *Algorithmica *9:495-514 (1993).

B. Aronov, S. Fortune, and G. Wilfong, "Furthest-site geodesic Voronoi diagram," *Discrete and Computational Geometry,* 9:217-255 (1993).

B. Aronov, M. Pellegrini, and M. Sharir, "On the zone of a surface in a hyperplane arrangement," *Discrete and Computational Geometry, *9(2):177-188 (1993).

B. Aronov and J. O'Rourke, "Nonoverlap of the star unfolding," *Discrete and Computational Geometry, *8:219-250 (1992).

B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, "The number of edges of many faces in a line segment arrangement,"* Combinatorica,* 12:261-274 (1992).

P.K. Agarwal and B. Aronov, "Counting facets and incidences," *Discrete and Computational Geometry,* 7:359-369 (1992).

B. Aronov, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, and R. Wenger, "Points and triangles in the plane and halving planes in space," *Discrete and Computational Geometry, *6:435-442 (1991).

P.K. Agarwal, A. Aggarwal, B. Aronov, S.R. Kosaraju, B. Schieber, and S. Suri, "Computing external farthest neighbors for a simple polygon," *Discrete and Applied Mathematics,* 31:97-111 (1991).

B. Aronov, S. Fortune, and G. Wilfong, "Minimum speed motions," International Journal of Robotics Research, 10(3):228-239 (1991).

B. Aronov and M. Sharir, "Triangles in space, or building (and analyzing) castles in the air,"* Combinatorica,* 10(2):137-173 (1990).

B. Aronov, "On the geodesic Voronoi diagram of point sites in a simple polygon," *Algorithmica,* 4(1):109-140 (1989).