Counting Triangulations of Planar Point Sets (2009)
Sharir, Micha, Sheffer, Adam, Welzl, Emo
We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme...
Capacity of Arbitrary Wireless Networks (2009)
Olga Goussevskaia, Magnús M. Halldórsson, Roger Wattenhofer, Emo Welzl
Abstract — In this work we study the problem of determining the throughput capacity of a wireless network. We propose a scheduling algorithm to achieve this capacity within an approximation factor....
citizen of Germany accepted on the recomodation of (2009)
Ingo Andreas Schurr, Prof Dr, Emo Welzl, Eth Zürich, Dr. Tibor Szabó, Eth Zürich, ...
I would like to express my deep gratitude to my advisor Emo Welzl. His idea of a Pre-Doc program gave me the chance to sneak into the world of discrete mathematics. Furthermore, all I know about how...
]~psilon-Nets and Simplex Range Queries (2009)
Altmtract We present a new technique for half-space and simplex range query using O(n) space and O(n a) query time, where a < if(a-l) +7 for all dimensions d ~2 a(a-l) + 1 and 7> 0. These...
On the Number of Lattice Triangulations ∗ (2008)
Emo Welzl, V. Kaibel, G. Ziegler, Counting Lattice Triangulations, British Combinatorial
For n a positive integer, we consider triangulations of the n×n lattice set {0, 1, 2,..., n} 2, i.e. crossing-free straight line embedded geometric graphs on this point set—thus with (n+1) 2...
I can't get no satisfactionI can't get no satisfaction 'Cause I try and I try and I try and I tryI can't get no, I can't get no
accepted on the recommendation of (2008)
Falk Tschirschnitz, Prof Dr, Emo Welzl, Eth Zürich, Prof Dr. Walter Morris
Linear Programming is the problem of maximizing a linear function in d variables subject to n linear constraints. Its relevance arises from the huge number of optimization problems that can be...
zur Erlangung des Doktorgrades vorgelegt am Fachbereich Mathematik und Informatik (2008)
Bernd Gärtner, Betreuer Prof, Dr. Emo Welzl, Zweitgutachter Prof, ...
verteidigt am 20. Dezember 1995
accepted on the recommendation of (2008)
Christoph Ambühl, Prof Dr, Emo Welzl, Eth Zürich, Prof Dr, Susanne Albers, ...
examiner
Abstract Efficient parallel computation of arrangements of hyperplanes in d dimensions* (2008)
Torben Hagerup, Hermann Jung, Emo Welzl
We propose the jirst optimal parallel algorithm comput-ing arrangements of hyperplanes in Ed (d 2 2). The algorithm is randomized and computes the arrangement of n hyperplanes within expected...
The Number of Triangulations on Planar Point Sets (2008)
Abstract. We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such as the n×n integer lattice....
Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, Kalyanmoy Deb
Running time analysis of a multi-objective
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...
Algorithms for Weak "-Nets (2008)
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, Emo Welzl
In the plane, we can nd a weak "-net for convex sets consisting of O( ",2) points, in time O(n ",2). We can determine the smallest " for which a given planar set...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 points, in time O(n" \Gamma2). We can determine the smallest " for which a given...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl
Let S be a set of n points in IR d. A set W is a weak "-net for (convex ranges of) S if for any T ` S containing "n points, the convex hull of T intersects W. We show the existence...
to appear in Combinatorics Probability and Computing. Point-Line Incidences in Space (2007)
Given a set L of n lines in R
New methods for computing visibility graphs* Extended abstract (2007)
methods for computing visibility graphs
v2V fi v = (n\Gamma2)-- known as Euclid's angle-sum equation. We normalize the full angle to 1, i.e. we set ff v = fi v =(2). Then the equation reads as
A recent result by Pach and Pinchasi on so-called balanced lines of a nite 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...
to appear in Discrete & Computational Geometry. Entering and Leaving j-Facets (2007)
Let S be a set of n points in d-space, no i + 1 points on a common (i 1)- at for 1 i d. An oriented (d 1)-simplex spanned by d points in S is called j-facet of S, if there are exactly j points from S...
Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, Kalyanmoy Deb
Running time analysis of a multi-objective evolutionary algorithm on a simple discrete
Point-sets with few k-sets Helmut Alt (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Emo Welzl
A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is...
Bernd G Artner, J Ozsef Solymosi, Falk Tschirschnitz, Emo Welzl, 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...
Decomposition of Masses (2007)
Michael Eisenring, Supervised Mark Cieliebak, Emo Welzl
for the different letters. For a given weight M 2 R and an error tolerance " ? 0, our question is if there exist multiplicities k 1 ; : : : k d 2 N 0 such that k 1 m 1 + : : : + k d m d 2 [M...
The Number of Triangulations on Planar Point Sets (2007)
We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such as the n x n integer lattice.
The Number of Triangulations on Planar Point Sets (2007)
We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such as the n x n integer lattice.
Spectral Methods for Reconstruction Problems (2007)
Dieter Mitsche, Dieter Mitsche, Prof Dr, Emo Welzl, Eth Zürich
presented by
Prof Dr, Emo Welzl, Eth Zurich
The goal of this thesis is to give a better understanding of the linear complementarity problem with a P-matrix (PLCP). Finding a polynomial time algorithm for the PLCP is a longstanding open...
Online conflict-free coloring for intervals. (2006)
Fiat, Amos, Matoušek, Jiří, Mossel, Elchanan, Pach, János, Sharir, Micha, Smorodinsky, Shakhar, ...
On the number of crossing-free matchings, (cycles, and partitions (2006)
Abstract We show that a set of n points in the plane has at mostO(10.05n) perfect matchings with crossing-free straight-line
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...
Interference in cellular networks: The minimum membership set cover problem (2005)
Fabian Kuhn, Pascal Von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger
Abstract. The infrastructure for mobile distributed tasks is often formed by cellular networks. One of the major issues in such networks is interference. In this paper we tackle interference...
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...
Off-line admission control for advance reservations in star networks (2004)
Udo Adamy, Thomas Erlebach, Dieter Mitsche, Ingo Schurr, Bettina Speckmann, Emo Welzl
Abstract. Given a network together with a set of connection requests, call admission control is the problem of deciding which calls to accept and which ones to reject in order to maximize the total...
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 –...
Algorithmic complexity of protein identification: Combinatorics of weighted strings (2004)
Mark Cieliebak, Thomas Eriebach, Zsuzsanna Liptak, Jens Stoye, Emo Welzl
We investigate a problem from computational biology: Given a constant size alphabet M with a weight function / : M--> +, find an efficient data structure and query algorithm solving the following...
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...
Mark Cieliebak, Thomas Erlebach, Zsuzsanna Lipták, Jens Stoye, Emo Welzl
We investigate a problem which arises in computational biology: Given a constant– size alphabet A with a weight function µ: A → N, find an efficient data structure and query algorithm solving...
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem (2003)
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...
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...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal,Pankaj, Hagerup,Torben, Ray,Rahul, Sharir,Micha, Smid,Michiel, Welzl,Emo
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal, Pankaj, Hagerup, Torben, Ray, Rahul, Sharir, Micha, Smid, Michiel, Welzl, Emo, ...
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
Translating a planar object to maximize point containment (2002)
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl
Abstract. Let C be a compact set in R
Welzl: Euler graphs, triangle-free graphs and bipartite graphs in switching classes (2002)
Jurriaan Hage, Tero Harju, Emo Welzl
switching classes
Translating a planar object to maximize point containment (2002)
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl
Abstract. Let � be a compact set in Ê and let Ë beasetofÒpoints in Ê.We consider the problem of computing a translate of � that contains the maximum number, � £ , of points of Ë. It is...
Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, Kalyanmoy Deb
For th first time, a running time analysis of populationbased multi-objective evolutionary algorithB for a discrete optimization problem is given. To th s end, we define a simple pseudo-Boolean...
Bernd Gartner, Falk Tschirschnitz, Emo Welzl, Jozsef 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...
A continuous analogue of the upper bound theorem (2001)
For an absolutely continuous probability measure on R
Explicit and implicit enforcing – randomized optimization (2001)
This tutorial is aiming at some randomized approaches for geometric optimization that have been developed over the last ten to fteen years. The methods are simple, sometimes even the analysis is. The...
A simple sampling lemma: Analysis and applications in geometric optimization (2001)
Random sampling is an efficient method to deal with constrained optimization problems in computational geometry. In a first step, one finds the optimal solution subject to a random subset of the...
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...
This is a collection of basics and basic examples of probabilistic analysis of discrete random variables, very much biased towards what we will need in the course on Randomized Algorithms. Even if...
Unique sink orientations of cubes (2000)
Suppose we are given (the edge graph of) an n-dimensional hypercube with its edges oriented so that every face has a unique sink. Such an orientation is called a unique sink orientation, and we are...
Enumerating Triangulation Paths (2000)
Adrian Dumitrescu, Bernd Gärtner, Samuele Pedroni, Emo Welzl
Recently, Aichholzer introduced the remarkable concept of the so-called triangulation path (of a triangulation with respect to a segment), which has the potential of providing efficient counting of...
Random Sampling in Geometric Optimization: New Insights and Applications (2000)
Random sampling is an efficient method to deal with constrained optimization problems in computational geometry. In a first step, one finds the optimal solution subject to a random subset of the...
citizen of Germany accepted on the recommendation of (2000)
Prof Dr, Emo Welzl, Prof Dr, Komei Fukuda
I am grateful to my adviser Prof. Dr. Emo Welzl for the opportunity to learn from him during the last years, and for countless ideas and suggestions, which became a part of this thesis. His...
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem (2000)
this paper is to show the relation between the balanced lines problem (A) of [7], some problems involving halving triangles in 3-space, and the Generalized Lower Bound Theorem. This sheds some extra...
Enumerating triangulation paths (2000)
Adrian Dumitrescu, Bernd Gärtner, Samuele Pedroni, Emo Welzl
Recently, Aichholzer introduced the remarkable concept of the so-called triangulation path (of a triangulation with respect to a segment), which has the potential of providing efficient counting of...
Constraint Programming and Graph Algorithms (2000)
Mehlhorn, Kurt, Montanari, Ugo, Rolim, José D. P., Welzl, Emo
Approximation of Convex Figures by Pairs of Rectangles (1998)
Schwarzkopf, Otfried, Fuchs, Ulrich, Rote, Günter, Welzl, Emo
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R....
Approximation of Convex Figures by Pairs of Rectangles (1998)
Schwarzkopf, Otfried, Fuchs, Ulrich, Rote, Günter, Welzl, Emo
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R....
Approximation of Convex Figures by Pairs of Rectangles (1998)
Schwarzkopf, Otfried, Fuchs, Ulrich, Rote, Günter, Welzl, Emo
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R....
Approximation of convex figures by pairs of rectangles (1998)
Otfried Schwarzkopf, Ulrich Fuchs, Emo Welzl
We consider the problem of approximating a convex �gure in the plane by a pair �r;R � of homothetic �that is, similar and parallel � rectangles with r � C � R. We show the existence of...
Results on k-sets and j-facets via continuous motion (1998)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR
One sided error predicates in geometric computing (1998)
A conservative implementation of a predicate returns true only if the exact predicate is true. That is, we accept a one sided error for the implementation. For geometric predicates, such as...
Approximation of convex figures by pairs of rectangles (1998)
Otfried Schwarzkopf, Ulrich Fuchs, Emo Welzl
We consider the problem of approximating a convex �gure in the plane by a pair �r;R � of homothetic �that is, similar and parallel � rectangles with r � C � R. We show the existence of...
. Given n points in R d , a hyperplane is called halving if it has at most bn=2c points on either side. How many partitions of a point set (into the points on one side, on the hyperplane, and on the...
Given n points in R d , a hyperplane is called halving if it has at most bn=2c points on either side. How many partitions of a point set (into the points on one side, on the hyperplane, and on the...
The Discrete 2-Center Problem (1998)
Pankaj K. Agarwal, Micha Sharir, Emo Welzl
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...
The Discrete 2-Center Problem (1997)
Pankaj Agarwal Micha, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir, Emo Welzl, ...
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...
The Rank of Sparse Random Matrices over Finite Fields (1997)
Johannes Blömer, Richard Karp, Emo Welzl
Let M be a random matrix over GF[q] such that for each entry M ij in M and for each non-zero field element ff the probability Pr[M ij = ff] is p=(q \Gamma 1), where p = (log n \Gamma c)=n and c is an...
Contour Edge Analysis for Polyhedron Projections (1997)
Lutz Kettner, Emo Welzl, R. Klein, R. Rau (eds
. Given a polyhedron (in 3-space) and a view point, an edge of the polyhedron is called contour edge, if one of the two incident facets is directed towards the view point, and the other incident...
Contour Edge Analysis for Polyhedron Projections (1997)
. Given a polyhedron (in 3-space) and a view point, an edge of the polyhedron is called contour edge, if one of the two incident facets is directed towards the view point, and the other incident...
Piecewise Linear Approximation of Bézier-Curves (1997)
Helmut Alt, Emo Welzl, Barbara Wolfers
F24.86> B i;n (t j ) can be precomputed and stored in a table, and the vertices of the approximation can be easily retrieved as linear combinations of the control points. Observe that C has a...
The Discrete 2-Center Problem (1997)
Pankaj K. Agarwal, Micha Sharir, Emo Welzl
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...
k-sets and j-facets - A tour of discrete geometry (1997)
This paper gives an account of the most important facts about k-sets, j-facets and k-levels. First, we describe the fundamental properties of the objects under discussion and some related ones. We...
Results on k-Sets and j-Facets via Continuous Motion (1997)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR d in general position, i.e., no i + 1 points on a common (i \Gamma 1)-flat, 1 i d. A k-set of P is a set S of k points in P that can be separated from P nS by a...
The Rank of Sparse Random Matrices over Finite Fields (1997)
Johannes Blömer, Emo Welzl, Emo Welzl, Richard Karp, Richard Karp
. Let M be a random matrix over GF[q] such that for each entry M ij in M and for each non-zero field element ff the probability Pr[M ij = ff] is p=(q \Gamma 1), where p = (log n \Gamma c)=n and c is...
Linear programming -- randomization and abstract frameworks (1996)
Recent years have brought some progress in the knowledge of the complexity of linear programming in the unit cost model, and the best result known at this point is a randomized ‘combinatorial ’...
Linear Programming - Randomization and Abstract Frameworks (1996)
B. Gärtner, E. Welzl, Bernd Gartner, Emo Welzl
Recent years have brought some progress in the knowledge of the complexity of linear programming in the unit cost model, and the best result known at this point is a randomized `combinatorial'...
Rectilinear and Polygonal p-Piercing and p-Center Problems (1996)
We consider the p-piercing problem, in which we are given a collection of regions, and wish to determine whether there exists a set of p points that intersects each of the given regions. We give...
A Subexponential Bound for Linear Programming (1996)
Jiri Matousek, Micha Sharir, Emo Welzl
We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected minfO(d 2 2 d n); e 2 p d ln(n= p d )+O( p d+ln n) g time in the unit cost model...
Algorithms for Weak Epsilon-Nets (1995)
Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, ...
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 ) points, in time O(n" \Gamma2 log 2 (1=")). We can determine the smallest " for which a...
Algorithms for Weak Epsilon-Nets (1995)
Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, ...
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 ) points, in time O(n" \Gamma2 ). We can determine the smallest " for which a given planar set is...
Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements (1994)
An arrangement of oriented pseudohyperplanes in affine d-space defines on its set X of pseudohyperplanes a set system (or range space) (X, R), R ⊆ 2 X of VCdimension d in a natural way: to every...
On finding a minimal enclosing parallelogram (Abstract) (1994)
Christian Schwarz, Jürgen Teich, Emo Welzl, Brian L. Evans
) Christian Schwarz Jurgen Teich y Emo Welzl z Brian L. Evans x November 29, 1994 Let C be a convex polygon in the plane with n vertices. We denote by PC a parallelogram that encloses C and that has...
Fast Greedy Triangulation Algorithms (1994)
Matthew T. Dickerson, Scott A. McElfresh, Emo Welzl
this paper we present a simple, practical algorithm that computes the greedy triangulation in expected time O(n log n) and space O(n) for points uniformly distributed over any convex shape. A variant...
On Finding a Minimal Enclosing Parallelogram (1994)
Christian Schwarz, Jürgen Teich, Emo Welzl, Brian Evans
Given a convex polygon C with n vertices, we show how a parallelogram with minimal area enclosing C can be computed in linear time O(n). The problem is of interest in digital signal processing....
Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements (1994)
An arrangement of oriented pseudohyperplanes in affine d-space defines on its set X of pseudohyperplanes a set system (or range space) (X; R), R ` 2 X of VCdimension d in a natural way: to every cell...
Leonidas Guibas, Micha Sharir, Emo Welzl
Let S be a set of n points in IR d. A set W is a weak "-net for (convex ranges of) S if for any T S containing "n points, the convex hull of T intersects W. We show the existence of...
Fat triangles determine linearly many holes. (1994)
Matoušek, Jiří, Pach, János, Sharir, Micha, Sifrony, Shmuel, Welzl, Emo
Shortest Paths for Line Segments (1993)
Christian Icking, Günter Rote, Emo Welzl, Chee Yap
We study the problem of shortest paths for a line segment in the plane. As a measure of the distance traversed by a path, we take the average curve length of the orbits of prescribed points on the...
On Spanning Trees with Low Crossing Numbers (1992)
Every set S of n points in the plane has a spanning tree such that no line disjoint from S has more than O( p n) intersections with the tree (where the edges are embedded as straight line segments)....
Case-Based BDI Agents: an Effective Approach for Intelligent Search on the World Wide Web (1992)
Cindy Olivia, C.F Chang, C.F Enguix, A.K. Ghose, Micha Sharir, Emo Welzl
We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected minfO(d 2 2 d n); e 2 p d ln(n= p d )+O( p d+ln n) g time in the unit cost model...
Simultaneous Inner and Outer Approximation of Shapes (1992)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng
Tail Estimates for the Space Complexity of Randomised Incremental Algorithms (1992)
Mehlhorn, Kurt, Sharir, Micha, Welzl, Emo, Frederickson, Grag, Graham, Ron, Hochbaum, Dorit S., ...
Smallest Enclosing Disks (balls and Ellipsoids) (1991)
A simple randomized algorithm is developed which computes the smallest enclosing disk of a finite set of points in the plane in expected linear time. The algorithm is based on Seidel's recent...
How to net a lot with little: small "-nets for disks and halfspaces (1990)
It is known that in general range spaces of VC-dimension d? 1 require "-nets to be of size at least\Omega\Gamma d " log 1 "). We address the question whether this general...
Approximation of Convex Figures by Pairs of Rectangles (1990)
Otfried Schwarzkopf Ulrich, Ulrich Fuchs, Gunter Rote, Emo Welzl
We consider the problem of approximating a convex figure in the plane by a pair (r; R) of homothetic (that is, similar and parallel) rectangles with r ` C ` R. We show the existence of such a pair...
Approximation of Convex Figures by Pairs of Rectangles (1990)
Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, Emo Welzl
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r ` C ` R. We show the existence of such a pair...
On Simultaneous Inner and Outer Approximation of Shapes (1990)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng
citizen of Switzerland accepted on the recommendation of (1975)
Kaspar Fischer, Prof Dr, Emo Welzl, Eth Zürich, Dr. Bernd Gärtner, Eth Zürich, ...
I would like to thank all the people without whom this thesis would not have been written. In the first place, my thanks go to Emo Welzl for giving me the opportunity to work in his research group...
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl
The combinatorial complexity of the Voronoi diagram of n lines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to be O(n 2 ff(n)...
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl
The combinatorial complexity of the Voronoi diagram of n lines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to be O(n 2 ff(n)...
Space Filling Curves and Their Use in the Design of Geometric Data Structures
Tetsuo Asano, Desh Ranjan, Thomas Roos, Emo Welzl, Peter Widmayer
. We are given a two-dimensional square grid of size N \Theta N , where N := 2 n and n 0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c + 1 to c +N 2 , for...