Source author record

Emo Welzl

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry math.CO Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Convex Hulls of Random Order Types

We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank $3$ ): (a) The number of extreme points in an $n$ -point order type, chosen uniformly at random from all such order types, is on average $4+o(1)$ . For labeled order types, this number has average $4- \frac{8}{n^2 - n +2}$ and variance at most $3$ . (b) The (labeled) order types read off a set of $n$ points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e. such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension $d$ for labeled order types with the average number of extreme points $2d+o(1)$ and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods allow to show the following relative of the Erdős-Szekeres theorem: for any fixed $k$ , as $n \to \infty$ , a proportion $1 - O(1/n)$ of the $n$ -point simple order types contain a triangle enclosing a convex $k$ -chain over an edge. For the unlabeled case in (a), we prove that for any antipodal, finite subset of the $2$ -dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral or one of $A_4$ , $S_4$ or $A_5$ (and each case is possible). These are the finite subgroups of $SO(3)$ and our proof follows the lines of their characterization by Felix Klein.

preprint2020arXiv

Connectivity of Triangulation Flip Graphs in the Plane

Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation flips an edge (an edge flip), removes a non-extreme point of degree 3, or adds a point in P \ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early 70s that these graphs are connected. Our goal is to investigate these graphs, with emphasis on vertex connectivity. For sets of n points in the plane in general position, we show that the edge flip graph is (n/2-2)-connected, and the bistellar flip graph is (n-3)-connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations, ie. partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull. Here (n-3)-connectivity has been known since the late 80s via the secondary polytope due to Gelfand, Kapranov & Zelevinsky and Balinski's Theorem. For the edge flip-graphs, the vertex connectivity can be shown to be at least as large as (and hence equal to) the minimum degree, provided n is large enough. Our methods yield several other results.

preprint2011arXiv

Counting Plane Graphs: Flippability and its Applications

We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to so-called \emph{pseudo-simultaneously flippable edges}. Such edges are related to the notion of convex decompositions spanned by S. We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of N points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let tr(N) denote the maximum number of triangulations on a set of N points in the plane. Then we show (using the known bound tr(N) < 30^N) that any N-element point set admits at most 6.9283^N * tr(N) < 207.85^N crossing-free straight-edge graphs, O(4.7022^N) * tr(N) = O(141.07^N) spanning trees, and O(5.3514^N) * tr(N) = O(160.55^N) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have cN, fewer than cN, or more than cN edges, for any constant parameter c, in terms of c and N.

preprint2011arXiv

Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of $N$ points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are $O(1.8181^N)$ for cycles and $O(1.1067^N)$ for matchings. These imply a new upper bound of $O(54.543^N)$ on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of $N$ points in the plane (improving upon the previous best upper bound $O(68.664^N)$ ). Our analysis is based on Kasteleyn's linear algebra technique.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.