Emo Welzl

Affiliations:
  • ETH Zurich, Switzerland


According to our database1, Emo Welzl authored at least 151 papers between 1981 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Convex Hulls of Random Order Types.
J. ACM, February, 2023

On Connectivity in Random Graph Models with Limited Dependencies.
Proceedings of the Approximation, 2023

2022
Connectivity of Triangulation Flip Graphs in the Plane.
Discret. Comput. Geom., 2022

2021
Lower bounds for searching robots, some faulty.
Distributed Comput., 2021

2020
Minimal Representations of Order Types by Geometric Graphs.
J. Graph Algorithms Appl., 2020

From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices.
Discret. Comput. Geom., 2020

Solving and Sampling with Many Solutions.
Algorithmica, 2020

Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Clustering Under Perturbation Stability in Near-Linear Time.
Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

An Optimal Decentralized (Δ + 1)-Coloring Algorithm.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).
Proceedings of the 36th International Symposium on Computational Geometry, 2020

2018
Order on Order Types.
Discret. Comput. Geom., 2018

2017
Packing plane spanning trees and paths in complete geometric graphs.
Inf. Process. Lett., 2017

Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

2016
A zero-player graph game in NP $\cap$ coNP.
CoRR, 2016

2014
On the number of upward planar orientations of maximal planar graphs.
Theor. Comput. Sci., 2014

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane.
Discret. Math. Theor. Comput. Sci., 2014

Editorial.
Comput. Geom., 2014

2013
Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique.
J. Comb. Theory, Ser. A, 2013

On the number of crossing-free partitions.
Comput. Geom., 2013

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

2011
On degrees in random triangulations of point sets.
J. Comb. Theory, Ser. A, 2011

Counting Plane Graphs: Flippability and Its Applications.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Counting Simple Polygonizations of Planar Point Sets.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Counting Plane Graphs with Exponential Speed-Up.
Proceedings of the Rainbow of Computer Science, 2011

The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?
Proceedings of the Algorithms Unplugged, 2011

2010
When Conflicting Constraints Can Be Resolved - The Lovász Local Lemma and Satisfiability.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Catching elephants with mice: Sparse sampling for monitoring sensor networks.
ACM Trans. Sens. Networks, 2009

Counting Triangulations of Planar Point Sets
CoRR, 2009

Foreword.
Algorithmica, 2009

Capacity of Arbitrary Wireless Networks.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

The Lovász Local Lemma and Satisfiability.
Proceedings of the Efficient Algorithms, 2009

2008
Kleinster umschließender Kreis. (Ein Demokratiebeitrag aus der Schweiz?)
Proceedings of the Taschenbuch der Algorithmen, 2008

Algorithms for center and Tverberg points.
ACM Trans. Algorithms, 2008

Number of Crossing-Free Geometric Graphs vs. Triangulations.
Electron. Notes Discret. Math., 2008

2007
Online Conflict-Free Coloring for Intervals.
SIAM J. Comput., 2007

2006
On the Number of Crossing-Free Matchings, Cycles, and Partitions.
SIAM J. Comput., 2006

The Number of Triangulations on Planar Point Sets.
Proceedings of the Graph Drawing, 14th International Symposium, 2006

The Number of Crossing Free Configurations on Finite Point Sets in the Plane.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Random triangulations of planar point sets.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005
Online conflict-free coloring for intervals.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Interference in Cellular Networks: The Minimum Membership Set Cover Problem.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
Linear programming.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Algorithmic complexity of protein identification: combinatorics of weighted strings.
Discret. Appl. Math., 2004

Point-Line Incidences in Space.
Comb. Probab. Comput., 2004

Off-line Admission Control for Advance Reservations in Star Networks.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Geometric Optimization and Unique Sink Orientations of Cubes p.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003
Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes.
Fundam. Informaticae, 2003

In between k -Sets, j -Facets, and i -Faces: (i , j) - Partitions.
Discret. Comput. Geom., 2003

2002
Running Time Analysis of Multi-objective Evolutionary Algorithms on a Simple Discrete Optimization Problem.
Proceedings of the Parallel Problem Solving from Nature, 2002

Algorithmic Complexity of Protein Identification: Searching in Weighted Strings.
Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

