Boris Aronov

Professor

Connect
Boris Aronov

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).