TopTeachingResearch

Research

What I like to work on

[[At some future point a lucid and witty introduction to computational and combinatorial geometry will appear here. May have to wait until I retire though. :-) ]]

Publications

I. Articles in Refereed Journals or Volumes, by Publication Date

  1. B. Aronov, "On the geodesic Voronoi diagram of point sites in a simple polygon," Algorithmica, 4(1):109-140 (1989). A revised and expanded version of this paper.
  2. B. Aronov and M. Sharir, "Triangles in space, or building (and analyzing) castles in the air," Combinatorica, 10(2):137-173 (1990). A revised and expanded version of this paper.
  3. B. Aronov, S. Fortune, and G. Wilfong, "Minimum speed motions," International Journal of Robotics Research, 10(3):228-239 (1991).
  4. 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).
  5. 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). A revised and expanded version of this paper.
  6. P.K. Agarwal and B. Aronov, "Counting facets and incidences," Discrete and Computational Geometry, 7:359-369 (1992).
  7. 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).
  8. B. Aronov and J. O'Rourke, "Nonoverlap of the star unfolding," Discrete and Computational Geometry, 8:219-250 (1992). A revised and expanded version of this paper.
  9. 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). A revised and expanded version of this paper.
  10. B. Aronov, S. Fortune, and G. Wilfong, "Furthest-site geodesic Voronoi diagram," Discrete and Computational Geometry, 9:217-255 (1993). A revised and expanded version of this paper.
  11. P.K. Agarwal, B. Aronov, M. Sharir, and S. Suri, "Selecting distances in the plane," Algorithmica 9:495-514 (1993). A revised and expanded version of this paper.
  12. B. Aronov, R. Seidel, and D. Souvaine, "On compatible triangulations of simple polygons," Computational Geometry: Theory and Applications, 3:27-35 (1993).
  13. 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).
  14. 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). A revised and expanded version of this paper.
  15. B. Aronov and M. Sharir, "Castles in the air revisited," Discrete and Computational Geometry, 12(2):119-150 (1994). A revised and expanded version of this paper.
  16. B. Aronov, M. Bern, and D. Eppstein, "On the number of minimal 1-Steiner trees," Discrete and Computational Geometry, 12(1):29-34 (1994).
  17. 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). A revised and expanded version of this paper.
  18. P. Agarwal, B. Aronov, N. Alon, and S. Suri, "Can visibility graphs be represented compactly?" Discrete and Computational Geometry, 12:347-365 (1994). A revised and expanded version of this paper.
  19. B. Aronov and J. Matousek, "On stabbing triangles by lines in 3-space," Comment. Math. Univ. Carolinae 36(1):109-113 (1995).
  20. P.K. Agarwal, B. Aronov, and M. Sharir, "Computing envelopes in four dimensions with applications," SIAM J. Computing, 26:1714-1732 (1997). A revised and expanded version of this paper.
  21. B. Aronov, M. Sharir, and B. Tagansky, "The union of convex polyhedra in three dimensions," SIAM J. Computing, 26:1670-1688 (1997). A revised and expanded version of this paper.
  22. B. Aronov and M. Sharir, "On translational motion planning of a convex polyhedron in 3-space," SIAM J. Computing, 26:1785-1803 (1997). A revised and expanded version of this paper.
  23. 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). A revised and expanded version of this paper.
  24. B. Aronov and M. Sharir, "The common exterior of convex polygons in the plane," Computational Geometry: Theory and Applications, 8(1997):139-149.
  25. F. Aurenhammer, F. Hoffmann, and B. Aronov, "Minkowski-type theorems and least-squares clustering," Algorithmica, 20:61-76 (1998). A revised and expanded version of this paper.
  26. 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). A revised and expanded version of this paper.
  27. 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). A revised and expanded version of this paper.
  28. 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). A revised and expanded version of this paper.
  29. 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). A revised and expanded version of this paper.
  30. 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). A revised and expanded version of this paper.
  31. B. Aronov and S. Fortune, "Approximating minimum-weight triangulations in three dimensions," Discrete and Computational Geometry, 21:527-549 (1999). A revised and expanded version of this paper.
  32. 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). A revised and expanded version of this paper.
  33. 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). A revised and expanded version of this paper.
  34. 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).
  35. 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). A revised and expanded version of this paper.
  36. 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). A revised and expanded version of this paper.
  37. B. Aronov and T.K. Dey, "Polytopes in arrangements," Discrete and Computational Geometry, 25:51-63 (2001). A revised and expanded version of this paper.
  38. 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). A revised and expanded version of this paper.
  39. 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). A revised and expanded version of this paper.
  40. 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. A preliminary version in Postscript.
  41. 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).
  42. B. Aronov, "A lower bound on Voronoi diagram complexity," Information Processing Letters, 83:183-185 (2002). A preliminary version in Postscript.
  43. B. Aronov, M. Sharir, "Cutting circles into pseudo-segments and improved bounds for incidences," Discrete and Computational Geometry, 28:475-490 (2002).
  44. 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. A revised and expanded version of this paper. A preliminary version in Postscript.
  45. 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). A revised and expanded version of this paper.
  46. B. Aronov and M. Sharir, "Cell complexities in hyperplane arrangements," Discrete and Computational Geometry, 32:107-115 (2004). A preliminary version in Postscript.
  47. 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. A preliminary version in Postscript.
  48. 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).
  49. 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). A preliminary version in Postscript.
  50. 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. A preliminary version in Postscript.
  51. 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. A preliminary version in Postscript.
  52. 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.
  53. B. Aronov and S. Smorodinsky, "Geometric permutations induced by line transversals through a fixed point," Discrete and Computational Geometry, 34 (2005), 285-294. On SpingerLink here (may need subscription to access this page).
  54. 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). A revised and expanded version of this paper.
  55. 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.
  56. 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.
  57. 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.
  58. 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. A revised and expanded version of this paper. A preliminary version in Postscript.
  59. 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. A revised and expanded version of this paper.
  60. B. Aronov and S. Har-Peled, "On approximating the depth and related problems," SIAM J. Computing, 38 (2008) 899-921. A revised and expanded version of this paper.
  61. 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. A revised and expanded version of this paper. A preliminary version in Postscript. http://dx.doi.org/10.1016/j.comgeo.2007.07.004
  62. 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. http://dx.doi.org/10.1016/j.comgeo.2008.02.005 A revised and expanded version of this paper.
  63. B. Aronov, P. Carmi, and M.J. Katz, "Minimum-cost load-balancing partitions," Algorithmica, 34 (2009) 318-336. http://dx.doi.org/10.1007/s00453-007-9125-3 A revised and expanded version of this paper.
  64. 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. http://dx.doi.org/10.1142/S0218195910003219 A revised and expanded version of this paper.
  65. B. Aronov and M. Sharir, "Approximate halfspace range counting," SIAM J. Computing, 39(2010), 2704-2725.
  66. B. Aronov, E. Ezra, and M. Sharir, "Small-size eps-nets for axis-parallel rectangles and boxes," SIAM J. Computing, 39(2010), 3248-3282. A revised and expanded version of this paper.
  67. B. Aronov, O. Cheong, X. Goaoc, and G. Rote, "Lines pinning lines," Discrete Comput. Geom., 45(2):230-260, http://dx.doi.org/10.1007/s00454-010-9288-6.
  68. B. Aronov, M.J. van Kreveld, M. Löffler, R.I. Silveira, "Peeling meshed potatoes," Algorithmica, 60(2):349-367(2011).
  69. B. Aronov, M. Dulieu, F. Hurtado, "Witness (Delaunay) graphs," Computational Geometry: Theory & Applications, 44(6-7):329-344 (2011); http://dx.doi.org/10.1016/j.comgeo.2011.01.001.
  70. 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). A revised and expanded version of this paper. A revised and expanded version of this paper.
  71. B. Aronov, M. de Berg, "Unions of fat convex polytopes have short skeletons," Discrete Comput. Geom., 48(1):53-64 (2012); see also http://dx.doi.org/10.1007/s00454-012-9422-8.
  72. 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). http://dx.doi.org/10.1016/j.dam.2012.03.009. A revised and expanded version of this paper.
  73. B. Aronov, M. Dulieu, "How to cover a point set with a V-shape of minimum width," Computational Geometry: Theory & Applications, 46(3):298-309 (2013). http://dx.doi.org/10.1016/j.comgeo.2012.09.006, 2012. A revised and expanded version of this paper.
  74. B. Aronov, M. Dulieu, F. Hurtado, "Witness Gabriel graphs," Computational Geometry: Theory & Applications, in press; Computational Geometry: Theory and Applications 46:894-908 (2013); http://dx.doi.org/10.1016/j.comgeo.2011.06.004
  75. B. Aronov, M. Dulieu, F. Hurtado, "Witness rectangle graphs," Graphs and Combinatorics, in press, http://dx.doi.org/10.1007/s00373-013-1316-x, 2013.
  76. P.K. Agarwal, B. Aronov, M. van Kreveld, M. Löffler, and R. Silveira, "Computing correlation between piecewise-linear functions," SIAM J. Computing, accepted for publication.
  77. R. Karasev, A. Hubard, and B. Aronov, "Convex equipartitions: the spicy chicken theorem," Geometriae Dedicata, 2013, accepted for publication; http://dx.doi.org/10.1007/s10711-013-9879-5.