Translating a Planar Object to Maximize Point Containment.
Proceedings of the Algorithms, 2002

2001
Entering and Leaving <i>j</i>-Facets.
Discret. Comput. Geom., 2001

A Continuous Analogue of the Upper Bound Theorem.
Discret. Comput. Geom., 2001

A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization.
Discret. Comput. Geom., 2001

Crossing-free segments and triangles in point configurations.
Discret. Appl. Math., 2001

Enumerating triangulation paths.
Comput. Geom., 2001

One line and n points.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Unique Sink Orientations of Cubes.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Balanced lines, halving triangles, and the generalized lower bound theorem.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

Explicit and Implicit Enforcing - Randomized Optimization.
Proceedings of the Computational Discrete Mathematics, Advanced Lectures, 2001

2000
On a simple sampling lemma.
Proceedings of the Computing: the Australasian Theory Symposium, 2000

A class of point-sets with few k-sets.
Comput. Geom., 2000

<i>n</i> Points and One Line: Analysis of Randomized Games.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2000

Origin-embracing distributions or a continuous analogue of the upper bound theorem.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

Random sampling in geometric optimization: new insights and applications.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1998
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions.
J. Algorithms, 1998

The Discrete 2-Center Problem.
Discret. Comput. Geom., 1998

Approximation of convex figures by pairs of rectangles.
Comput. Geom., 1998

One Sided Error Predicates in Geometric Computing.
Proceedings of the Fundamentals - Foundations of Computer Science, 1998

Results on <i>k</i>-Sets and <i>j</i>-Facets via Continuous Motion.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997
Space-Filling Curves and Their Use in the Design of Geometric Data Structures.
Theor. Comput. Sci., 1997

The rank of sparse random matrices over finite fields.
Random Struct. Algorithms, 1997

Cutting Dense Point Sets in Half.
Discret. Comput. Geom., 1997

Fast Greedy Triangulation Algorithms.
Comput. Geom., 1997

Piecewise Linear Approximation of Bézier-Curves.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Contour Edge Analysis for Polyhedron Projections.
Proceedings of the Geometric Modeling: Theory and Practice, 1997

1996
Guest Editor's Foreword.
Discret. Comput. Geom., 1996

A Subexponential Bound for Linear Programming.
Algorithmica, 1996

Linear Programming - Randomization and Abstract Frameworks.
Proceedings of the STACS 96, 1996

Rectilinear and Polygonal <i>p</i>-Piercing and <i>p</i>-Center Problems.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
Improved Bounds on Weak epsilon-Nets for Convex Sets.
Discret. Comput. Geom., 1995

Minimal Enclosing Parallelogram with Application.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

1994
Fat Triangles Determine Linearly Many Holes.
SIAM J. Comput., 1994

Surface Reconstruction Between Simple Polygons via Angle Criteria.
J. Symb. Comput., 1994

Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements.
Discret. Comput. Geom., 1994

Gram's Equation - A Probabilistic Proof.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993
Drawing Graphs in the Plane with High Resolution.
SIAM J. Comput., 1993

Tail Estimates for the Efficiency of Randomized Incremental Algorithms for Line Segment Intersection.
Comput. Geom., 1993

Discrepancy and approximations for bounded VC-dimension.
Comb., 1993

Weaving Patterns of Lines and Line Segments in Space.
Algorithmica, 1993

Shortest Paths for Line Segments.
Algorithmica, 1993

1992
Good Splitters for Counting Points in Triangles.
J. Algorithms, 1992

Polynomial graph-colorings.
Discret. Appl. Math., 1992

Simultaneous Inner and Outer Approximation of Shapes.
Algorithmica, 1992

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems.
Algorithmica, 1992

New Results on Linear Programming and Related Problems.
Proceedings of the Algorithm Theory, 1992

A Combinatorial Bound for Linear Programming and Related Problems.
Proceedings of the STACS 92, 1992

Tail Estimates for the Space Complexity of Randomized Incremental Algorithms.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

On Spanning Trees with Low Crossing Numbers.
Proceedings of the Data Structures and Efficient Algorithms, 1992

1991
Discrepancy and epsilon-approximations for bounded VC-dimension
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Fat Triangles Determine Linearly Many Holes
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

