Shakhar Smorodinsky

According to our database, Shakhar Smorodinsky authored at least 76 papers between 1999 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

A simple proof of a (p,2)-theorem for non-piercing regions.

Chaya Keller, Shakhar Smorodinsky

CoRR, July, 2025

Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets.

Noga Alon, Shakhar Smorodinsky

CoRR, June, 2025

On Separating Path and Tree Systems in Graphs.

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Babak Miraftab, Saeed Odak, Michiel Smid, Shakhar Smorodinsky, Yelena Yuditsky

Discret. Math. Theor. Comput. Sci., 2025

On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects.

Timothy M. Chan, Chaya Keller, Shakhar Smorodinsky

Proceedings of the 41st International Symposium on Computational Geometry, 2025

Polychromatic Coloring of Tuples in Hypergraphs.

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Milos Stojakovic

Proceedings of the 41st International Symposium on Computational Geometry, 2025

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs.

Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Tóth

Proceedings of the 41st International Symposium on Computational Geometry, 2025

2024

Conflict-Free Colouring of Subsets.

Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky

Discret. Comput. Geom., September, 2024

A survey of Zarankiewicz problem in geometry.

Shakhar Smorodinsky

CoRR, 2024

Zarankiewicz's Problem via ε-t-Nets.

Chaya Keller, Shakhar Smorodinsky

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2022

On Multicolor Ramsey Numbers and Subset Coloring of Hypergraphs.

Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky

SIAM J. Discret. Math., September, 2022

A Solution to Ringel's Circle Problem.

James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

On the VC-dimension of half-spaces with respect to convex sets.

Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky

Discret. Math. Theor. Comput. Sci., 2021

Conflict-Free Coloring of String Graphs.

Chaya Keller, Alexandre Rok, Shakhar Smorodinsky

Discret. Comput. Geom., 2021

2020

A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane.

Chaya Keller, Shakhar Smorodinsky

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

The ε-t-Net Problem.

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky

Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019

On the VC-dimension of convex sets and half-spaces.

Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky

CoRR, 2019

2018

Distinct distances between points and lines.

Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu, Frank de Zeeuw

Comput. Geom., 2018

On piercing numbers of families satisfying the (<i>p</i>, <i>q</i>)_<i>r</i> property.

Chaya Keller, Shakhar Smorodinsky

Comput. Geom., 2018

On the Union Complexity of Families of Axis-Parallel Rectangles with a Low Packing Number.

Chaya Keller, Shakhar Smorodinsky

Electron. J. Comb., 2018

Conflict-Free Coloring of Intersection Graphs of Geometric Objects.

Chaya Keller, Shakhar Smorodinsky

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

From a (p, 2)-Theorem to a Tight (p, q)-Theorem.

Chaya Keller, Shakhar Smorodinsky

Proceedings of the 34th International Symposium on Computational Geometry, 2018

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs.

A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel H. M. Smid, Shakhar Smorodinsky

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

The Price of Anarchy in Hypergraph Coloring Games.

Rann Smorodinsky, Shakhar Smorodinsky

CoRR, 2017

Bounding a global red-blue proportion using local conditions.

Márton Naszódi, Leonardo Martínez-Sandoval, Shakhar Smorodinsky

CoRR, 2017

Balanced Line Separators of Unit Disk Graphs.

Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, Shakhar Smorodinsky

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers.

Chaya Keller, Shakhar Smorodinsky, Gábor Tardos

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

On Interference Among Moving Sensors and Related Problems.

Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Weak 1/r-Nets for Moving Points.

Alexandre Rok, Shakhar Smorodinsky

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

On vertex rankings of graphs and its relatives.

Ilan Karpas, Ofer Neiman, Shakhar Smorodinsky

Discret. Math., 2015

A short proof of the first selection lemma and weak $\frac{1}{r}$-nets for moving points.

Alexandre Rok, Shakhar Smorodinsky

CoRR, 2015

On Kinetic Range Spaces and their Applications.

Jean-Lou De Carufel, Matya Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky

CoRR, 2015

2014

On totally positive matrices and geometric incidences.

Miriam Farber, Saurabh Ray, Shakhar Smorodinsky

J. Comb. Theory A, 2014

Hitting sets online and unique-max coloring.

Guy Even, Shakhar Smorodinsky

Discret. Appl. Math., 2014

Epsilon-Nets for Halfspaces Revisited.

Sariel Har-Peled, Haim Kaplan, Micha Sharir, Shakhar Smorodinsky

CoRR, 2014

2012

Conflict-free coloring with respect to a subset of intervals

Panagiotis Cheilaris, Shakhar Smorodinsky

CoRR, 2012

Strong Conflict-Free Coloring for Intervals.

Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno, Shakhar Smorodinsky

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011

