Modem Illumination of Monotone Polygons (2009)
Oswin Aichholzer, Ruy Fabila-monroy, David Flores-peñaloza, Thomas Hackl, Clemens Huemer, Jorge Urrutia, ...
We study a generalization of the classical problem of illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number k of...
Degree Bounds for Constrained Pseudo-triangulations (2009)
Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, Csaba D. Toth
We introduce the concept of a constrained pointed pseudo-triangulation T G of a point set S with respect to a pointed planar straight line graph G = (S, E). Forthe case that G forms a simple polygon...
Flipturning Polygons (Extended abstract) (2009)
Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Mark Overmars, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
Maximizing Maximal Angles for Plane Straight-Line Graphs ⋆ (2009)
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Attila Pór, Francisco Santos, ...
Abstract. Let G =(S, E) be a plane straight-line graph on a finite point set S ⊂ R 2 in general position. The incident angles of a point p ∈ S in G are the angles between any two edges of G that...
Flip Graphs of Degree-Bounded (Pseudo-)Triangulations (2009)
Aichholzer, Oswin, Hackl, Thomas, Orden, David, Ramos, Pedro, Rote, Günter, Schulz, André, ...
We study flip graphs of (pseudo-)triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider (pseudo-)triangulations of sets of n points in convex position in...
Games on Triangulations (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games—constructing, transforming, and marking...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
1 Introduction Let S be a set of n points in the plane, which we assume to be in general position, i.e., no threepoints of S lie on the same line. A triangulation of S is a simplicial decomposition...
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...
Abstract Degree Bounds for Constrained Pseudo-Triangulations (2008)
Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, Csaba D. Tóth
We introduce the concept of a constrained pointed pseudo-triangulation TG of a point set S with respect to a pointed planar straight line graph G =(S, E). For the case that G forms a simple polygon P...
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
Playing with Triangulations (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Geometric Games on Triangulations Extended Abstract (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Maximizing Maximal Angles for Plane Straight Line Graphs (2008)
Oswin Aichholzer, Thomas Hackl, Francisco Santos
Let G =(S, E) be a plane straight line graph on a finite point set S ⊂ R 2 in general position. For a point p ∈ S let the maximum incident angle of p in G be the maximum angle between any two...
Abstract Improved Upper Bounds on the Reflexivity of Point Sets (2008)
Eyal Ackerman, Oswin Aichholzer, Balázs Keszegh
Given a set S of n points in the plane, the reflexivity of S, ρ(S), is the minimum number of reflex vertices in a simple polygonalization of S. Arkin et al. [4] proved that ρ(S) ≤ ⌈n/2 ⌉ for...
Improved Upper Bounds on the Reflexivity of Point Sets (2008)
Eyal Ackerman, Oswin Aichholzer, Balázs Keszegh
Given a set S of n points in the plane, the reflexivity of S, ρ(S), is the minimum number of reflex vertices in a simple polygonalization of S. Arkin et al. [4] proved that ρ(S) ≤ ⌈n/2 ⌉ for...
Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferran Hurtado, Hannes Krasser
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane graphs and connected plane graphs as well as the...
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
Abstract Degree Bounds for Constrained Pseudo-Triangulations (2008)
Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, Csaba D. Tóth
We introduce the concept of a constrained pointed pseudo-triangulation TG of a point set S with respect to a pointed planar straight line graph G =(S, E). For the case that G forms a simple polygon P...
Abstract Pointed Drawings of Planar Graphs (2008)
Oswin Aichholzer, Günter Rote, André Schulz, Birgit Vogtenhuber
We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than π. In general a straight-line embedding cannot guarantee this property. We present...
Maximizing Maximal Angles for Plane Straight Line Graphs (2008)
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Francisco Santos
Let G =(S, E) be a plane straight line graph on a finite point set S ⊂ R 2 in general position. For a point p ∈ S let the maximum incident angle of p in G be the maximum angle between any two...
New results on lower bounds for the number of (at most k)-facets (2008)
Aichholzer, Oswin, García, Jesús, Orden, David, Ramos, Pedro
In this paper we present three different results dealing with the number of $(\leq k)$-facets of a set of points: 1. We give structural properties of sets in the plane that achieve the optimal lower...
Pointed Drawings of Planar Graphs (2008)
Oswin Aichholzer, Günter Rote, André Schulz, Birgit Vogtenhuber
We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than π. In general a straightline embedding cannot guarantee this property. We present...
ported by the Austrian FWF Joint Research Project ’Industrial Geometry ’ S9205-N12. (2008)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
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...
Playing with Triangulations (2007)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Flipturning Polygons* (Extended abstract) (2007)
Oswin Aichholzer, Carmen Corts, Erik D. Demaine, Vida Dujmovi, Jeff Ericksonll, Henk Meijer, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
Oswin Aichholzer, Erik D. Demaine, Je Erickson, Ferran Hurtado, Mark Overmars, Michael Soss, ...
We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Oswin Aichholzer, David Bremner, Erik D. Demaine, Henk Meijer, Michael Soss
We explore a problem suggested by Brian Hayes in 1998: what proteins in the twodimensional hydrophilic-hydrophobic (H-P) model have unique optimal foldings? In particular, we prove that there are...
Oswin Aichholzer, Ferran Hurtado, Marc Noy
We show that the number of straight line triangulations exhibited by any set of n points in general position in the plane is bounded from below by 45 + ") n) for some "> 0. To...
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...
A Lower Bound on the Number of Triangulations of Planar Point Sets (2007)
Oswin Aichholzer, Ferran Hurtado, Marc Noy
We show that the number of straight-edge triangulations exhibited by any set of n points in general position in the plane is bounded from below by 4 :33 ).
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
Maximizing Maximal Angles for Plane Straight-Line Graphs (2007)
Aichholzer, Oswin, Hackl, Thomas, Hoffmann, Michael, Huemer, Clemens, Por, Attila, Santos, Francisco, ...
Let $G=(S, E)$ be a plane straight-line graph on a finite point set $S\subset\R^2$ in general position. The \emph{incident angles} of a point $p \in S$ in $G$ are the angles between any two edges of...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
For information about obtaining copies of this volume contact (2007)
www.ub.tugraz.at/Verlag
On the number of pseudo-triangulations of certain point sets (2007)
Oswin Aichholzer, David Orden, Francisco Santos, Bettina Speckmann
We pose a monotonicity conjecture on the number of pseudo-triangulations of any planar point set, and check it on two prominent families of point sets, namely the so-called double circle and double...
On the number of pseudo-triangulations of certain point sets (2007)
Oswin Aichholzer, David Orden, Francisco Santos, Bettina Speckmann
We pose a monotonicity conjecture on the number of pseudo-triangulations of any planar point set, and check it in two prominent families of point sets, namely the so-called double circle and double...
Aichholzer, Oswin, García, Jesús, Orden, David, Ramos, Pedro
We provide a new lower bound on the number of $(\leq k)$-edges of a set of $n$ points in the plane in general position. We show that for $0 \leq k \leq\lfloor\frac{n-2}{2}\rfloor$ the number of...
On the Number of Pseudo-Triangulations of Certain Point Sets (2006)
Aichholzer, Oswin, Orden, David, Santos, Francisco, Speckmann, Bettina
We pose a monotonicity conjecture on the number of pseudo-triangulations of any planar point set, and check it on two prominent families of point sets, namely the so-called double circle and double...
On the number of plane graphs (2006)
Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, Birgit Vogtenhuber
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane graphs is minimized when S is in convex position,...
O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, B. Vogtenhuber, ...
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane geometric graphs and connected plane geometric...
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...
O. Aichholzer, F. Aurenhammer, T. Hackl, Oswin Aichholzer
FSP Report No. 6 Pre-triangulations and liftable
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...
New lower bounds for the number of (≤ k)-edges and the rectilinear crossing number of K_n (2006)
Oswin Aichholzer, Jesús García, David Orden, Pedro Ramos
We provide a new lower bound on the number of ( ≤ k)-edges of a set of n points in the plane in general position. We show that for 0 ≤ k ≤ ⌊ n−2 2 ⌋ the number of ( ≤ k)-edges is at...
The Zigzag Path of a Pseudo-Triangulation (2003)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudo-triangulation zigzag path allows us to use divide-and-conquer type...
The Zigzag Path of a Pseudo-Triangulation (2003)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
Abstract. We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudotriangulation zigzag path allows us to use...
The Zigzag Path of a Pseudo-Triangulation (2003)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
Abstract. We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudotriangulation zigzag path allows us to use...
Degree bounds for constrained pseudo-triangulations (2003)
Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, Csaba D. Tóth
We introduce the concept of a constrained pointed pseudo-triangulation TG of a point set S with respect to a pointed planar straight line graph G =(S, E). For the case that G forms a simple polygon P...
Long Proteins with Unique Optimal Foldings in the H-P Model (2002)
Aichholzer, Oswin, Bremner, David, Demaine, Erik D., Meijer, Henk, Sacristán, Vera, Soss, Michael
It is widely accepted that (1) the natural or folded state of proteins is a global energy minimum, and (2) in most cases proteins fold to a unique state determined by their amino acid sequence. The...
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.
Aichholzer, Oswin, Cortes, Carmen, Demaine, Erik D., Dujmovic, Vida, Erickson, Jeff, Meijer, Henk, ...
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hull edge. Joss and...
Reconfiguring Convex Polygons (2000)
Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, ...
. We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
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...
A Simple Linear Time Greedy Triangulation Algorithm for Uniformly Distributed Points (1995)
this paper we present a simple, practical algorithm that computes the greedy triangulation in expected time O(n) and space O(n), for n points drawn independently from a uniform distribution over some...
A Simple Linear Time Greedy Triangulation Algorithm for Uniformly Distributed Points (1995)
this paper we present a simple, practical algorithm that computes the greedy triangulation in expected time O#n# and space O#n#, for n points drawn independently from a uniform distribution over some...
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...
Matching Shapes with a Reference Point (1994)
Helmut Alt, Oswin Aichholzer, Günter Rote
For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the...
Matching Shapes with a Reference Point (1994)
Helmut Alt, Oswin Aichholzer, Günter Rote
For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the...
Degree Bounds for Constrained Pseudo-Triangulations
Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, Csaba D. Toth
We introduce the concept of a constrained pointed pseudo-triangulation T_G of a point set S with respect to a pointed planar straight line graph G = (S, E). For the case that G forms a simple polygon...