Teaching 2012-2013

Seminar: Topics in discrete geometry (Spring semester)

Publications

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.