AICHHOLZER , Oswin

Let S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that any two trees in TS can be transformed into each other by O(n2) local and constant-size edge slide operations. No polynomial upper bound for this task has been known, but in O.Aichholzer, F.Aurenhammer, F.Hurtado Sequences of...

Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.

Given a set $\cal S$ of $n$ points in three dimensions, we study the maximum numbers of quadrics spanned by subsets of points in $\cal S$ in various ways. We prove that the set of empty or enclosing ellipsoids has $\Theta(n^4)$ complexity. The same bound applies to empty general cylinders, while for empty circular cylinders a gap remains...

Given a set S of n points in three dimensions, we study the maximum numbers of quadrics spanned by subsets of points in S in several ways. Among various results we prove that the number of empty circular cylinders is between Omega(n3) and O(n4) while we have a tight bound Theta(n4) for empty ellipsoids. We also take interest in pairs of empty...

We compute the exact number of pseudo-triangulations for two prominent point sets, namely the so-called double circle and the double chain. We also derive a new asymptotic lower bound for the maximal number of pseudotriangulations which lies significantly above the related bound for triangulations.

A flipturn transforms a nonconvex simple polygon into another simple polygon by rotating a concavity 180◦ around the midpoint of its bounding convex hull edge. Joss and Shannon proved in 1973 that a sequence of flipturns eventually transforms any simple polygon into a convex polygon. This paper describes several new results about such...

No description

We present a practical Java tool for simulating synchronized distributed algorithms on sets of 2-and 3-dimensional square/cubic lattice-based agents. This AgentSystem assumes that each agent is capable to change position in the lattice and that neighboring agents can attach and detach from each other. In addition, it assumes that each module...

No description

In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the...