Arrow Research search

Author name cluster

Emo Welzl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

TCS Journal 2014 Journal Article

On the number of upward planar orientations of maximal planar graphs

  • Fabrizio Frati
  • Joachim Gudmundsson
  • Emo Welzl

We consider the problem of determining the maximum and the minimum number of upward planar orientations a maximal planar graph can have. We show that every n-vertex maximal planar graph has at least Ω ⁎ ( 1. 189 n ) and at most O ⁎ ( 4 n ) upward planar orientations. Moreover, we show that there exist n-vertex maximal planar graphs having O ⁎ ( 2 n ) upward planar orientations and n-vertex maximal planar graphs having Ω ⁎ ( 2. 599 n ) upward planar orientations. Further, we present bounds for the maximum and the minimum number of acyclic orientations a maximal planar graph can have.

Details DOI

MFCS Conference 2004 Invited Paper

Geometric Optimization and Unique Sink Orientations of Cubes p

  • Emo Welzl

Abstract There is an ongoing attempt of designing a provably fast method for solving Linear Programs and related geometric optimization problems by combinatorial methods in the unit cost model (as opposed to the bit-model, where polynomial methods are known). Among others, this research has brought forth randomized methods with subexponential running time, but also a number of interesting combinatorial models like Oriented Matroids, Abstract Objective Functions (AOF), Unimodal Numberings, LP-type Problems, Abstract Optimization Problems (AOP), Unique Sink Orientations of Cubes (USO), et cetera. Although many of these models are quite general, so far there has been little success in showing good lower bounds even in these generalized abstractions. As for the simplex method, there are a number of open questions concerning several pivoting rules, notably randomized ones. After a general introduction, we will focus on one particular model: unique sink orientations of cubes (USO). To this end consider (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 interested in finding the unique sink of the whole cube when the orientation is given implicitly. The basic operation available is the so-called vertex evaluation, where we can access an arbitrary vertex of the cube, for which we obtain the orientations of the incident edges. Unique sink orientations occur when the edges of a deformed geometric n -dimensional cube (i. e. , a polytope with the combinatorial structure of a cube) are oriented according to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for studying unique sink orientations are certain linear complementarity problems, which allow this combinatorial abstraction (due to Alan Stickney and Layne Watson), where orientations with cycles can arise. Similarly, linear programming and some quadratic optimization problems, like computing the smallest enclosing ball of a finite point set, are polynomial time reducible (in the unit cost model) to finding a sink in a unique sink orientation (possibly with cycles). The talk surveys some results concerning upper and lower bounds for algorithms finding the sink in a USO (acyclic or possibly with cycles).

Details

FOCS Conference 2001 Conference Paper

Unique Sink Orientations of Cubes

  • Tibor Szabó
  • Emo Welzl

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 interested in finding the unique sink of the whole cube, when the orientation is given implicitly. The basic operation available is the so-called vertex evaluation, where we can access an arbitrary vertex of the cube, for which we obtain the orientations of the incident edges. Unique sink orientations occur when the edges of a deformed geometric n-dimensional cube (i. e. , a polytope with the combinatorial structure of a cube) are oriented according to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for studying unique sink orientations are certain linear complementarity problems, which allow this combinatorial abstraction (due to Stickney and Watson, 1978), where orientations with cycles can arise. Similarly, some quadratic optimization problems, like computing the smallest enclosing ball of a finite point set, can be formulated as finding a sink in a unique sink orientation (with cycles possible). For acyclic unique sink orientations, randomized procedures due to Bernd Gartner (1998, 2001) with an expected number of at Most e/sup 2/spl radic/n/ vertex evaluations have been known. For the general case, a simple randomized (3/2)/sup n/ procedure exists (without explicit mention in the literature). We present new algorithms, a deterministic O(1. 61/sup n/) procedure and a randomized O((43/20)/sup n/2/)=O(1. 47/sup n/) procedure for unique sink orientations. An interesting aspect of these algorithms is that they do not proceed on a path to the sink (in a simplex-like fashion), but they exploit the potential of random access (in the sense of arbitrary access) to any vertex of the cube. We consider this feature the main contribution of the paper. We believe that unique sink orientations have a rich structure, and there is ample space for improvement on the bounds given above.

Details

TCS Journal 1997 Journal Article

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 × 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 some c⩾0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size. We prove several useful and interesting combinatorial properties of recursive and general SFCs. For an optimality criterion that is important in the design of geometric data structures, we propose a RSFC that is optimal in the worst case and outperforms the previously known RSFCs.

Details DOI

FOCS Conference 1991 Conference Paper

Discrepancy and epsilon-approximations for bounded VC-dimension

  • Jirí Matousek 0001
  • Emo Welzl
  • Lorenz Wernisch

Let (X, R) be a set system on an n-point set X. For a two-coloring on X, its discrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in R. It is shown that if for any m-point subset Y contained in X the number of distinct subsets induced by R on Y is bounded by O(m/sup d/) for a fixed integer d is a coloring with discrepancy bounded by O(n/sup 1/2-1/2d/ (log n)/sup 1+1/2d/). Also, if any subcollection of m sets of R partitions the points into at most O(m/sup d/) classes, then there is a coloring with discrepancy at most O(n/sup 1/2-1/2d/ n). These bounds imply improved upper bounds on the size of in -approximations for (X, R). All of the bounds are tight up to polylogarithmic factors in the worst case. The results allow the generalization of several results of J. Beck (1984) bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure. >

Details

FOCS Conference 1991 Conference Paper

Fat Triangles Determine Linearly Many Holes

  • Jirí Matousek 0001
  • Nathaly Miller
  • János Pach
  • Micha Sharir
  • Shmuel Sifrony
  • Emo Welzl

It is shown that for every fixed delta >0 the following holds: if F is a union of n triangles, all of whose angles are at least delta, then the complement of F has O(n) connected components, and the boundary of F consists of O(n log log n) segments. This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges. A randomized algorithm that computes F in expected time O(n2/sup alpha (n)/ log n) is given. Several applications of these results are presented. >

Details

FOCS Conference 1990 Conference Paper

Drawing Graphs in the Plane with High Resolution

  • Michael Formann
  • Torben Hagerup
  • James Haralambides
  • Michael Kaufmann 0001
  • Frank Thomson Leighton
  • Antonios Symvonis
  • Emo Welzl
  • Gerhard J. Woeginger

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/) >

Details

FOCS Conference 1988 Conference Paper

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces

  • Kenneth L. Clarkson
  • Herbert Edelsbrunner
  • Leonidas J. Guibas
  • Micha Sharir
  • Emo Welzl

The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest. >

Details
v2026.09.13