On a Geometric Generalization of the Upper Bound Theorem (2010)
We prove an upper bound, tight up to a factor of 2, for the number of vertices of level at most ℓ in an arrangement of n halfspaces in R d, for arbitrary n and d (in particular, the dimension d is...
New Results in Tropical Discrete Geometry (2009)
Martin Jaggi, Gabriel Katz, Uli Wagner
Following the recent work of Develin and Sturmfels and others (see, e.g., [10, 16, 2, 11]), we investigate discrete geometric questions over the tropical semiring (R, min, +). Specifically, we obtain...
Hardness of embedding simplicial complexes in d Jiˇrí Matouˇsek a,b,c Martin Tancera,b,c c, d (2009)
Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into d? Known results easily...
Hardness of embedding simplicial complexes in $\R^d$ (2008)
Matoušek, Jiří, Tancer, Martin, Wagner, Uli
Let EMBED(k,d) be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into R^d? Known results easily...
Abstract On the Rectilinear Crossing Number of Complete Graphs (2008)
The rectilinear crossing number cr(G) of a graph G is the minimal number of crossings in any straight-edge drawing of G in the Euclidean plane. We refrain here from attempting to give an overview of...
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...
On the Clique Problem in Intersection Graphs of Ellipses and Triangles (2008)
Abstract. Intersection graphs of disks and of line segments, respectively, have been well studied, because of both, practical applications and theoretically interesting properties of these graphs....
On the Embeddability of Skeleta of Spheres (2008)
We consider a generalization of the van Kampen-Flores Theorem and relate it to the long-standing g-conjecture for simplicial spheres. 1 Introduction and results A well-known result by van Kampen [26,...
On the Embeddability of Skeleta of Spheres (2008)
We consider a generalization of the van Kampen-Flores Theorem and relate it to the long-standing g-conjecture for simplicial spheres. 1 Introduction and results A well-known result by van Kampen [26,...
A corner cut in dimension d is a nite subset of N d 0 that can be separated from its complement in N d
On the Embeddability of Skeleta of Spheres (2007)
We consider a generalization of the van Kampen-Flores Theorem and relate it to the long-standing $g$-conjecture for simplicial spheres.
Transforming spanning trees: A lower bound (2007)
Kevin Buchin, Andreas Razen, Takeaki Uno, Uli Wagner
For a planar point set we consider the graph of crossing-free straight-line spanning trees where two spanning trees are adjacent in the graph if their union is crossing-free. An upper bound on the...
Online conflict-free coloring for intervals. (2006)
Fiat, Amos, Matoušek, Jiří, Mossel, Elchanan, Pach, János, Sharir, Micha, Smorodinsky, Shakhar, ...
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 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 (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...
Convex quadrilaterals and k-sets (2004)
László Lovász, Katalin Vesztergombi, Uli Wagner, Emo Welzl
We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane – or in other words, the rectilinear crossing number of the complete graph Kn –...
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...
Convex quadrilaterals and k-sets (2004)
László Lovász, Katalin Vesztergombi, Uli Wagner, Emo Welzl
We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane – or in other words, the rectilinear crossing number of the complete graph Kn –...
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...
appeared in Contemporary Mathematics 342 (2004) 139-148. Convex Quadrilaterals and k-Sets (2004)
László Lovász, Katalin Vesztergombi, Uli Wagner, Emo Welzl
We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane – or in other words, the rectilinear crossing number of the complete graph Kn –...
On k-sets in four dimension (2004)
Micha Sharir, Shakhar Smorodinsky, Uli Wagner
We show, with an elementary proof, that the number of halving simplices 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...
On the rectilinear crossing number of complete graphs (2003)
We prove a lower bound of 0:3288 n
New constructions of weak epsilon-nets (2003)
A finite set N ⊂ R d is a weak ε-net for an n-point set X ⊂ R d (with respect to convex sets) if N intersects every convex set K with |K ∩ X | ≥ εn. We give an alternative, and arguably...
Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (2003)
We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some Euclidean space d. We assume that M is known to us only through a finite sample P...
Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (2003)
We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some Euclidean space Êd. We assume that M is known to us only through a finite sample P...
Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (2003)
We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some Euclidean space d. We assume that M is known to us only through a finite sample P...
On the number of corner cuts (2002)
A corner cut in dimension d is a finite subset of N d 0 that can be separated from its complement in N d 0 by an affine hyperplane disjoint from N d 0. Corner cuts were first investigated by Onn and...
On the number of corner cuts (2002)
A corner cut in dimension d is a finite subset of N d 0 that can be separated from its complement in N d 0 by an affine hyperplane disjoint from N d 0. Corner cuts were first investigated by Onn and...
A continuous analogue of the upper bound theorem (2001)
For an absolutely continuous probability measure on R
A continuous analogue of the upper bound theorem (2001)
For an absolutely continuous probability measure µ onÊd and a nonnegative integer k, let ˜sk(µ,0) denote the probability that the convex hull of k+d+1 random points which are i.i.d. according to...
A continuous analogue of the upper bound theorem (2001)
For an absolutely continuous probability measure µ on d and a nonnegative integer k, let ˜sk(µ, 0) denote the probability that the convex hull of k+d+1 random points which are i.i.d. according...
A continuous analogue of the upper bound theorem (2001)
d For an absolutely continuous probability measure µ on and a nonnegative integer k, let ˜sk(µ, 0) denote the probability that the convex hull of k+d+1 random points which are i.i.d. according to...