Shakhar's Home Page




Address:
Shakhar Smorodinsky
Department of Mathematics, Ben-Gurion University,
Be'er Sheva 84105
Israel


Office: +972-8-6461604
Fax: +972-8-6477648

Email: "My first name" at math.bgu.ac.il



Research areas:
computational and combinatorial geometry, sensor and wireless networks, online algorithms, discrete math.


Teaching

  • Graph Theory (Fall semester)
  • Seminar: Topics in discrete geometry (Spring semester)

  • Publications

  • ***NEW*** : A Survey on Conflict-Free Colorings,
    To appear in "Geometry---Intuitive, Discrete, and Convex", (I. Barany, K.J. Boroczky, G. Fejes Toth, J. Pach, eds.) Bolyai Society Mathematical Studies, Springer.

  • Journal papers

  • S. Smorodinsky, J.S.B. Mitchell, M. Sharir,
    Sharp Bounds on Geometric Permutations for Pairwise Disjoint Balls in R^d, Discrete & Comput. Geom (DCG) 23:247-259 (2000).

  • M. Sharir, S. Smorodinsky, G. Tardos,
    An Improved Bound for k-Sets in Three Dimensions Discrete & Comput. Geom (DCG) 26:195-204 (2001).

  • M. Sharir, S. Smorodinsky
    On Neighbors in Geometric Permutations, Discrete Mathematics 268:327-335 (2003).

  • P.K. Agarwal, E. Nevo, J. Pach, R. Picnchasi, M. Sharir, S. Smorodinsky
    Lenses in Arrangements of Pseudo-circles and their Applications,
    JACM 51(2): 139-186 (2004).

  • S. Smorodinsky, M. Sharir,
    Selecting Points that are Heavily Covered by Pseudo-circles, Spheres or Rectangles,
    Combinatorics, Probability & Computing, 13 (2004), 389--411.

  • G. Even, Z. Lotker, D. Ron, S. Smorodinsky,
    Conflict-Free Colorings of Simple Geometric Regions With Applications to Frequency Assignment in Cellular Networks,
    SIAM J. Comput. (SICOMP) 33(1): 94-136 (2003).

  • S. Har-Peled, S. Smorodinsky,
    Conflict-Free Coloring of Points and Simple Regions in the Plane,
    Discrete & Comput. Geom (DCG), 34: 47-70 (2005).

  • K. Chen, A. Fiat, H. Kaplan, M, Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl,
    Online Conflict-Free Coloring for Intervals,
    SIAM J. Comput. (SICOMP), 36: 1342--1359 (2006).

  • B. Aronov, S. Smorodinsky,
    On Geometric Permutations Induced by Lines Transversal through a Fixed Point,
    Discrete & Comput. Geom ( DCG), 34(2):285--294 (2005).

  • J. Matousek, M. Sharir, S. Smorodinsky, U. Wagner,
    On K-Sets in Four dimensions,
    Discrete & Comput. Geom ( DCG), 35(2):177--191 (2006).

  • R. Dhandapani, J.E. Goodman, A. Holmsen, R. Pollack, S. Smorodinsky,
    Convexity in Topological Affine Planes,
    Discrete & Comput. Geom (DCG), 38:243--257 (2007).

  • S. Smorodinsky,
    On The Chromatic Number of Some Geometric Hypergraphs,
    Siam Journal on Discrete Mathematics (SIDMA), 21(3) 676--687 (2007).

  • N. Alon, S. Smorodinsky,
    Conflict-Free Colorings of Shallow Discs,
    International Journal of Computational Geometry and Applications
    (IJCGA), to appear (2008)
    Special issue devoted to the 22nd ACM Symposium on Computational Geometry, ( SoCG ).

  • B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, C. Seara, S. Smorodinsky
    Small Weak Epsilon Nets,
    Computational Geometry: Theory and Applications ( CGTA ),42:455-462, 2009.
    Special issue devoted to 17th Canadian Conference on Computational Geometry ( CCCG ).

  • N. Alon, H. Kaplan, G. Nivasch, M. Sharir and S. Smorodinsky,
    Weak epsilon-nets and interval chains,
    J. ACM, 55(6): (2008).

  • A. Bar-Noy, P. Cheilaris and S. Smorodinsky,
    Deterministic Conflict-Free Coloring for Intervals: from Offline to Online,
    ACM Transactions on Algorithms, 4(4) 44:1--18, (2008).

  • S. Smorodinsky,
    A note on the online first-fit algorithm for coloring $k$-inductive graphs,
    Information Processing Letters (IPL), 109 44--45, (2008).

  • G. Aloupis, J. Cardinal, S. Collette, S. Langerman and S. Smorodinsky,
    Coloring Geometric Range Spaces,
    Discrete & Comput. Geom (DCG), 41(2): 348-362 (2009)


  • A. Bar-Noy, P. Cheilaris, S. Olonetsky and S. Smorodinsky,
    Online conflict-free colorings for hypergraphs,
    Combinatorics, Probability & Computing (CPC), 19:493-516 (2010)


  • G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, S. Smorodinsky, P. Taslakian
    Colorful Strips,
    Graphs and Combinatorics, 27(3) 327-339 (2011).

  • S. Smorodinsky and Y. Yuditsky
    Polychromatic coloring for half-planes, Journal of Combinatorial Theory series A, accepted.
  • Conference papers


  • S. Smorodinsky, J.S.B. Mitchell, M. Sharir,
    Sharp Bounds on Geometric Permutations for Pairwise Disjoint Balls in R^d,
    In Proc. of the 15th ACM Symposium on Computational Geometry (SoCG) , pp. 400--406, 1999.
    Presentation

  • M. Sharir, S. Smorodinsky, G. Tardos,
    An Improved Bound for k-Sets in Three Dimensions
    In Proc. of the 16th ACM Symposium on Computational Geometry (SoCG) , pp. 43--49, 2000 .

  • M. Sharir, S. Smorodinsky
    Extremal Configurations and Le vels in Pseudoline Arrangements, In Proc.of WADS 2003.
    Presentation

  • M. Sharir, S. Smorodinsky
    On Neighbors in Geometric Permutations,
    In Proc. of the Eighth Scandinavian Workshop on Algorithms Theory, pp.~131--139, SWAT 2002.
    Presentation

  • E. Nevo, J. Pach, R. Picnchasi, M. Sharir, S. Smorodinsky
    Lenses in Arrangements of Pseudo-circles and their Applications,
    In Proc. of the 18th ACM Symposium on Computational Geometry June 5-7, ( SoCG 2002), Barcelona Spain.

  • G. Even, Z. Lotker, D. Ron, S. Smorodinsky,
    Conflict-Free Colorings of Sim ple Geometric Regions With Applications to Frequency Assignment in Cellular Networks,
    In proc. 43rd Annual IEEE Symposium on Foundations of Computer Science ( FOCS )pp. 691-700, 2002.

  • S. Har-Peled, S. Smorodinsky,
    Conflict-Free Coloring of Points and Simple Regions in the Plane,
    In Proc. of the 19th ACM Symposium on Computational Geometry (SoCG) , pp. 114--123, 2003.

  • R. Pinchasi, S. Smorodinsky, On Locally Delaunay Geometric Graphs,
    In Proc. of the 20th ACM Symposium on Computational Geometry (SoCG 2004), pp. 378--382, june 9-11. Polytechnic University in Brooklyn, New York, U.S.A. Presentation

  • A. Fiat, M, Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl,
    Online Conflict-Free Coloring for Intervals,
    In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005).
    Presentation

  • B. Aronov, S. Smorodinsky,
    On Geometric Permutations Induced by Lines Transversal through a Fixed Point,
    In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005).
    Presentation

  • A. Bar-Noy, P. Cheilaris, S. Smorodinsky,
    Conflict-Free Coloring for Intervals: from Offline to Online,
    In Proc. of the 18th ACM Symposium on Parallelism in Algorithms and Architectures, ( SPAA 2006)

  • N. Alon, S. Smorodinsky,
    Conflict-Free Colorings of Shallow Discs,
    In Proc. of the 22nd ACM Symposium on Computational Geometry, ( SoCG 2006)
    Presentation

  • B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, C. Seara, S. Smorodinsky
    Small Weak Epsilon Nets,
    In proc of 17th Canadian Conference on Computational Geometry ( CCCG ), August 10-12, 2005 University of Windsor. 2005.

  • S. Smorodinsky,
    On The Chromatic Number of Some Geometric Hypergraphs,
    In Proc. of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006).
    Presentation

  • A. Bar-Noy, P. Cheilaris, S. Olonetsky and S. Smorodinsky,
    Online conflict-free colorings for hypergraphs,
    In Proc. of the 34th International Colloquium on Automata, Languages and Programming , ( ICALP 2007).

  • N. Alon, H. Kaplan, G. Nivasch, M. Sharir and S. Smorodinsky,
    Weak epsilon-nets and interval chains,
    In Proc. of 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008).

  • G. Aloupis, J. Cardinal, S. Collette, S. Langerman and S. Smorodinsky,
    Coloring Geometric Range Spaces,
    In Proc. of 8th Latin American Theoretical Informatics, (LATIN), Lecture Notes in Computer Science, Springer Volume 4957, 2008.

  • S. Smorodinsky, M. Sulovsky and U. Wagner
    On lower center regions and balls containing many points,
    In Proc. of 14th Annual International Computing and Combinatorics Conference , (COCOON 2008).

  • G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, S. Smorodinsky, P. Taslakian
    Colorful Strips,
    In Proc. of 9th Latin American Theoretical Informatics, (LATIN 2010),

  • S. Smorodinsky and Y. Yuditsky
    Polychromatic coloring for half-planes,
    In Proc. 12'th Scandinavian Symposium and Workshops on Algorithm Theory , (SWAT 2010), to appear.

  • E. Horev, R. Krakovski and S. Smorodinsky,
    Conflict-Free Coloring Made Stronger,
    In Proc. 12'th Scandinavian Symposium and Workshops on Algorithm Theory , (SWAT 2010), to appear.

  • P. Cheilaris, S. Smorodinsky and M. Sulovsky,
    The potential to improve the choice: list conflict-free coloring for geometric hypergraphs,
    In Proc. of the 27th ACM Symposium on Computational Geometry (SoCG), 2011, to appear.

  • G. Even and S. Smorodinsky,
    Hitting Sets Online and Vertex Ranking,
    In Proc. of the 19th Annual European Symposium on Algorithms (ESA ), 2011, to appear.