Noga Alon, Haim Kaplan, Gabriel Nivasch, Shakhar Smorodinsky
Abstract. We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1-nets of size O(rα(r)), where...
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, Carlos Seara, Shakhar Smorodinsky
Given a set P of points in the plane, a set of points Q is a weak ε-net with respect to a family of sets S (e.g., rectangles, disks, or convex sets) if every set of S containing ε|P | points...
1 Introduction Small Weak Epsilon Nets (2008)
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, Shakhar Smorodinsky, Carlos Seara
Let P be a set of n points in R 2. A point q (not
Vol. 21, No. 3, pp. 676–687 ON THE CHROMATIC NUMBER OF GEOMETRIC HYPERGRAPHS ∗ (2008)
Abstract. A finite family R of simple Jordan regions in the plane defines a hypergraph H = H(R) where the vertex set of H is R and the hyperedges are all subsets S ⊂Rfor which there is a point p...
Abstract. We provide a framework for online conflict-free coloring (CFcoloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any...
ABSTRACT On Locally Delaunay Geometric Graphs (2008)
Rom Pinchasi, Shakhar Smorodinsky
A geometric graph is a simple graph G = (V, E) with an embedding of the set V in the plane such that the points that represent V are in general position. A geometric graph is said to be k-locally...
Amotz Bar-noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky
conflict-free coloring for geometric hypergraphs
Prof Emo Welzl, Eth Zürich, Bernd Gärtner, Jochen Giesen, Matthias John, Michael Hoffmann, ...
citizen of Japan submitted to
Abstract Online Conflict-Free Coloring for Intervals (2008)
Amos Fiat, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
ported by the Austrian FWF Joint Research Project ’Industrial Geometry ’ S9205-N12. (2008)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Sariel Har-peled, Shakhar Smorodinsky
In this paper, we study coloring problems related to frequency setting, the problems are of the following two types: CF-coloring of regions: Given a finite family
Shakhar Smorodinsky, Micha Sharir
In this paper we prove several point-selection theorems concerning objects \spanned " by a nite set of points. For example, we show that for any set P of n points in IR 2 and any set C of m...
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call Minimum Con ict-Free Coloring (Min-CF-Coloring). In its general form, the...
Extremal Congurations and Levels in Pseudoline Arrangements (2007)
Micha Sharir, Shakhar Smorodinsky
This paper studies a variety of problems involving certain types of extreme congurations in arrangements of (x-monotone) pseudo-lines. For example, we obtain a very simple proof of the bound O(nk
Micha Sharir, Shakhar Smorodinsky
We introduce a new notion of `neighbors ' in geometric permutations. We conjecture that the maximum number of neighbors in a set of n pairwise disjoint convex bodies in R
On Polytopes Spanned by Sets of Points in IR 3 (2007)
Micha Sharir, Shakhar Smorodinsky
(a) We prove that the total complexity of k polygons in arrangement of n lines with distinct vertices is (nk 1=2). If the polygons do not overlap in edges then we show that their complexity is (nk
Shakhar Smorodinsky, Micha Sharir
In this paper we prove several point-selection theorems concerning objects \spanned " by a nite set of points. In the planar case we show the following: (i) For any set P of n points in IR
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call Minimum Con ict-Free Coloring (Min-CF-Coloring). In its general form, the...
Shakhar Smorodinsky, Micha Sharir
We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IR d, is \Theta(n d\Gamma1
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Online conflict-free coloring for intervals. (2006)
Fiat, Amos, Matoušek, Jiří, Mossel, Elchanan, Pach, János, Sharir, Micha, Smorodinsky, Shakhar, ...
Conflict-free colorings of shallow discs (2006)
Noga Alon, Shakhar Smorodinsky
We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log 3 k) colors so that for each point p in the union of all discs there is at...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online conflict-free colorings for hypergraphs, manuscript (2006)
Amotz Bar-noy, Panagiotis Cheilaris, Svetalana Olonetsky, Shakhar Smorodinsky
(i) We provide a framework for online conflict-free coloring (CF-coloring) any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any k-degenerate...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Ji Rí, Matou Sek, ...
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
Online conflict-free colorings for hypergraphs, manuscript (2006)
Amotz Bar-noy, Panagiotis Cheilaris, Svetalana Olonetsky, Shakhar Smorodinsky
We provide a framework for online conflict-free coloring (CF-coloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any k-degenerate...
1.1 History and Mission (2005)
Shakhar Smorodinsky, Dina Schneidman, Eran Leiserowitz, Eyal Molad, ...
performed at Tel-Aviv University and presented at the most prestigious international computer science conferences and workshops. The Deutsch Institute believes that enabling graduate students to...
Conflict-free coloring of points and simple regions in the plane (2005)
Sariel Har-peled, Shakhar Smorodinsky
We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A...
Conflict-free coloring of points and simple regions in the plane (2005)
Sariel Har-peled, Shakhar Smorodinsky
We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A...
Lenses in arrangements of pseudo-circles and their applications (2004)
Pankaj K. Agarwal, Micha Sharir, Eran Nevo, Shakhar Smorodinsky
Abstract. A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Lenses in arrangements of pseudo-circles and their applications (2004)
Pankaj K. Agarwal, Eran Nevo, Janos Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...
k-sets in four dimensions (2004)
Micha Sharir, Shakhar Smorodinsky, Uli Wagner
We show, with an elementary proof, that the number of halving sim-plices in a set of n points in R 4 in general position is O(n 4−2/45). This improves the previous bound of O(n4−1/134). Our main...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Lenses in arrangements of pseudo-circles and their applications (2002)
Pach, János, Agarwal, Pankaj K., Nevo, E., Pinchasi, Rom, Sharir, Micha, Smorodinsky, Shakhar
Lenses in arrangements of pseudocircles and their applications (2002)
Eran Nevo, J Anos Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
k A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...
Lenses in Arrangements of Pseudo-circles and Their Applications£ (2002)
Pankaj K. Agarwalý, Eran Nevoþ, János Pachü, Rom Pinchasiß, Micha Sharir, Shakhar Smorodinsky
A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...
On generalized geometric graphs and pseudolines (2001)
Micha Sharir, Shakhar Smorodinsky
This paper generalizes, extends and simplies many results involving geometric graphs on planar point sets, in the context of pseudoline arrangements. Many of the problems studied here have been the...
On generalized geometric graphs and pseudolines (2001)
Micha Sharir, Shakhar Smorodinsky
(a) Using a duality transformation on pseudolines, established recently by Agarwal and Sharir [4], we show that any graph G induced by a set of vertices of an arrangement of a nite set of...
An improved bound for k-sets in three dimensions (2000)
Micha Sharir, Shakhar Smorodinsky
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk
Sets In Three, Micha Sharir, Shakhar Smorodinsky
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk 3=2 ). This improves substantially the previous best known upper bound of O(nk 5=3 ) (see [7] and [1]). 1...
An Improved Bound for k-Sets in Three Dimensions (2000)
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk 3=2 ). This improves substantially the previous best known upper bound of O(nk 5=3 ) (see [7] and [1]). 1...
On k-Sets in Three Dimensions (1999)
Shakhar Smorodinsky, Micha Sharir
We prove that the maximum number of k-sets in a set S of n points in IR 3 , for any fixed k, is O(n 8=3 ). This bound is already known [6], but we believe that our proof is simpler. 1 Introduction...
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R^d (1999)
Shakhar Smorodinsky, Micha Sharir
We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IR d , is \Theta(n d\Gamma1 ). This improves substantially the...
Geometric Permutations and Common Transversals (1998)
Shakhar Smorodinsky, Common Transversals
Contents 1 Introduction 2 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 k-Transversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R^d (1998)
Shakhar Smorodinsky, Micha Sharir
(i) We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IR d , is \Theta(n d\Gamma1 ). This improves substantially...