ANovel Type of Skeleton for Polygons OSWIN AICHHOLZER (2009)
Franz Aurenhammer, David Alberts, Bernd Gartner
and discussed. It is composed of pieces of angular bisectores which partition the interior of a given n-gon P in a tree-like fashion into n monotone polygons. Its straight-line structure and its...
Lower and upper bounds on the number of empty cylinders and ellipsoids (2009)
Aichholzer, Oswin, Aurenhammer, Franz, Devillers, Olivier, Hackl, Thomas, Teillaud, Monique, Vogtenhuber, Birgit
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...
Lower and upper bounds on the number of empty cylinders and ellipsoids (2009)
Aichholzer, Oswin, Aurenhammer, Franz, Devillers, Olivier, Hackl, Thomas, Teillaud, Monique, Vogtenhuber, Birgit
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...
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, Carlos Seara, Shakhar Smorodinsky
Given a set P of points in the plane, a set of points Q is a weak ε-net with respect to a family of sets S (e.g., rectangles, disks, or convex sets) if every set of S containing ε|P | points...
1 Introduction Small Weak Epsilon Nets (2008)
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, Shakhar Smorodinsky, Carlos Seara
Let P be a set of n points in R 2. A point q (not
On (Pointed) Minimum Weight Pseudo-Triangulations (2008)
Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Bettina Speckmann
In this note we discuss some structural properties of minimum weight (pointed) pseudo-triangulations. 1
A Novel Type of Skeleton for Polygons OSWIN AICHHOLZER (2008)
Franz Aurenhammer, David Alberts, Bernd Gartner
Abstract A new internal structure for simple polygons, the straight skeleton, is introduced and discussed. It is composed of pieces of angular bisectores which partition the interior of a given n-gon...
On (Pointed) Minimum Weight Pseudo-Triangulations (2008)
Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Bettina Speckmann
In this note we discuss some structural properties of minimum weight (pointed) pseudo-triangulations. 1
Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem (2008)
Aicholzer, Oswin, Devillers, Olivier, Aurenhammer, Franz, Hackl, Thomas, Teillaud, Monique, Vogtenhuber, Birgit
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...
Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem (2008)
Aicholzer, Oswin, Devillers, Olivier, Aurenhammer, Franz, Hackl, Thomas, Teillaud, Monique, Vogtenhuber, Birgit
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...
Matching edges and faces in polygonal partitions (2008)
Aichholzer, Oswin, Aurenhammer, Franz, Gonzalez-Nava, Paola, Hackl, Thomas, Huerner, Clemens, Hurtado, Ferran, ...
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Gunter Rote, Triangulations Intersect Nicely, Oswin Aichholzer, Oswin Aichholzer, ...
We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other...
Towards Compatible Triangulations (2007)
Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado, Hannes Krasser
We state the following conjecture: any two planar n-point sets (that agree on the number of convex hull points) can be triangulated in a compatible manner, i.e., such that the resulting two planar...
O. Aichholzer, F. Aurenhammer, C. Huemer, H. Krasser, Oswin Aichholzer, Franz Aurenhammer, ...
Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T ′ of TS are adjacent if T intersects T ′ only in...
Forschungsschwerpunkt S, F. Aurenhammer, Franz Aurenhammer
We introduce the concept of weighted skeleton of a polygon and present various decomposition and optimality results for this skeletal structure when the underlying polygon is convex. 1
Transforming spanning trees and pseudo-triangulations (2006)
Oswin Aichholzer, Franz Aurenhammer, Clemens Huemer, Hannes Krasser
Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T ′ of TS are adjacent if T intersects T ′ only in...
O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, Oswin Aichholzer, Franz Aurenhammer, ...
We study the following Ramsey-type problem. Let S = B ∪ R be a two-colored set of n points in the plane. We show how to construct, in O(n log n) time, a crossing-free spanning tree T(B) for B, and...
Approximating uniform triangular meshes in polygons,” Theor (2002)
Franz Aurenhammer, Naoki Katoh, Hiromichi Kojima, Makoto Ohsaki, Yinfeng Xu
Given a convex polygon P in the plane and a positive integer n, weconsider the problem of generating a length-uniform triangular mesh for the interior of P using n Steiner points. More specifically,...
Convexity Minimizes Pseudo-Triangulations (2002)
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina Speckmann
The number of minimum pseudo-triangulations is minimized for point sets in convex position.
Approximating Uniform Triangular Meshes in Polygons (Algorithm Engineering as a New Paradigm) (1999)
Aurenhammer, Franz, Katoh, Naoki, Ohsaki, Makoto, Xu, Yin-Feng
Generalized self-approaching curves (1998)
Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, Günter Rote, ...
Abstract. We consider all planar oriented curves that have the following property depending on a fixed angle ϕ. ForeachpointB on the curve, the rest of the curve lies inside a wedge of angle ϕ with...
Generalized Self-Approaching Curves (1998)
Oswin Aichholzer, Oswin Aichholzer, Franz Aurenhammer, Franz Aurenhammer, Christian Icking, Christian Icking, ...
We consider all planar oriented curves that have the following property depending on a fixed angle '. For each point B on the curve, the rest of the curve lies inside a wedge of angle '...
Generalized Self-Approaching Curves (1998)
Spezialforschungsbereich F, Oswin Aichholzer, Oswin Aichholzer, Franz Aurenhammer, Franz Aurenhammer, Günter Rote, ...
We consider all planar oriented curves that have the following property depending on a #xed angle '. For each point B on the curve, the rest of the curve lies inside a wedge of angle ' with...
Straight Skeletons for General Polygonal Figures in the Plane (1996)
Oswin Aichholzer, Franz Aurenhammer
: A novel type of skeleton for general polygonal figures, the straight skeleton S(G) of a planar straight line graph G, is introduced and discussed. Exact bounds on the size of S(G) are derived. The...
Triangulations Intersect Nicely (1996)
Oswin Aichholzer, Oswin Aichholzer, Franz Aurenhammer, Franz Aurenhammer, Günter Rote, Michael Taschwer, ...
We show that there is a matching between the edges of anytwo triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other...
Constant-Level Greedy Triangulations Approximate the MWT Well (1995)
Diskrete Optimierung, O. Aichholzer, F. Aurenhammer, G. Rote, Oswin Aichholzer, ...
The well-known greedy triangulation GT (S) of a finite point set S is obtained by inserting compatible edges in increasing length order, where an edge is compatible if it does not cross previously...
Constant-Level Greedy Triangulations Approximate the MWT Well (1995)
O. Aichholzer, F. Aurenhammer, G. Rote, Oswin Aichholzer, Franz Aurenhammer, ...
The well-known greedy triangulation GT #S# of a #nite point set S is obtained by inserting compatible edges in increasing length order, where an edge is compatible if it does not cross previously...
Voronoi diagrams: A survey of a fundamental geometric data structure (1991)
This paper presents a survey of the Voronoi diagram, one of the most fundamental data structures in computational geometry. It demonstrates the importance and usefulness of the Voronoi diagram in a...
Forschungsschwerpunkt S, F. Aurenhammer, B. Jüttler, Franz Aurenhammer, Bert Jüttler
We utilize support functions to transform the problem of constructing the convex hull of a finite set of spherical objects into the problem of computing the upper envelope of piecewise linear...
Franz Aurenhammer, Rolf Klein, Praktische Informatik Vi
Voronoi diagrams can also be thought of as lower envelopes, in the sense mentioned at the beginning of this subsection. Namely, for each point x not situated on a bisecting curve, the relation p x q...