Boris Aronov

Boris Aronov

Professor

Computer Science and Engineering

Journal Articles

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

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

B. Aronov, S. Fortune, and G. Wilfong, "Minimum speed motions," International Journal of Robotics Research, 10(3):228-239 (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, 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 and B. Aronov, "Counting facets and incidences," Discrete and Computational Geometry, 7:359-369 (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).

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

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, S. Fortune, and G. Wilfong, "Furthest-site geodesic Voronoi diagram," Discrete and Computational Geometry, 9:217-255 (1993).

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

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

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, J. Matousek, 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 and M. Sharir, "Castles in the air revisited," Discrete and Computational Geometry, 12(2):119-150 (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, P. Erdös, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, and L.J. Schulman, "Crossing families," Combinatorica, 14(2):127-134 (1994).

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 and J. Matousek, "On stabbing triangles by lines in 3-space," Comment. Math. Univ. Carolinae 36(1):109-113 (1995).

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

B. Aronov, M. Sharir, and B. Tagansky, "The union of convex polyhedra in three dimensions," SIAM J. Computing, 26:1670-1688 (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, 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, "The common exterior of convex polygons in the plane," Computational Geometry: Theory and Applications, 8(1997):139-149.

F. Aurenhammer, F. Hoffmann, and B. Aronov, "Minkowski-type theorems and least-squares clustering," Algorithmica, 20:61-76 (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).

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

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

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

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 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, "Motion planning for a convex polygon in a polygonal environment." Discrete and Computational Geometry, 22:201-221 (1999).

B. Aronov, M. de Berg, F. van der Stappen, P. Svestka, 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).

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, A. Efrat, D. Halperin, M. Sharir, "On the number of regular vertices of the union of Jordan regions," Discrete and Computational Geometry, 25:203-220 (2001).

B. Aronov and T.K. Dey, "Polytopes in arrangements," Discrete and Computational Geometry, 25:51-63 (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).

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, L. J. Guibas, M. Teichmann, and L. Zhang, "Visibility queries and maintenance in simple polygons," Discrete and Computational Geometry, 27:461-483 (2002). A revised and expanded version of this paper.

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, "A lower bound on Voronoi diagram complexity," Information Processing Letters, 83:183-185 (2002).

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

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, M. Sharir, eds), in the series: Algorithms and Combinatorics, volume 25, Springer Verlag, Berlin, 2003, 1-24.

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

B. Aronov and M. Sharir, "Cell complexities in hyperplane arrangements," Discrete and Computational Geometry, 32:107-115 (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). A revised and expanded version of this paper.

B. Aronov, R. Schiffenbauer, 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, V. Koltun, and M. Sharir, "Incidences between points and circles in three and higher dimensions," Discrete and Computational Geometry, 33 (2005), 185-206. On SpingerLink here (may need subscription to access this page).

B. Aronov, V. Koltun, and M. Sharir, "Cutting triangular cycles of lines in space," Discrete and Computational Geometry, 33 (2005), 231-247. On SpingerLink here (may need subscription to access this page). A revised and expanded version of this paper.

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

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 and S. Smorodinsky, "Geometric permutations induced by line transversals through a fixed point," Discrete and Computational Geometry, 34 (2005), 285-294.

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. http://dx.doi.org/10.1007/s00454-005-1166-2 On SpingerLink here (may need subscription to access this page).

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.

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, Y. Kikuchi, S.C. Nandy, S. Sasahara, and T. Uno, "A generalization of magic squares with applications to digital halftoning," Theory of Computing Systems, accepted for publication.

P.K. Agarwal, B. Aronov, and V. Koltun, "Efficient algorithms for bichromatic separability," ACM Transactions on Algorithms, 2 (2006), 209-227. A revised and expanded version of this paper.

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, to appear. A revised and expanded version of this paper. A preliminary version in Postscript. http://dx.doi.org/10.1016/j.comgeo.2007.07.004

B. Aronov, M. de Berg, and C. Gray, "Ray shooting and intersection searching amidst fat convex polyhedra in 3-space," Computational Geometry: Theory & Applications, to appear.

B. Aronov, P. Carmi, and M.J. Katz, "Minimum-cost load-balancing partitions," Algorithmica, to appear.

Education

Courant Institute, New York University, Class of 1989

Doctor of Philosophy, Computer Science

Courant Institute, New York University, Class of 1986

Master of Science, Computer Science

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

Bachelor of Arts, Computer Science and Mathematics

Research Interests

Computational and Combinatorial Geometry
Algorithms