29 citations · 89 across the 22 of their papers we have counts for
22 papers · 1 filter
Deciding monotonicity of simple drawings of the complete graph
Oswin Aichholzer, Thomas Hackl, Alexander Pilz +2
A drawing of a graph is {\em -monotone} if every vertical line intersects each edge of the graph at most once. We present an time algorithm for deciding whether a simpl…
Blocking Delaunay Triangulations from the Exterior
Oswin Aichholzer, Thomas Hackl, Maarten Löffler +4
Given two distinct point sets and in the plane, we say that \emph{blocks} if no two points of are adjacent in any Delaunay triangulation of . Aichholze…
On Plane Subgraphs of Complete Topological Drawings
Alfredo García, Alexander Pilz, Javier Tejel
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if…
On Compatible Matchings
Oswin Aichholzer, Alan Arroyo, Zuzana Masárová +5
A matching is compatible to two or more labeled point sets of size with labels if its straight-line drawing on each of these point sets is crossing-free. We stu…
Arrangements of Approaching Pseudo-Lines
Stefan Felsner, Alexander Pilz, Patrick Schnider
We consider arrangements of pseudo-lines in the Euclidean plane where each pseudo-line is represented by a bi-infinite connected -monotone curve , $x \in \m…
Bisecting three classes of lines
Alexander Pilz, Patrick Schnider
We consider the following problem: Let be an arrangement of lines in colored red, green, and blue. Does there exist a vertical plane such that…
A new lower bound on the maximum number of plane graphs using production matrices
Clemens Huemer, Alexander Pilz, Rodrigo I. Silveira
We use the concept of production matrices to show that there exist sets of points in the plane that admit crossing-free geometric graphs. This improves the previou…
From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
Alexander Pilz, Emo Welzl, Manuel Wettstein
A set of points in general position in the plane is called a wheel set if all points but are extreme. We show that for the purpose of counting crossing…
Extending the centerpoint theorem to multiple points
Alexander Pilz, Patrick Schnider
The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set of points in , there is a point , not…
A Note on the Flip Distance Problem for Edge-Labeled Triangulations
Alexander Pilz
For both triangulations of point sets and simple polygons, it is known that determining the flip distance between two triangulations is an NP-hard problem. To gain more insight int…
Geodesic Order Types
Oswin Aichholzer, Matias Korman, Alexander Pilz +1
The geodesic between two points and in the interior of a simple polygon~ is the shortest polygonal path inside that connects to . It is thus the natural gener…
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman +5
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph on any set of points in general position…
Packing Short Plane Spanning Graphs in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman +5
Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want t…
An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer +2
Let be a set of labeled points in the plane. The radial system of describes, for each , the order in which a ray that rotates around encounters the points i…
Ham-Sandwich Cuts for Abstract Order Types
Stefan Felsner, Alexander Pilz
The linear-time ham-sandwich cut algorithm of Lo, Matoušek, and Steiger for bi-chromatic finite point sets in the plane works by appropriately selecting crossings of the lines in t…
The Dual Diameter of Triangulations
Matias Korman, Stefan Langerman, Wolfgang Mulzer +3
Let $\Poly$ be a simple polygon with vertices. The \emph{dual graph} $\triang^*$ of a triangulation~$\triang$ of~$\Poly$ is the graph whose vertices correspond to the bounded f…
Linear transformation distance for bichromatic matchings
Oswin Aichholzer, Luis Barba, Thomas Hackl +2
Let be a set of points in general position, where is a set of blue points and a set of red points. A \emph{-matching} is a plane geometric perf…
Monotone Simultaneous Embedding of Directed Paths
Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp +3
We study monotone simultaneous embeddings of upward planar digraphs, which are simultaneous embeddings where the drawing of each digraph is upward planar, and the directions of the…
Geodesic-Preserving Polygon Simplification
Oswin Aichholzer, Thomas Hackl, Matias Korman +2
Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the inpu…
Empty triangles in good drawings of the complete graph
Oswin Aichholzer, Thomas Hackl, Alexander Pilz +3
A good drawing of a simple graph is a drawing on the sphere or, equivalently, in the plane in which vertices are drawn as distinct points, edges are drawn as Jordan arcs connecting…
Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
Oswin Aichholzer, Wolfgang Mulzer, Alexander Pilz
Let T be a triangulation of a simple polygon. A flip in T is the operation of removing one diagonal of T and adding a different one such that the resulting graph is again a triangu…
Flip Distance Between Triangulations of a Planar Point Set is APX-Hard
Alexander Pilz
In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a…