Hitting Sets Online and Vertex Ranking.

Guy Even, Shakhar Smorodinsky

Proceedings of the Algorithms - ESA 2011, 2011

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs.

Panagiotis Cheilaris, Shakhar Smorodinsky, Marek Sulovský

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Online Conflict-Free Colouring for Hypergraphs.

Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky

Comb. Probab. Comput., 2010

Choosability in geometric hypergraphs

Panagiotis Cheilaris, Shakhar Smorodinsky

CoRR, 2010

Conflict-Free Coloring and its Applications

Shakhar Smorodinsky

CoRR, 2010

Polychromatic Coloring for Half-Planes.

Shakhar Smorodinsky, Yelena Yuditsky

Proceedings of the Algorithm Theory, 2010

Conflict-Free Coloring Made Stronger.

Elad Horev, Roi Krakovski, Shakhar Smorodinsky

Proceedings of the Algorithm Theory, 2010

Colorful Strips.

Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, Perouz Taslakian

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2008

Deterministic conflict-free coloring for intervals: From offline to online.

Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky

ACM Trans. Algorithms, 2008

A note on the online First-Fit algorithm for coloring k.

Shakhar Smorodinsky

Inf. Process. Lett., 2008

Compatible Geometric Matchings.

Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García Olaverri, Clemens Huemer, Ferran Hurtado, Mikio Kano, Alberto Márquez, David Rappaport, Shakhar Smorodinsky, Diane L. Souvaine, Jorge Urrutia, David R. Wood

Electron. Notes Discret. Math., 2008

Weak ε-nets and interval chains.

Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Coloring Geometric Range Spaces.

Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, Shakhar Smorodinsky

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

On Center Regions and Balls Containing Many Points.

Shakhar Smorodinsky, Marek Sulovský, Uli Wagner

Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

2007

On The Chromatic Number of Geometric Hypergraphs.

Shakhar Smorodinsky

SIAM J. Discret. Math., 2007

Online Conflict-Free Coloring for Intervals.

Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl

SIAM J. Comput., 2007

Convexity in Topological Affine Planes.

Raghavan Dhandapani, Jacob E. Goodman, Andreas F. Holmsen, Richard Pollack, Shakhar Smorodinsky

Discret. Comput. Geom., 2007

Weakening the online adversary just enough to get optimal conflict-free colorings for intervals.

Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky

Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Online Conflict-Free Colorings for Hypergraphs.

Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

k-Sets in Four Dimensions.

Jirí Matousek, Micha Sharir, Shakhar Smorodinsky, Uli Wagner

Discret. Comput. Geom., 2006

Conflict-free coloring for intervals: from offline to online.

Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

On the chromatic number of some geometric hypergraphs.

Shakhar Smorodinsky

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Conflict-free colorings of shallow discs.

Noga Alon, Shakhar Smorodinsky

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Geometric Permutations Induced by Line Transversals through a Fixed Point.

Boris Aronov, Shakhar Smorodinsky

Discret. Comput. Geom., 2005

Online conflict-free coloring for intervals.

Amos Fiat, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On geometric permutations induced by lines transversal through a fixed point.

Boris Aronov, Shakhar Smorodinsky

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Small weak epsilon nets.

Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, David Rappaport, Shakhar Smorodinsky, Carlos Seara

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004

Lenses in arrangements of pseudo-circles and their applications.

Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky

J. ACM, 2004

Selecting Points that are Heavily Covered by Pseudo-Circles, Spheres or Rectangles.

Shakhar Smorodinsky, Micha Sharir

Comb. Probab. Comput., 2004

On locally Delaunay geometric graphs.

Rom Pinchasi, Shakhar Smorodinsky

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003

Combinatorial problems in computational geometry

Shakhar Smorodinsky

PhD thesis, 2003

Extremal Configurations and Levels in Pseudoline Arrangements.

Micha Sharir, Shakhar Smorodinsky

Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

On conflict-free coloring of points and simple regions in the plane.

Sariel Har-Peled, Shakhar Smorodinsky

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002

On Neighbors in Geometric Permutations.

Micha Sharir, Shakhar Smorodinsky

Proceedings of the Algorithm Theory, 2002

Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.

Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Lenses in arrangements of pseudo-circles and their applications.

Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

2000

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in Rd.

Shakhar Smorodinsky, Joseph S. B. Mitchell, Micha Sharir

Discret. Comput. Geom., 2000

An Improved Bound for k-Sets in Three Dimensions.

Micha Sharir, Shakhar Smorodinsky, Gábor Tardos

EuroCG, 2000

An improved bound for <i>k</i>-sets in three dimensions.

Micha Sharir, Shakhar Smorodinsky, Gábor Tardos

Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls inR^d.

Shakhar Smorodinsky, Joseph S. B. Mitchell, Micha Sharir

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999