Diss. ETH No. 18603 Extremal Colorings and Extremal Satisfiability (2010)
Prof Dr, Emo Welzl, Prof Dr, Tibor Szabó
accepted on the recommendation of
appeared in Algorithmica 16 (1996) 498-516. A Subexponential Bound for Linear Programming ∗† (2010)
We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected min{O(d 2 2 d n),e 2 d ln(n / d)+O ( d+ln n)} time in the unit cost model (where...
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem (2010)
A recent result by Pach and Pinchasi on so-called balanced lines of a finite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the...
Entering and leaving j-facets (2010)
Let S be a set of n points in d-space, no i + 1 points on a common (i − 1)-flat for 1 ≤ i ≤ d. An oriented (d − 1)-simplex spanned by d points in S is called j-facet of S, if there are...
We show that a set of n points in the plane has at most O(10.05 n) perfect matchings with crossing-free straight-line embedding. The expected number of perfect crossingfree matchings of a set of n...
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...
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 –...
In between k-Sets, j-Facets, and i-Faces: (i,j)-Partitions ∗ (2002)
Artur Andrzejak, Emo Welzl, Inst Theoretische Informatik
Let S be a finite set of points in general position in R d. We call a pair (A,B) of subsets of S an (i,j)-partition of S, if |A | = i, |B | = j and there is an oriented hyperplane h with S ∩h = A...
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...
Bernd Gärtner, Falk Tschirschnitz, Emo Welzl, József Solymosi, Pavel Valtr
We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the Random-Edge simplex algorithm on simple polytopes with n facets in...
accepted on the recommendation of (1982)
Andreas Razen, Prof Dr, Emo Welzl, Prof Dr, Jack Snoeyink, Dr. Uli Wagner Co-examiner
2009 to my parentsAcknowledgments I am deeply grateful to my supervisor Emo Welzl for his motivating and encouraging support during my time as Ph.D. student. He introduced me to the beautiful field...