II. Edited volumes

  1. B. Aronov, S. Basu, J. Pach, and M. Sharir, eds, Discrete and Computational Geometry - The Goodman-Pollack Festschrift, Algorithms and Combinatorics, volume 25, Springer Verlag, Berlin, 2003, ISBN: 3-540-00371-1. Springer-Verlag catalog entry here.

III. Proceedings of Refereed Conferences

  1. B. Aronov, "On the geodesic Voronoi diagram of point sites in a simple polygon," Proceedings of 3rd Annual ACM Symposium on Computational Geometry, 1987, pp. 39-49. In ACM Electronic Library here.
  2. B. Aronov, S. Fortune, and G. Wilfong, "The furthest-site geodesic Voronoi diagram," Proceedings of 4th Annual ACM Symposium on Computational Geometry, 1988, pp. 229-240.
  3. B. Aronov and M. Sharir, "Triangles in space, or building (and analyzing) castles in the air," Proceedings of 4th Annual ACM Symposium on Computational Geometry, 1988, pp. 381-391.
  4. 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," Proceedings of 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 112-115.
  5. B. Aronov and S. Suri, "Selecting distances in the plane," with P.K. Agarwal, M. Sharir, and Proceedings of 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 321-331.
  6. P.K. Agarwal, B. Aronov, J. O'Rourke, and C.A. Schevon, "Star unfolding of a polytope with applications," Proceedings of 2nd Scandinavian Workshop on Algorithm Theory, 1990, pp. 251-263.
  7. B. Aronov and J. O'Rourke, "Nonoverlap of the star unfolding," Proceedings of 7th Annual ACM Symposium on Computational Geometry, 1991, pp. 105-114.
  8. B. Aronov, J. Matousek and M. Sharir, "On the sum of squares of cell complexities in hyperplane arrangements," Proceedings of 7th Annual ACM Symposium on Computational Geometry, 1991, pp. 307-313.
  9. B. Aronov, P. Erdös, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, and L.J. Schulman, "Crossing families," Proceedings of 7th Annual ACM Symposium on Computational Geometry, 1991, pp. 351-356.
  10. B. Aronov and M. Sharir, "On the zone of a surface in a hyperplane arrangement," Proceedings of the 2nd Workshop on Algorithms and Data Structures, 1991, pp. 13-19.
  11. B. Aronov and M. Sharir, "Castles in the air revisited," Proceedings of 8th Annual ACM Symposium on Computational Geometry, 1992, pp. 146-156.
  12. F. Aurenhammer, F. Hoffmann, and B. Aronov, "Minkowski-type theorems and least-squares partitioning," Proceedings of 8th Annual ACM Symposium on Computational Geometry, 1992, pp. 350-357.
  13. P. Agarwal, B. Aronov, N. Alon, and S. Suri, "Can visibility graphs be represented compactly?" Proceedings of 9th Annual ACM Symposium on Computational Geometry, 1993, pp. 338-347.
  14. B. Aronov and M. Sharir, "The union of convex polyhedra in three dimensions," Proceedings of 34th Annual IEEE Symposium on Foundations of Computer Science, 1993, pp. 518-527.
  15. B. Aronov and M. Sharir, "On translational motion planning in 3-space," Proceedings of 10th Annual ACM Symposium on Computational Geometry, 1994, pp. 21-30.
  16. P.K. Agarwal, B. Aronov, and M. Sharir, "Computing envelopes in four dimensions with applications," Proceedings of 10th Annual ACM Symposium on Computational Geometry, 1994, pp. 348-358.
  17. P.K. Agarwal, B. Aronov, and S. Suri, "Stabbing triangulations by lines in 3D," Proceedings of 11th Annual ACM Symposium on Computational Geometry, 1995, pp. 267-276.
  18. "Visibility with reflection," B. Aronov, A.R. Davis, T.K. Dey, S.P. Pal, and D.C. Prasad, Proceedings of 11th Annual ACM Symposium on Computational Geometry, 1995, pp. 316-325.
  19. P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir, "Quasi-planar graphs have a linear number of edges," Graph Drawing, Proceedings of Symposium on Graph Drawing (GD'95), LNCS 1027, (F.J. Brandenburg, ed.), 1995, pp. 1-7.
  20. B. Aronov, A.R. Davis, T.K. Dey, S.P. Pal, and D.C. Prasad, "Visibility with multiple reflections," Proceedings of 5th Scandinavian Workshop on Algorithm Theory (SWAT'96), (R. Karlsson, A. Lingas, eds.), 1996, pp. 284-295.
  21. P.K. Agarwal, B. Aronov, N. Amenta, and M. Sharir, "Largest placements and motion planning of a convex polygon," Proceedings 2nd International Workshop on Algorithmic Foundations of Robotics (WAFR'96), 1997, pp. 143-154.
  22. P.K. Agarwal, B. Aronov, and M. Sharir, "Line transversals of balls and smallest enclosing cylinder in three dimensions," Proceedings 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97), 1997, pp. 483-492.
  23. P.K. Agarwal, B. Aronov, and M. Sharir, "On levels in arrangements of lines, segments, planes, and triangles," Proceedings of 13th Annual ACM Symposium on Computational Geometry, 1997, pp. 30-38.
  24. B. Aronov and S. Fortune, "Average-case ray shooting and minimum weight triangulations," Proceedings of 13th Annual ACM Symposium on Computational Geometry, 1997, pp. 203-211.
  25. A. Andrzejak, B. Aronov, S. Har-Peled, R. Seidel, and E. Welzl, "Results on k-sets and j-facets via continuous motion," Proceedings of 14th Annual ACM Symposium on Computational Geometry, 1998, pp. 192-199.
  26. B. Aronov, M. de Berg, F. van der Stappen, P. Svestka, J. Vleugels, "Motion planning for multiple robots," Proceedings of 14th Annual ACM Symposium on Computational Geometry, 1998, pp. 374-382.
  27. B. Aronov, A. Efrat, D. Halperin, M. Sharir, "On the number of regular vertices of the union of Jordan regions," Proceedings of 6th Scandinavian Workshop on Algorithm Theory (SWAT'98), 1998, pp. 322-334.
  28. B. Aronov, M. van Kreveld, R. van Oostrum, and K. Varadarajan, "Facility location on terrains," Proceedings of Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), 1998, pp. 19-28.
  29. B. Aronov, L. J. Guibas, M. Teichmann, and L. Zhang, "Visibility queries in simple polygons and applications," Proceedings of Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), 1998, pp. 357-366.
  30. B. Aronov and T.K. Dey, "Polytopes in arrangements," Proceedings of 15th Annual ACM Symposium on Computational Geometry, 1999, pp. 154-162. In ACM Electronic Library here. A preliminary version in Postscript.
  31. P.K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir, "Approximation and exact algorithms for minimum-width annuli and shells," Proceedings of 15th Annual ACM Symposium on Computational Geometry, 1999, pp. 380-389. In ACM Electronic Library here. A preliminary version in Postscript.
  32. P.K. Agarwal, B. Aronov, and M. Sharir, "Exact and approximation algorithms for minimum-width cylindrical shells," Proceedings of 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 510-517. In ACM Electronic Library here. A preliminary version in Postscript.
  33. B. Aronov, J.E. Goodman, R. Pollack, and R. Wenger, "A Helly-type theorem for hyperplane transversals to well-separated convex sets," Proceedings of 16th Annual ACM Symposium on Computational Geometry, 2000, pp. 57-63. In ACM Electronic Library here. A preliminary version in Postscript.
  34. B. Aronov, H. Brönnimann, D. Halperin, and R. Schiffenbauer, "On the number of views of polyhedral scenes," Proceedings of the Japanese Conference on Discrete and Computational Geometry (JCDCG 2000), Tokai University, Japan, October 2000, volume 2098 in Lecture Notes In Computer Science, pp. 81-90. On SpingerLink here (may need subscription to access this page). A preliminary version in Postscript.
  35. P.K. Agarwal, B. Aronov and M. Sharir, "On the complexity of many faces in arrangements of circles," Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), Las Vegas, Nevada, 2001, pp. 74-83. See here for a new and improved version. A preliminary version in Postscript.
  36. B. Aronov, V. Koltun, and M. Sharir, "Incidences between points and circles in three and higher dimensions," Proceedings of 18th Annual ACM Symposium on Computational Geometry, 2002, pp. 116-122. See here for a new and improved version. A preliminary version in Postscript.
  37. B. Aronov, H. Brönnimann, A.Y. Chang, and Y.-J. Chiang, "Cost prediction for ray tracing," Proceedings of 18th Annual ACM Symposium on Computational Geometry, 2002, pp. 293-302. A preliminary version in Postscript.
  38. B. Aronov, J. Pach, M. Sharir, and G. Tardos, "Distinct distances in three and higher dimensions," Proceedings of Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 541-546.
  39. B. Aronov, V. Koltun, and M. Sharir, "Cutting triangular cycles of lines in space," Proceedings of Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 547-555.
  40. B. Aronov, H. Brönnimann, A.Y. Chang, and Y.-J. Chiang, "Cost-driven octree construction schemes: an experimental study," Proceedings of 19th Annual ACM Symposium on Computational Geometry, 2003, pp. 227-236.
  41. P.K. Agarwal, B. Aronov, V. Koltun, "Efficient algorithms for bichromatic separability," Proceedings 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), 2004, pp. 682-690.
  42. B. Aronov, A. Efrat, V. Koltun, and M. Sharir, "On the union of kappa-round objects in three and four dimensions," Proceedings of 20th Annual ACM Symposium on Computational Geometry, 2004, pp. 383-390. A preliminary version in Postscript.
  43. P.K. Agarwal, B. Aronov, V. Koltun, and M. Sharir, "On lines avoiding unit balls in three dimensions," Proceedings of 20th Annual ACM Symposium on Computational Geometry, 2004, pp. 36-45. A preliminary version in Postscript.
  44. B. Aronov, T. Asano, Y. Kikuchi, S.C. Nandy, S. Sasahara, and T. Uno, "A Generalization of Magic Squares with Applications to Digital Halftoning," Proceedings of 15th International Symposium on Algorithms and Computation (ISAAC 2004), 2004, pp. 89-100.
  45. B. Aronov, T. Asano, N. Katoh, K. Mehlhorn, and T. Tokuyama, "Polyline fitting of planar points under min-sum criteria," Proceedings of 15th International Symposium on Algorithms and Computation (ISAAC 2004), 2004, pp. 77-88. On SpingerLink here (may need subscription to access this page).
  46. B. Aronov and S. Smorodinsky, "On geometric permutations induced by lines transversal through a fixed point," Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), 2005, pp. 251-256.
  47. B. Aronov and S. Har-Peled, "On approximating the depth and related problems," Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), 2005, pp. 886-894.
  48. B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. Haverkort, A. Vigneron, "Sparse geometric graphs with small dilation," Proceedings of 15th International Symposium on Algorithms and Computation (ISAAC 2005), 2006, pp. 50-59.
  49. B. Aronov, A.R. Davis, J. Iacono, and A.S.C. Yu, "The complexity of diffuse reflections in a simple polygon," Proceedings of Latin American Theoretical INformatics Symposium (LATIN'2006), 2006, pp. 93-104.
  50. 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," Proceedings of Latin American Theoretical INformatics Symposium (LATIN'2006), 2006, pp. 80-92.
  51. B. Aronov, S. Har-Peled, C. Knauer, Y. Wang, C. Wenk, "Frechet distance for curves, revisited," Proceedings of 14th Annual European Symposium on Algorithms (ESA 2006), 2006, pp. 52-63.
  52. B. Aronov, P. Carmi, and M.J. Katz, "Minimum-cost load-balancing partitions, Proceedings of 22nd Annual ACM Symposium on Computational Geometry, 2006, pp. 301-308.
  53. B. Aronov, M. de Berg, and C. Gray, "Ray shooting and intersection searching amidst fat convex polyhedra in 3-space," Proceedings of 22nd Annual ACM Symposium on Computational Geometry, 2006, pp. 88-94.
  54. B. Aronov, S. Har-Peled, M. Sharir, "On approximate halfspace range counting and relative epsilon-approximations," Proceedings of 23rd Annual ACM Symposium on Computational Geometry, 2007, pp. 327-336.
  55. B. Aronov, T. Asano, and S. Funke, "Optimal triangulation of a polygon with Steiner points," Proceedings of 18th Annu. Int. Sympos. Algorithms and Computation (ISAAC 2007), 2007, pp. 681-691.
  56. B. Aronov, M. de Berg, C. Gray, and E. Mumford, "Cutting cycles of rods in space: Hardness results and approximation algorithms," Proceedings of 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), 2008, pp. 1241-1248.
  57. B. Aronov, K. Buchin, M. Buchin, B. Jansen, T. de Jong, M. van Kreveld, M. Löffler, J. Luo, R.I. Silveira, and B. Speckmann, "Feed-links for Network Extensions," 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), 2008, pp. 308-316.
  58. B. Aronov, M. de Berg, and S. Thite, "The complexity of bisectors and Voronoi diagrams on realistic terrains," Proc. European Symp. Algorithms (ESA'08), LNCS 5193, pp. 100-111, 2008.
  59. B. Aronov, E. Ezra, and M. Sharir, "Small-size eps-nets for axis-parallel rectangles and boxes," Proceedings of Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 639-648.
  60. 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 with minimum dilation," Algorithms and Data Structures Symposium (WADS'09), 2009, pp. 49-60.
  61. P.K. Agarwal, B. Aronov, M. van Kreveld, M. Löffler, and R. Silveira, "Computing similarity between piecewise-linear functions," Proceedings of 26th Annual ACM Symposium on Computational Geometry, 2010, pp. 375-383.
  62. E. Ezra, B. Aronov, and M. Sharir, "Improved bound for the union of fat triangles," Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 2011, pp. 1778-1785. available on SIAM site.
  63. B. Aronov, M. Dulieu, F. Hurtado, "Witness rectangle graphs," Algorithms and Data Structures Symposium (WADS'11), 2011, pp. 73-85.
  64. B. Aronov, M. Dulieu, "How to cover a point set with a V-shape of minimum width," Algorithms and Data Structures Symposium (WADS'11), 2011, pp. 61-72.
  65. G. Moroz, B. Aronov, "Computing the distance between piecewise-linear bivariate functions," Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12), 2012, pp. 288-293.
  66. B. Aronov, M. de Berg, M, Roeloffzen, and B. Speckmann, "Distance-planar point location," Algorithms and Data Structures Symposium (WADS'13), 2013, pp. 49-60.

IV. Other work

  1. S. Har-Peled, T. M. Chan, B. Aronov, D. Halperin, and J. Snoeyink, "The complexity of a single face of a Minkowski sum," Proceedings of 7th Canadian Conference on Computational Geometry, 1995, 91-96. A compressed .ps version is available from Danny Halperin's site.
  2. B. Aronov, J.E. Goodman, and R. Pollack, "Convexification of planar polygons in R3," manuscript. A preliminary version in Postscript.
  3. B. Aronov and J. Iacono, "Sorting Similar Vectors," manuscript. A preliminary version in Postscript. This is a revised version of the "Detecting Duplicates Among Similar Bit Vectors" manuscript.
  4. B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, S. Smorodinsky, C. Seara, "Small weak epsilon nets" CCCG 2005: Canadian Conference on Computational Geometry, pp. 52-56.
  5. B. Aronov, M. van Kreveld, M. Löffler, and R. Silveira, "Largest subsets of triangles in a triangulation," CCCG 2007: Canadian Conference on Computational Geometry, pp. 213-216. A revised and expanded version of this paper.
  6. A. Hubard and B. Aronov, "Convex equipartitions of volume and surface area," submitted for publication; also in arXiv:1010.4611v3.
  7. B. Aronov, M. de Berg, E. Ezra, and M. Sharir, "Improved bound for the union of locally fat objects in the plane," manuscript in preparation.
  8. B. Aronov, D. Garijoy, Y. Núñez-Rodríguez, D. Rappaport, C. Seara, and J. Urrutia, "Measuring the error of linear separators on linearly inseparable data," presented at JCCGG'09: http://www.jaist.ac.jp/ uehara/JCCGG09/.

Useful/interesting geometry pointers

Seminars, workshops, and conferences, in geometry and theory and random others.

Lists of conferences

I have given up on keeping track of meetings. Either there are many more of them now, or my brain can no longer keep track of them. So below is a short selection of places where one can look the up on the web.

More specific lists:

More general lists:

Ongoing regular events in geometry (or not), in and around Poly (or not)

Geometry-related web pages

Applications of Computational Geometry

David Eppstein's Geometry in Action

Computational Geometry Mailing Lists

For compgeom mailing lists watched over by Ken Clarkson and Sylvain Pion. More information can be found here.

People in geometry

Here are some pointers to lists of people who do computational geometry:

Geometry-related projects

Computational-geometry related research groups


Boris Aronov, June 27, 2013


TopTeachingResearch