Shakhar Smorodinsky

110 papers A* 19A 2B 7C 1Misc 1Journal 68Unranked 11
YearRankTypeTitle / Venue / Authors
2026 A* conf
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets.
SODA
Noga Alon, Shakhar Smorodinsky
2025 J jnl
A simple proof of a (p,2)-theorem for non-piercing regions.
CoRR
Chaya Keller, Shakhar Smorodinsky
2025 J jnl
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets.
CoRR
Noga Alon, Shakhar Smorodinsky
2025 J jnl
On Separating Path and Tree Systems in Graphs.
Discret. Math. Theor. Comput. Sci.
Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Babak Miraftab, Saeed Odak, Michiel Smid, Shakhar Smorodinsky, Yelena Yuditsky
2025 A* conf
On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects.
SoCG
Timothy M. Chan, Chaya Keller, Shakhar Smorodinsky
2025 A* conf
Polychromatic Coloring of Tuples in Hypergraphs.
SoCG
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Milos Stojakovic
2025 J jnl
Polychromatic Coloring of Tuples in Hypergraphs.
CoRR
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Milos Stojakovic
2025 A* conf
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs.
SoCG
Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Tóth
2025 J jnl
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs.
CoRR
Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Tóth
2024 J jnl
A survey of Zarankiewicz problem in geometry.
CoRR
Shakhar Smorodinsky
2024 J jnl
Conflict-Free Colouring of Subsets.
Discret. Comput. Geom.
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
2024 J jnl
On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects.
CoRR
Timothy M. Chan, Chaya Keller, Shakhar Smorodinsky
2024 A* conf
Zarankiewicz's Problem via ε-t-Nets.
SoCG
Chaya Keller, Shakhar Smorodinsky
2023 J jnl
On Separating Path and Tree Systems in Graphs.
CoRR
Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Babak Miraftab, Saeed Odak, Michiel Smid, Shakhar Smorodinsky, Yelena Yuditsky
2023 J jnl
Zarankiewicz's problem via ε-t-nets.
CoRR
Chaya Keller, Shakhar Smorodinsky
2022 A* conf
A Solution to Ringel's Circle Problem.
SoCG
James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
2022 J jnl
Conflict-Free Colouring of Subsets.
CoRR
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
2022 J jnl
On Multicolor Ramsey Numbers and Subset Coloring of Hypergraphs.
SIAM J. Discret. Math.
Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
2022 J jnl
The ε-t-Net Problem.
Discret. Comput. Geom.
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
2021 J jnl
A solution to Ringel's circle problem.
CoRR
James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
2021 J jnl
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs.
Discret. Comput. Geom.
A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, Shakhar Smorodinsky
2021 J jnl
Conflict-Free Coloring of String Graphs.
Discret. Comput. Geom.
Chaya Keller, Alexandre Rok, Shakhar Smorodinsky
2021 J jnl
On the VC-dimension of half-spaces with respect to convex sets.
Discret. Math. Theor. Comput. Sci.
Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky
2020 A* conf
A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane.
SODA
Chaya Keller, Shakhar Smorodinsky
2020 J jnl
Balanced line separators of unit disk graphs.
Comput. Geom.
Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, Shakhar Smorodinsky
2020 J jnl
Conflict-Free Coloring of Intersection Graphs of Geometric Objects.
Discret. Comput. Geom.
Chaya Keller, Shakhar Smorodinsky
2020 J jnl
From a (p, 2)-Theorem to a Tight (p, q)-Theorem.
Discret. Comput. Geom.
Chaya Keller, Shakhar Smorodinsky
2020 A* conf
The ε-t-Net Problem.
SoCG
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
2020 J jnl
The ε-t-Net Problem.
CoRR
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
2019 J jnl
On the VC-dimension of convex sets and half-spaces.
CoRR
Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky
2018 J jnl
A new lower bound on Hadwiger-Debrunner numbers in the plane.
CoRR
Chaya Keller, Shakhar Smorodinsky
2018 A* conf
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs.
SoCG
A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel H. M. Smid, Shakhar Smorodinsky
2018 A* conf
Conflict-Free Coloring of Intersection Graphs of Geometric Objects.
SODA
Chaya Keller, Shakhar Smorodinsky
2018 J jnl
Distinct distances between points and lines.
Comput. Geom.
Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu, Frank de Zeeuw
2018 A* conf
From a (p, 2)-Theorem to a Tight (p, q)-Theorem.
SoCG
Chaya Keller, Shakhar Smorodinsky
2018 J jnl
On piercing numbers of families satisfying the (
Comput. Geom.
Chaya Keller, Shakhar Smorodinsky
2018 J jnl
On the Union Complexity of Families of Axis-Parallel Rectangles with a Low Packing Number.
Electron. J. Comb.
Chaya Keller, Shakhar Smorodinsky
2017 B conf
Balanced Line Separators of Unit Disk Graphs.
WADS
Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, Shakhar Smorodinsky
2017 J jnl
Balanced Line Separators of Unit Disk Graphs.
CoRR
Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, Shakhar Smorodinsky
2017 J jnl
Bounding a global red-blue proportion using local conditions.
CoRR
Márton Naszódi, Leonardo Martínez-Sandoval, Shakhar Smorodinsky
2017 A* conf
On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers.
SODA
Chaya Keller, Shakhar Smorodinsky, Gábor Tardos
2017 J jnl
On interference among moving sensors and related problems.
J. Comput. Geom.
Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky
2017 J jnl
On the union complexity of families of axis-parallel rectangles with a low packing number.
CoRR
Chaya Keller, Shakhar Smorodinsky
2017 J jnl
The Price of Anarchy in Hypergraph Coloring Games.
CoRR
Rann Smorodinsky, Shakhar Smorodinsky
2016 A conf
On Interference Among Moving Sensors and Related Problems.
ESA
Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky
2016 J jnl
On Vertex Rankings of Graphs and its Relatives.
CoRR
Ilan Karpas, Ofer Neiman, Shakhar Smorodinsky
2016 A* conf
Weak 1/r-Nets for Moving Points.
SoCG
Alexandre Rok, Shakhar Smorodinsky
2015 J jnl
A short proof of the first selection lemma and weak $\frac{1}{r}$-nets for moving points.
CoRR
Alexandre Rok, Shakhar Smorodinsky
2015 J jnl
On Kinetic Range Spaces and their Applications.
CoRR
Jean-Lou De Carufel, Matya Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky
2015 J jnl
On vertex rankings of graphs and its relatives.
Discret. Math.
Ilan Karpas, Ofer Neiman, Shakhar Smorodinsky
2014 J jnl
Epsilon-Nets for Halfspaces Revisited.
CoRR
Sariel Har-Peled, Haim Kaplan, Micha Sharir, Shakhar Smorodinsky
2014 J jnl
Hitting sets online and unique-max coloring.
Discret. Appl. Math.
Guy Even, Shakhar Smorodinsky
2014 J jnl
On totally positive matrices and geometric incidences.
J. Comb. Theory A
Miriam Farber, Saurabh Ray, Shakhar Smorodinsky
2014 J jnl
Strong Conflict-Free Coloring for Intervals.
Algorithmica
Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno, Shakhar Smorodinsky
2012 J jnl
Conflict-free coloring with respect to a subset of intervals
CoRR
Panagiotis Cheilaris, Shakhar Smorodinsky
2012 J jnl
Hitting Sets Online and Unique-Max Coloring
CoRR
Guy Even, Shakhar Smorodinsky
2012 J jnl
Polychromatic coloring for half-planes.
J. Comb. Theory A
Shakhar Smorodinsky, Yelena Yuditsky
2012 B conf
Strong Conflict-Free Coloring for Intervals.
ISAAC
Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno, Shakhar Smorodinsky
2011 J jnl
Colorful Strips.
Graphs Comb.
Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, Perouz Taslakian
2011 A conf
Hitting Sets Online and Vertex Ranking.
ESA
Guy Even, Shakhar Smorodinsky
2011 — conf
The potential to improve the choice: list conflict-free coloring for geometric hypergraphs.
SCG
Panagiotis Cheilaris, Shakhar Smorodinsky, Marek Sulovský
2010 J jnl
Choosability in geometric hypergraphs
CoRR
Panagiotis Cheilaris, Shakhar Smorodinsky
2010 B conf
Colorful Strips.
LATIN
Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, Perouz Taslakian
2010 J jnl
Conflict-Free Coloring Made Stronger
CoRR
Elad Horev, Roi Krakovski, Shakhar Smorodinsky
2010 — conf
Conflict-Free Coloring Made Stronger.
SWAT
Elad Horev, Roi Krakovski, Shakhar Smorodinsky
2010 J jnl
Conflict-Free Coloring and its Applications
CoRR
Shakhar Smorodinsky
2010 J jnl
Online Conflict-Free Colouring for Hypergraphs.
Comb. Probab. Comput.
Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky
2010 — conf
Polychromatic Coloring for Half-Planes.
SWAT
Shakhar Smorodinsky, Yelena Yuditsky
2009 J jnl
Colorful Strips
CoRR
Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, Perouz Taslakian
2009 J jnl
Coloring Geometric Range Spaces.
Discret. Comput. Geom.
Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, Shakhar Smorodinsky
2009 J jnl
Compatible geometric matchings.
Comput. Geom.
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
2009 J jnl
Small weak epsilon-nets.
Comput. Geom.
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, David Rappaport, Carlos Seara, Shakhar Smorodinsky
2008 J jnl
A note on the online First-Fit algorithm for coloring k.
Inf. Process. Lett.
Shakhar Smorodinsky
2008 B conf
Coloring Geometric Range Spaces.
LATIN
Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, Shakhar Smorodinsky
2008 J jnl
Compatible Geometric Matchings.
Electron. Notes Discret. Math.
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
2008 J jnl
Conflict-Free colorings of Shallow Discs.
Int. J. Comput. Geom. Appl.
Noga Alon, Shakhar Smorodinsky
2008 J jnl
Deterministic conflict-free coloring for intervals: From offline to online.
ACM Trans. Algorithms
Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky
2008 Misc conf
On Center Regions and Balls Containing Many Points.
COCOON
Shakhar Smorodinsky, Marek Sulovský, Uli Wagner
2008 A* conf
Weak ε-nets and interval chains.
SODA
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
2008 J jnl
Weak ε-nets and interval chains.
J. ACM
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
2007 J jnl
Convexity in Topological Affine Planes.
Discret. Comput. Geom.
Raghavan Dhandapani, Jacob E. Goodman, Andreas F. Holmsen, Richard Pollack, Shakhar Smorodinsky
2007 J jnl
On The Chromatic Number of Geometric Hypergraphs.
SIAM J. Discret. Math.
Shakhar Smorodinsky
2007 J jnl
Online Conflict-Free Coloring for Intervals.
SIAM J. Comput.
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl
2007 A* conf
Online Conflict-Free Colorings for Hypergraphs.
ICALP
Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky
2007 B conf
Weakening the online adversary just enough to get optimal conflict-free colorings for intervals.
SPAA
Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky
2006 B conf
Conflict-free coloring for intervals: from offline to online.
SPAA
Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky
2006 — conf
Conflict-free colorings of shallow discs.
SCG
Noga Alon, Shakhar Smorodinsky
2006 A* conf
On the chromatic number of some geometric hypergraphs.
SODA
Shakhar Smorodinsky
2006 J jnl
k-Sets in Four Dimensions.
Discret. Comput. Geom.
Jirí Matousek, Micha Sharir, Shakhar Smorodinsky, Uli Wagner
2005 J jnl
Conflict-Free Coloring of Points and Simple Regions in the Plane.
Discret. Comput. Geom.
Sariel Har-Peled, Shakhar Smorodinsky
2005 J jnl
Geometric Permutations Induced by Line Transversals through a Fixed Point.
Discret. Comput. Geom.
Boris Aronov, Shakhar Smorodinsky
2005 A* conf
On geometric permutations induced by lines transversal through a fixed point.
SODA
Boris Aronov, Shakhar Smorodinsky
2005 A* conf
Online conflict-free coloring for intervals.
SODA
Amos Fiat, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl
2005 — conf
Small weak epsilon nets.
CCCG
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, David Rappaport, Shakhar Smorodinsky, Carlos Seara
2004 J jnl
Lenses in arrangements of pseudo-circles and their applications.
J. ACM
Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
2004 — conf
On locally Delaunay geometric graphs.
SCG
Rom Pinchasi, Shakhar Smorodinsky
2004 J jnl
Selecting Points that are Heavily Covered by Pseudo-Circles, Spheres or Rectangles.
Comb. Probab. Comput.
Shakhar Smorodinsky, Micha Sharir
2003 — —
Combinatorial problems in computational geometry
Shakhar Smorodinsky
2003 J jnl
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
SIAM J. Comput.
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
2003 B conf
Extremal Configurations and Levels in Pseudoline Arrangements.
WADS
Micha Sharir, Shakhar Smorodinsky
2003 — conf
On conflict-free coloring of points and simple regions in the plane.
SCG
Sariel Har-Peled, Shakhar Smorodinsky
2003 J jnl
On neighbors in geometric permutations.
Discret. Math.
Micha Sharir, Shakhar Smorodinsky
2002 A* conf
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
FOCS
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
2002 — conf
Lenses in arrangements of pseudo-circles and their applications.
SCG
Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
2002 — conf
On Neighbors in Geometric Permutations.
SWAT
Micha Sharir, Shakhar Smorodinsky
2001 J jnl
An Improved Bound for
Discret. Comput. Geom.
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
2000 C conf
An Improved Bound for k-Sets in Three Dimensions.
EuroCG
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
2000 — conf
An improved bound for
SCG
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
2000 J jnl
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in Rd.
Discret. Comput. Geom.
Shakhar Smorodinsky, Joseph S. B. Mitchell, Micha Sharir
1999 — conf
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls inR
SCG
Shakhar Smorodinsky, Joseph S. B. Mitchell, Micha Sharir