The Post Office Problem for Fuzzy Point Sets.
Proceedings of the Computational Geometry, 1991

Smallest enclosing disks (balls and ellipsoids).
Proceedings of the New Results and New Trends in Computer Science, 1991

1990
Boundary Graph Grammars with Dynamic Edge Relabeling.
J. Comput. Syst. Sci., 1990

Ranking intervals under visibility constraints.
Int. J. Comput. Math., 1990

Combinatorial Complexity Bounds for Arrangement of Curves and Spheres.
Discret. Comput. Geom., 1990

Efficient Parallel Computation of Arrangements of Hyperplanes in d Dimensions.
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Weaving Patterns of Lines and Segments in Space.
Proceedings of the Algorithms, 1990

How to Net a Lot with Little: Small epsilon-Nets for Disks and Halfspaces.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.
Theor. Comput. Sci., 1989

Implicitly Representing Arrangements of Lines or Segments.
Discret. Comput. Geom., 1989

Quasi-Optimal Range Searching in Space of Finite VC-Dimension.
Discret. Comput. Geom., 1989

1988
Visibility graphs and obstacle-avoiding shortest paths.
ZOR Methods Model. Oper. Res., 1988

Congruence, Similarity, and Symmetries of Geometric Objects.
Discret. Comput. Geom., 1988

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Partition Trees for Triangle Counting and Other Range Searching Problems.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

New Methods for Computing Visibility Graphs.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987
epsilon-Nets and Simplex Range Queries.
Discret. Comput. Geom., 1987

Combinatorial properties of boundary NLC graph languages.
Discret. Appl. Math., 1987

String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing.
Discret. Appl. Math., 1987

Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986
Constructing Belts in Two-Dimensional Arrangements with Applications.
SIAM J. Comput., 1986

On the maximal number of edges of many faces in an arrangement.
J. Comb. Theory, Ser. A, 1986

The Bounded Degree Problem for NLC Grammars is Decidable.
J. Comput. Syst. Sci., 1986

Trace Languages Defined by Regular String Languages.
RAIRO Theor. Informatics Appl., 1986

Halfplanar Range Search in Linear Space and O(n^(0.695)) Query Time.
Inf. Process. Lett., 1986

Boundary NLC Graph Grammars-Basic Definitions, Normal Forms, and Complexity
Inf. Control., 1986

More on k-Sets of Finite Sets in the Plane.
Discret. Comput. Geom., 1986

Graph Theoretic Closure Properties of the Family of Boundary NLC Graph Languages.
Acta Informatica, 1986

Boundary NlC and partition controlled graph grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1986

1985
Complexity and Decidability for Chain Code Picture Languages.
Theor. Comput. Sci., 1985

Recurrent Words and Simultaneous Growth in T0L Systems.
Theor. Comput. Sci., 1985

On the Number of Line Separations of a Finite Set in the Plane.
J. Comb. Theory, Ser. A, 1985

Constructing the Visibility Graph for n-Line Segments in O(n²) Time.
Inf. Process. Lett., 1985

A simple method for solving 2-dimensional static range searching.
Bull. EATCS, 1985

String grammars with disconnecting.
Proceedings of the Fundamentals of Computation Theory, 1985

The complexity of cutting paper (extended abstract).
Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984
Symmetric graphs and interpretations.
J. Comb. Theory, Ser. B, 1984

Monotone Edge Sequences in Line Arrangements and Applications (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Encoding Graphs by Derivations and Implications for the Theory of Graph Grammars.
Proceedings of the Automata, 1984

Boundary NLC Grammars.
Proceedings of the CAAP'84, 1984

1983
On the Number of Equal-Sized Semisapces of a Set of Points in the Plane (Extended Abstract).
Proceedings of the Automata, 1983

Two Way Finite State Generators.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
Using String Languages to Describe Picture Languages
Inf. Control., September, 1982

Color-Families are Dense.
Theor. Comput. Sci., 1982

Stabbing Line Segments.
BIT, 1982

Chain code picture languages.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1982

1981
On the Complexity of the General Coloring Problem
Inf. Control., November, 1981

On the Density of Color-Families.
Proceedings of the Automata, 1981


  Loading...