@headline{art, note = "Journal articles"}
@Article{aaahjpr-dcvdr-10,
author = {O. Aichholzer and W. Aigner and F. Aurenhammer and T.
Hackl and B. J\"uttler and E. Pilgerstorfer and M. Rabl},
title = {Divide-and-conquer for {V}oronoi diagrams revisited},
journal = {Computational Geometry: Theory and Applications},
volume = {to appear},
number = {},
pages = {},
year = 2010,
abstract = {We show how to divide the edge graph of a Voronoi diagram
into a tree that corresponds to the medial axis of an
(augmented) planar domain. Division into base cases is then
possible, which, in the bottom-up phase, can be merged by
trivial concatenation. The resulting construction
algorithm---similar to Delaunay triangulation methods---is
not bisector-based and merely computes dual links between
the sites, its atomic steps being inclusion tests for sites
in circles. This guarantees computational simplicity and
numerical stability. Moreover, no part of the Voronoi
diagram, once constructed, has to be discarded again. The
algorithm works for polygonal and curved objects as sites
and, in particular, for circular arcs which allows its
extension to general free-form objects by Voronoi diagram
preserving and data saving biarc approximations. The
algorithm is randomized, with expected runtime $O(n\logn)$
under certain assumptions on the input data. Experiments
substantiate an efficient behavior even when these
assumptions are not met. Applications to offset
computations and motion planning for general objects are
described.}
}
@Article{aahjos-csacb-09,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
J\"uttler and M.Oberneder and Z. S\'ir},
title = {Computational and Structural Advantages of Circular
Boundary Representation},
journal = {Int'l. Journal of Computational Geometry \& Applications},
year = 2010,
volume = {accepted},
number = {},
pages = {},
abstract = {Boundary approximation of planar shapes by circular arcs
has quantitive and qualitative advantages compared to using
straight-line segments. We demonstrate this by way of three
basic and frequent computations on shapes -- convex hull,
decomposition, and medial axis. In particular, we propose a
novel medial axis algorithm that beats existing methods in
simplicity and practicality, and at the same time
guarantees convergence to the medial axis of the original
shape.}
}
@Article{acffhhhw-erncc-09,
author = {O. Aichholzer and S. Cabello and R. Fabila-Monroy and D.
Flores-Pe{\~n}aloza and T. Hackl and C. Huemer and F.
Hurtado and D.R. Wood},
title = {Edge-Removal and Non-Crossing Configurations in Geometric
Graphs},
journal = {Discrete Mathematics \& Theoretical Computer Science
(DMTCS)},
year = 2010,
volume = {accepted},
number = {},
pages = {},
abstract = {We study the following extremal problem for geometric
graphs: How many arbitrary edges can be removed from a
complete geometric graph with $n$ vertices such that the
remaining graph still contains a certain non-crossing
subgraph. In particular we consider perfect matchings and
subtrees of a given size. For both classes of geometric
graphs we obtain tight bounds on the maximum number of
removable edges. We further present several conjectures and
bounds on the number of removable edges for other classes
of non-crossing geometric graphs.}
}
@Article{ahhhv-lbpsa-09b,
author = {O.~Aichholzer and T.~Hackl and C.~Huemer and F.~Hurtado
and B.~Vogtenhuber},
title = {Large bichromatic point sets admit empty monochromatic
$4$-gons},
year = 2010,
journal = {SIAM Journal on Discrete Mathematics (SIDMA)},
volume = {23},
number = {4},
pages = {2147--2155},
doi = {http://dx.doi.org/10.1137/090767947},
abstract = {We consider a variation of a problem stated by Erd\"os and
Szekeres in 1935 about the existence of a number
$f^\textrm{ES}(k)$ such that any set $S$ of at least
$f^\textrm{ES}(k)$ points in general position in the plane
has a subset of $k$ points that are the vertices of a
convex $k$-gon. In our setting the points of $S$ are
colored, and we say that a (not necessarily convex) spanned
polygon is monochromatic if all its vertices have the same
color. Moreover, a polygon is called empty if it does not
contain any points of $S$ in its interior. We show that any
bichromatic set of $n \geq 5044$ points in $\mathcal{R}^2$
in general position determines at least one empty,
monochromatic quadrilateral (and thus linearly many).}
}
@Article{aj-cchps-07,
author = {F. Aurenhammer and B. J{\"u}ttler},
title = {On computing the convex hull of (piecewise) spherical
objects},
journal = {submitted to journal},
volume = {},
number = {},
pages = {},
year = {2010}
}
@Article{aak-iubrp-08,
author = {E. Ackerman and O. Aichholzer and B. Keszegh},
title = {Improved Upper Bounds on the Reflexivity of Point Sets},
year = 2009,
journal = {Computational Geometry: Theory and Applications},
volume = {42},
pages = {241--249},
abstract = {Given a set $S$ of $n$ points in the plane, the
\emph{reflexivity} of $S$, $\rho(S)$, is the minimum number
of reflex vertices in a simple polygonalization of $S$.
Arkin et al. proved that $\rho(S) \le n/2$ for any set $S$,
and conjectured that the tight upper bound is $n/4$. We
show that the reflexivity of any set of $n$ points is at
most $\frac{3}{7}n + O(1) \approx 0.4286n$. Using
computer-aided abstract order type extension the upper
bound can be further improved to $\frac{5}{12}n + O(1)
\approx 0.4167n$.}
}
@Article{aaahjr-macpf-08,
author = {O. Aichholzer and W. Aigner and F. Aurenhammer and T.
Hackl and B. J{\"u}ttler and M. Rabl},
title = {Medial Axis Computation for Planar Free-Form Shapes},
journal = {Computer-Aided Design},
note = {Special issue: {V}oronoi Diagrams and their Applications},
year = 2009,
volume = {41},
number = {5},
doi = {http://dx.doi.org/10.1016/j.cad.2008.08.008},
pages = {339--349},
abstract = {We present a simple, efficient, and stable method for
computing---with any desired precision---the medial axis of
simply connected planar domains. The domain boundaries are
assumed to be given as polynomial spline curves. Our
approach combines known results from the field of geometric
approximation theory with a new algorithm from the field of
computational geometry. Challenging steps are (1) the
approximation of the boundary spline such that the medial
axis is geometrically stable, and (2) the efficient
decomposition of the domain into base cases where the
medial axis can be computed directly and exactly. We solve
these problems via spiral biarc approximation and a
randomized divide \& conquer algorithm.}
}
@Article{aahs-mwpt-08,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
Speckmann},
title = {On Minimum Weight Pseudo-Triangulations},
journal = {Computational Geometry: Theory and Applications},
pages = {627--631},
volume = {42},
number = {6-7},
year = 2009,
abstract = {In this note we discuss some structural properties of
minimum weight pseudo-triangulations of point sets.}
}
@Article{abdgh-cgm-08b,
author = {O. Aichholzer and S. Bereg and A. Dumitrescu and A.
Garc\'{\i}a and C. Huemer and F. Hurtado and M. Kano and A.
M{\'a}rquez and D. Rappaport and S. Smorodinsky and D.
Souvaine and J. Urrutia and D. Wood},
title = {Compatible Geometric Matchings},
year = 2009,
volume = {42},
number = {6-7},
journal = {Computational Geometry: Theory and Applications},
pages = {617--626},
abstract = {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 result states that for any
two perfect matchings $M$ and $M'$ of the same set of $n$
points, for some $k \in O(log n)$, there is a sequence of
perfect matchings $M = M_0,M_1, . . . ,M_k = M'$, such that
each $M_i$ is compatible with $M_{i+1}$. This improves the
previous best bound of $k \leq n-2$. We then study the
conjecture: every perfect matching with an even number of
edges has an edge-disjoint compatible perfect matching. We
introduce a sequence of stronger conjectures that imply
this conjecture, and prove the strongest of these
conjectures in the case of perfec matchings that consist of
vertical and horizontal segments. Finally, we prove that
every perfect matching with $n$ edges has an edge-disjoint
compatible matching with approximately $4n/5$ edges. }
}
@Article{affhhu-emt-09,
author = {O. Aichholzer and R. Fabila-Monroy and D.
Flores-Pe{\~n}aloza and T. Hackl and C. Huemer and J.
Urrutia},
title = {Empty Monochromatic Triangles},
year = 2009,
journal = {Computational Geometry: Theory and Applications},
volume = {42},
number = {9},
pages = {934--938},
doi = {http://dx.doi.org/10.1016/j.comgeo.2009.04.002},
abstract = {We consider a variation of a problem stated by Erd\"os and
Guy in 1973 about the number of convex $k$-gons determined
by any set $S$ of $n$ points in the plane. In our setting
the points of $S$ are colored and we say that a spanned
polygon is monochromatic if all its points are colored with
the same color. As a main result we show that any
bi-colored set of $n$ points in $\mathcal{R}^2$ in general
position determines a super-linear number of empty
monochromatic triangles, namely $\Omega(n^{5/4})$.}
}
@Article{agor-nrlbn-07,
author = {O. Aichholzer and J. Garc\'{\i}a and D. Orden and P.A.
Ramos},
title = {New results on lower bounds for the number of~$(\leq
k)$-facets},
journal = {European Journal of Combinatorics},
year = 2009,
volume = {30},
number = {},
pages = {1568--1574},
abstract = {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 bound $3{k+2 \choose 2}$ of
$(\leq k)$-edges for a fixed $k\leq \lfloor n/3 \rfloor
-1$; (2) We show that the lower bound $3{k+2 \choose
2}+3{k-\lfloor \frac{n}{3} \rfloor+2 \choose 2}$ for the
number of $(\leq k)$-edges of a planar point set is optimal
in the range $\lfloor n/3 \rfloor \leq k \leq \lfloor 5n/12
\rfloor -1$; (3) We show that, for $k < n/4$, the number of
$(\leq k)$-facets a set of $n$ points in $\mathbb{R}^3$ in
general position is at least $4{k+3 \choose 3}$, and that
this bound is tight in that range.}
}
@Article{aaghhhkrv-mefpp-06,
author = {O. Aichholzer and F. Aurenhammer and P. Gonzalez-Nava and
T. Hackl and C. Huemer and F. Hurtado and H. Krasser and S.
Ray and B. Vogtenhuber},
title = {Matching Edges and Faces in Polygonal Partitions},
journal = {Computational Geometry: Theory and Applications},
pages = {134--141},
volume = {39(2)},
year = 2008,
abstract = {We define general Laman (count) conditions for edges and
faces of polygonal partitions in the plane. Several
well-known classes, including $k$-regular partitions,
$k$-angulations, and rank $k$ pseudo-triangulations, are
shown to fulfill such conditions. As a consequence
non-trivial perfect matchings exist between the edge sets
(or face sets) of two such structures when they live on the
same point set. We also describe a link to spanning tree
decompositions that applies to quadrangulations and certain
pseudo-triangulations.}
}
@Article{abdgh-cgm-08c,
author = {O. Aichholzer and S. Bereg and A. Dumitrescu and A.
Garc\'{i}a and C. Huemer and F. Hurtado and M. Kano and A.
M\'{a}rquez and D. Rappaport and S. Smorodinsky and D.
Souvaine and J. Urrutia and D. Wood},
title = {Compatible Geometric Matchings},
year = 2008,
volume = {31},
numer = {},
journal = {Electronic Notes in Discrete Mathematics},
pages = {201--206},
abstract = {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 result states that for any
two perfect matchings $M$ and $M'$ of the same set of $n$
points, for some $k \in O(log n)$, there is a sequence of
perfect matchings $M = M_0,M_1, . . . ,M_k = M'$, such that
each $M_i$ is compatible with $M_{i+1}$. This improves the
previous best bound of $k \leq n-2$. We then study the
conjecture: every perfect matching with an even number of
edges has an edge-disjoint compatible perfect matching. We
introduce a sequence of stronger conjectures that imply
this conjecture, and prove the strongest of these
conjectures in the case of perfec matchings that consist of
vertical and horizontal segments. Finally, we prove that
every perfect matching with $n$ edges has an edge-disjoint
compatible matching with approximately $4n/5$ edges. }
}
@Article{ahk-twpst-07,
author = {O. Aichholzer and C. Huemer and H. Krasser},
title = {Triangulations Without Pointed Spanning Trees},
year = 2008,
volume = {40},
numer = {1},
journal = {Computational Geometry: Theory and Applications},
pages = {79--83},
abstract = {Problem $50$ in the Open Problems Project~\cite{OPP} 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. }
}
@Article{aoss-nptcp-07,
author = {O. Aichholzer and D. Orden and F. Santos and B.
Speckmann},
title = {On the Number of Pseudo-Triangulations of Certain Point
Sets},
journal = {Journal of Combinatorial Theory, Series A},
year = 2008,
volume = {115(2)},
pages = {254--278},
abstract = {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 chain. The latter has
asymptotically $12^n n^{\Theta(1)}$ pointed
pseudo-triangulations, which lies significantly above the
maximum number of triangulations in a planar point set
known so far.}
}
@Article{aah-ptlc-06a,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl},
title = {Pre-triangulations and liftable complexes},
journal = {Discrete \& Computational Geometry},
year = 2007,
volume = {38},
number = {},
pages = {701--725},
abstract = {We introduce the concept of pre-triangulations, a
relaxation of triangulations that goes beyond the
frequently used concept of pseudo-triangulations.
Pre-triangulations turn out to be more natural than
pseudo-triangulations in certain cases. We show that
pre-triangulations arise in three different contexts: In
the characterization of polygonal complexes that are
liftable to three-space in a strong sense, in flip
sequences for general polygonal complexes, and as graphs of
maximal locally convex functions.}
}
@Article{aahh-ccps-06,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and
C. Huemer},
title = {Connecting Colored Point Sets},
journal = {Discrete Applied Mathematics},
year = 2007,
volume = {155},
number = {3},
pages = {271--278},
htmlnote = {Also available as FSP-report S092-45, Austria, 2006, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {We study the following Ramsey-type problem. Let \mbox{$S =
B \cup R$} be a two-colored set of $n$ points in the plane.
We show how to construct, in \mbox{$O(n \log n)$} time, a
crossing-free spanning tree $T(R)$ for~$R$, and a
crossing-free spanning tree $T(B)$ for~$B$, such that both
the number of crossings between $T(R)$ and $T(B)$ and the
diameters of~$T(R)$ and $T(B)$ are kept small. The
algorithm is conceptually simple and is implementable
without using any non-trivial data structure. This improves
over a previous method in Tokunaga~\cite{T} that is less
efficient in implementation and does not guarantee a
diameter bound. }
}
@Article{aahv-gceps-07,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and B.
Vogtenhuber},
title = {Gray code enumeration of plane straight-line graphs},
journal = {Graphs and Combinatorics (Springer)},
pages = {467--479},
volume = {23(5)},
year = 2007,
abstract = {We develop Gray code enumeration schemes for geometric
straight-line graphs in the plane. The considered graph
classes include plane graphs, connected plane graphs, and
plane spanning trees. Previous results were restricted to
the case where the underlying vertex set is in convex
position.}
}
@Article{agor-nlbnk-06,
author = {O. Aichholzer and J. Garc\'{i}a and D. Orden and P.A.
Ramos},
title = {New lower bounds for the number of $(\leq k)$-edges and
the rectilinear crossing number of $K_n$},
journal = {Discrete \& Computational Geometry},
year = 2007,
volume = {38},
pages = {1--14},
htmlnote = {Also available as FSP-report S092-20, Austria, 2006, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {We provide a new lower bound on the number of~$(\leq
k)$-edges on 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~$(\leq k)$-edges
is at least $ E_k(S) \geq 3 {k+2 \choose 2} +
\sum_{j=\lfloor\frac{n}{3}\rfloor}^k (3j-n+3)$, which, for
$k\geq \lfloor \frac{n}{3}\rfloor$, improves the previous
best lower bound.\\ As a main consequence, we obtain a new
lower bound on the rectilinear crossing number of the
complete graph or, in other words, on the minimum number of
convex quadrilaterals determined by~$n$ points in the plane
in general position. We show that the crossing number is at
least $ \left(\frac{41}{108}+\varepsilon \right) {n \choose
4} + O(n^3) \geq 0.379631 {n \choose 4} + O(n^3)$, which
improves the previous bound of~$0.37533 {n \choose 4} +
O(n^3)$ and approaches the best known upper bound $0.38058
{n \choose 4}$.\\ The proof is based on a result about the
structure of sets attaining the rectilinear crossing
number, for which we show that the convex hull is always a
triangle.\\ Further implications include improved results
for small values of $n$. We extend the range of known
values for the rectilinear crossing number, namely by
$cr(K_{19})=1318$ and $cr(K_{21})=2055$. Moreover we
provide improved upper bounds on the maximum number $h_n$
of halving edges a point set can have. }
}
@Article{ahhhkv-npg-06a,
author = {O. Aichholzer and T. Hackl and C. Huemer and F. Hurtado
and H. Krasser and B. Vogtenhuber},
title = {On the number of plane geometric graphs},
journal = {Graphs and Combinatorics (Springer)},
pages = {67--84},
volume = {23(1)},
year = 2007,
abstract = {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 graphs as well as the number
of cycle-free plane geometric graphs is minimized when $S$
is in convex position. Moreover, these results hold for all
these graphs with an arbitrary but fixed number of edges.
Consequently, we provide a unified proof that the
cardinality of any family of acyclic graphs (for example
spanning trees, forests, perfect matchings, spanning paths,
and more) is minimized for point sets in convex position.
In addition we construct a new extremal configuration, the
so-called double zig-zag chain. Most noteworthy this
example bears $\Theta^*(\sqrt{72}\,^n)$ =
$\Theta^*(8.4853^n)$ triangulations and
$\Theta^*(41.1889^n)$ plane graphs (omitting polynomial
factors in both cases), improving the previously known best
maximizing examples.}
}
@Article{ahkst-pcdpc-07,
author = {O. Aichholzer and C. Huemer and S. Kappes and B. Speckmann
and C. D. T\'oth},
title = {Decompositions, Partitions, and Coverings with Convex
Polygons and Pseudo-Triangles},
journal = {Graphs and Combinatorics},
year = 2007,
volume = {23(5)},
pages = {481--507},
abstract = {We propose a novel subdivision of the plane that consists
of both convex polygons and pseudo-triangles. This
pseudo-convex decomposition is significantly sparser than
either convex decompositions or pseudo-triangulations for
planar point sets and simple polygons. We also introduce
pseudo-convex partitions and coverings. We establish some
basic properties and give combinatorial bounds on their
complexity. Our upper bounds depend on new Ramsey-type
results concerning disjoint empty convex k-gons in point
sets.}
}
@Article{ar-qdbsb-05,
author = {O. Aichholzer and K. Reinhardt},
title = {A quadratic distance bound on sliding between
crossing-free spanning trees},
year = 2007,
journal = {Computational Geometry: Theory and Applications, special
issue},
pages = {155-161},
volume = {37},
abstract = {Let $S$ be a set of $n$ points in the plane and let
${\mathcal T}_S$ be the set of all crossing-free spanning
trees of $S$. We show that any two trees in ${\mathcal
T}_S$ can be transformed into each other by $O(n^2)$ local
and constant-size edge slide operations. No polynomial
upper bound for this task has been known, but in~\cite{AAH}
a bound of $O(n^2 \log n)$ operations was conjectured.}
}
@Article{a-wsfsd-07,
author = {F. Aurenhammer},
title = {Weighted skeletons and fixed-share decomposition},
journal = {Computational Geometry: Theory and Applications},
year = 2007,
pages = {93-101},
volume = {40},
}
@InCollection{ax-ot-07,
author = {F. Aurenhammer and Y.-F.Xu},
title = {Optimal triangulations},
booktitle = {Encyclopedia of Optimization, Second Edition},
publisher = {Kluwer Academic Publishing},
editor = {C.A.Floudas, P.M.Pardalos},
year = {2007}
}
@Article{aahk-tstpt-05b,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and H.
Krasser},
title = {Transforming Spanning Trees and Pseudo-Triangulations},
journal = {Information Processing Letters (IPL)},
year = 2006,
volume = {97(1)},
pages = {19--22},
abstract = {Let $T_{S}$ be the set of all crossing-free straight line
spanning trees of a planar $n$-point set~$S$. Consider the
graph ${\cal T}_S$ where two members $T$ and $T'$ of
$T_{S}$ are adjacent if $T$ intersects $T'$ only in points
of~$S$ or in common edges. We prove that the diameter
of~${\cal T}_S$ is $O(\log k)$, where $k$ denotes the
number of convex layers of $S$. Based on this result, we
show that the flip graph~${\cal P}_S$ of
pseudo-triangulations of~$S$ (where two
pseudo-triangulations are adjacent if they differ in
exactly one edge -- either by replacement or by removal)
has a dia\-meter of $O(n \log k)$. This sharpens a known
$O(n \log n)$ bound. Let~${\cal \widehat{P}}_S$ be the
induced subgraph of pointed pseudo-triangulations of~${\cal
P}_S$. We present an example showing that the distance
between two nodes in~${\cal \widehat{P}}_S$ is strictly
larger than the distance between the corresponding nodes
in~${\cal P}_S$. }
}
@Article{aak-cncg-05,
author = {O. Aichholzer and F. Aurenhammer and H. Krasser},
title = {On the Crossing Number of Complete Graphs},
year = 2006,
journal = {Computing},
volume = 76,
pages = {165--176},
abstract = { Let $\overline{cr}(G)$ denote the rectilinear crossing
number of a graph~$G$. We determine
$\overline{cr}(K_{11})=102$ and
$\overline{cr}(K_{12})=153$. Despite the remarkable hunt
for crossing numbers of the complete graph~$K_n$ --
initiated by R.~Guy in the 1960s -- these quantities have
been unknown for \mbox{$n>10$} to~date. Our solution mainly
relies on a tailor-made method for enumerating all
inequivalent sets of points (order types) of size~$11$.
Based on these findings, we establish a new upper bound on
$\overline{cr}(K_{n})$ for general~$n$. The bound stems
from a novel construction of drawings of $K_{n}$ with few
crossings.}
}
@Article{ak-aoten-06,
author = {O. Aichholzer and H. Krasser},
title = {Abstract Order Type Extension and New Results on the
Rectilinear Crossing Number},
year = 2006,
journal = {Computational Geometry: Theory and Applications, Special
Issue on the 21st European Workshop on Computational
Geometry},
volume = {36},
number = {1},
pages = {2--15},
abstract = {We extend the order type data base of all realizable order
types in the plane to point sets of cardinality 11. More
precisely, we provide a complete data base of all
combinatorial different sets of up to 11 points in general
position in the plane. In addition, we develop a novel and
efficient method for a complete extension to order types of
size 12 and more in an abstract sense, that is, without the
need to store or realize the sets. The presented method is
well suited for independent computations. Thus, time
intensive investigations benefit from the possibility of
distributed computing.\\ Our approach has various
applications to combinatorial problems which are based on
sets of points in the plane. This includes classic problems
like searching for (empty) convex k-gons (´happy end
problem´), decomposing sets into convex regions, counting
structures like triangulations or pseudo-triangulations,
minimal crossing numbers, and more. We present some
improved results to several of these problems. As an
outstanding result we have been able to determine the exact
rectilinear crossing number of the complete graph $K_n$ for
up to $n=17$, the largest previous range being $n=12$, and
slightly improved the asymptotic upper bound. }
}
@Article{adk-flsvd-06,
author = {F. Aurenhammer and R.L.S.Drysdale and H. Krasser},
title = {Farthest line segment {V}oronoi diagrams},
journal = {Information Processing Letters},
year = 2006,
pages = {220--225},
volume = {100}
}
@Article{ak-psclcf-06,
author = {F. Aurenhammer and H. Krasser},
title = {Pseudo-simplicial complexes from maximal locally convex
functions},
journal = {Discrete \& Computional Geometry},
year = 2006,
pages = {201--221},
volume = 35
}
@headline{proc, note = "Refereed articles in books and conference proceedings"}
@InProceedings{a-ecgrr-09,
author = {O. Aichholzer},
title = {[{E}mpty] [colored] $k$-gons - {R}ecent results on some
{E}rd\"os-{S}zekeres type problems},
booktitle = {Proc. XIII Encuentros de Geometr\'{\i}a Computacional},
pages = {43--52},
year = 2009,
address = {Zaragoza, Spain},
abstract = {We consider a family of problems which are based on a
question posed by Erd\H{o}s and Szekeres in 1935: ``What is
the smallest integer $g(k)$ such that any set of $g(k)$
points in the plane contains at least one convex $k$-gon?''
In the mathematical history this has become well known as
the ``Happy End Problem''. There are several variations of
this problem: The $k$-gons might be required to be empty,
that is, to not contain any points of the set in their
interior. In addition the points can be colored, and we
look for monochromatic $k$-gons, meaning polygons spanned
by points of the same color. Beside the pure existence
question we are also interested in the asymptotic behavior,
for example whether there are super-linear many $k$-gons of
some type. And finally, for several of these problems even
small non-convex $k$-gons are of interest. We will survey
recent progress and discuss open questions for this class
of problems.}
}
@InProceedings{aaahjpr-dcvdr-09b,
author = {O. Aichholzer and W.~Aigner and F. Aurenhammer and
T.~Hackl and B.~J{\"u}ttler and E.~Pilgerstorfer and
M.~Rabl},
title = {Divide-and-Conquer for Voronoi Diagrams Revisited},
booktitle = {$25^{th}$ Ann. ACM Symp. Computational Geometry},
pages = {189--197},
year = 2009,
address = {Aarhus, Denmark},
abstract = {We propose a simple and practical divide-and-conquer
algorithm for constructing planar Voronoi diagrams. The
novel aspect of the algorithm is its emphasis on the
top-down phase, which makes it applicable to sites of
general shape.}
}
@InProceedings{aaahjpr-dcvdr-09,
author = {O. Aichholzer and W.~Aigner and F. Aurenhammer and
T.~Hackl and B.~J{\"u}ttler and E.~Pilgerstorfer and
M.~Rabl},
title = {Divide-and-Conquer for Voronoi Diagrams Revisited},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
pages = {293--296},
year = 2009,
address = {Brussels, Belgium},
abstract = {We propose a simple and practical divide-and-conquer
algorithm for constructing planar Voronoi diagrams. The
novel aspect of the algorithm is its emphasis on the
top-down phase, which makes it applicable to sites of
general shape.}
}
@InProceedings{aadhtv-lubne-09,
author = {O. Aichholzer and F. Aurenhammer and O.~Devillers and
T.~Hackl and M.~Teillaud and B.~Vogtenhuber},
title = {Lower and upper bounds on the number of empty cylinders
and ellipsoids},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
pages = {139--142},
year = 2009,
address = {Brussels, Belgium},
abstract = {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. Among various results
we prove that the number of empty circular cylinders is
between $\Omega(n^3)$ and $O(n^4)$ while we have a tight
bound $\Theta(n^4)$ for empty ellipsoids. We also take
interest in pairs of empty homothetic ellipsoids, with
application to the number of combinatorially distinct
Delaunay triangulations obtained by orthogonal projections
of $\cal S$ on a two-dimensional plane, which is
$\Omega(n^4)$ and $O(n^5)$.
A side result is that the convex hull in $d$ dimensions of
a set of $n$ points, where one half lies in a subspace of
odd dimension~\mbox{$\delta > \frac{d}{2}$}, and the second
half is the (multi-dimensional) projection of the first
half on another subspace of dimension~$\delta$, has
complexity only $O\left(n^{\frac{d}{2}-1}\right)$.}
}
@InProceedings{aahru-tcp-09,
author = {O. Aichholzer and F. Aurenhammer and F.~Hurtado and
P.~Ramos and J.~Urrutia},
title = {Two-Convex Polygons},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
pages = {117--120},
year = 2009,
address = {Brussels, Belgium},
abstract = {We introduce a notion of $k$-convexity and explore some
properties of polygons that have this property. In
particular, \mbox{$2$-convex} polygons can be recognized in
\mbox{$O(n \log n)$} time, and \mbox{$k$-convex} polygons
can be triangulated in $O(kn)$ time.}
}
@InProceedings{aahkprsv-rsrso-09,
author = {O. Aichholzer and F. Aurenhammer and B. Kornberger and S.
Plantinga and G. Rote and A. Sturm and G. Vegter},
title = {Recovering Structure from r-Sampled Objects},
booktitle = {Eurographics Symposium on Geometry Processing, special
issue of Computer Graphics Forum 28(5)},
pages = {1349--1360},
year = 2009,
address = {Berlin, Germany},
abstract = {For a surface~$F$ in 3-space that is represented by a
set~$S$ of sample points, we construct a coarse
approximating polytope $P$ that uses a subset of~$S$ as its
vertices and preserves the topology of~$F$. In contrast to
surface reconstruction we do not use all the sample points,
but we try to use as few points as possible. Such a
polytope~$P$ is useful as a `seed polytope' for starting an
incremental refinement procedure to generate better and
better approximations of $F$ based on interpolating
subdivision surfaces or e.g. B\'ezier patches.
Our algorithm starts from an \mbox{$r$-sample} $S$ of $F$.
Based on $S$, a set of surface covering balls with maximal
radii is calculated such that the topology is retained.
From the weighted $\alpha$-shape of a proper subset of
these highly overlapping surface balls we get the desired
polytope. As there is a rather large range for the possible
radii for the surface balls, the method can be used to
construct triangular surfaces from point clouds in a
scalable manner. We also briefly sketch how to combine
parts of our algorithm with existing medial axis algorithms
for balls, in order to compute stable medial axis
approximations with scalable level of detail.}
}
@InProceedings{affhhuv-mimp-09,
author = {O. Aichholzer and R.~Fabila-Monroy and
D.~Flores-Pe{\~n}aloza and T.~Hackl and C.~Huemer and
J.~Urrutia and B.~Vogtenhuber},
title = {Modem Illumination of Monotone Polygons},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
pages = {167--170},
year = 2009,
address = {Brussels, Belgium},
abstract = {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 walls. We call these
objects $k$-modems and study the minimum number of
$k$-modems necessary to illuminate monotone and monotone
orthogonal polygons. We show that every monotone polygon on
$n$ vertices can be illuminated with $\left\lceil
\frac{n}{2k} \right\rceil$ $k$-modems and exhibit examples
of monotone polygons requiring $\left\lceil \frac{n}{2k+2}
\right\rceil$ $k$-modems. For monotone orthogonal polygons,
we show that every such polygon on $n$ vertices can be
illuminated with $\left\lceil \frac{n}{2k+4} \right\rceil$
$k$-modems and give examples which require $\left\lceil
\frac{n}{2k+4} \right\rceil$ $k$-modems for $k$ even and
$\left\lceil \frac{n}{2k+6} \right\rceil$ for $k$ odd.}
}
@InProceedings{ahhprsv-pgpc-09,
author = {O. Aichholzer and T. Hackl and M.~Hoffmann and A.~Pilz and
G.~Rote and B.~Speckmann and B.~Vogtenhuber},
title = {Plane Graphs with Parity Constraints},
booktitle = {Lecture Notes in Computer Science, Proc. 11th
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {5664},
address = {Banff, Alberta, Canada},
pages = {13--24},
year = 2009,
abstract = {Let $S$ be a set of $n$ points in general position in the
plane. Together with $S$ we are given a set of parity
constraints, that is, every point of $S$ is labeled either
even or odd. A graph $G$ on $S$ satisfies the parity
constraint of a point $p \in S$, if the parity of the
degree of $p$ in $G$ matches its label. In this paper we
study how well various classes of planar graphs can satisfy
arbitrary parity constraints. Specifically, we show that we
can always find a plane tree, a two-connected outerplanar
graph, or a pointed pseudo-triangulation which satisfy all
but at most three parity constraints. With triangulations
we can satisfy about 2/3 of all parity constraints. In
contrast, for a given simple polygon $H$ with polygonal
holes on $S$, we show that it is NP-complete to decide
whether there exists a triangulation of $H$ that satisfies
all parity constraints.}
}
@InProceedings{ahhhv-lbpsa-09,
author = {O.~Aichholzer and T.~Hackl and C.~Huemer and F.~Hurtado
and B.~Vogtenhuber},
title = {Large bichromatic point sets admit empty monochromatic
$4$-gons},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
pages = {133--136},
year = 2009,
address = {Brussels, Belgium},
abstract = {We consider a variation of a problem stated by Erd\"os and
Szekeres in 1935 about the existence of a number
$f^\textrm{ES}(k)$ such that any set $S$ of at least
$f^\textrm{ES}(k)$ points in general position in the plane
has a subset of $k$ points that are the vertices of a
convex $k$-gon. In our setting the points of $S$ are
colored, and we say that a (not necessarily convex) spanned
polygon is monochromatic if all its vertices have the same
color. Moreover, a polygon is called empty if it does not
contain any points of $S$ in its interior. We show that any
bichromatic set of $n \geq 5044$ points in $\mathcal{R}^2$
in general position determines at least one empty,
monochromatic quadrilateral (and thus linearly many).}
}
@InProceedings{ahorrss-fgbdt-09,
author = {O.~Aichholzer and T.~Hackl and D.~Orden and P.~Ramos and
G.~Rote and A.~Schulz and B.~Speckmann},
title = {Flip Graphs of Bounded-Degree Triangulations},
booktitle = {Electronic Notes in Discrete Mathematics: Proc. European
Conference on Combinatorics, Graph Theory and Applications
EuroComb 2009},
volume = {34},
pages = {509--513},
year = 2009,
address = {Bordeaux, France},
abstract = {We study flip graphs of triangulations whose maximum
vertex degree is bounded by a constant $k$. Specifically,
we consider triangulations of sets of $n$ points in convex
position in the plane and prove that their flip graph is
connected if and only if $k > 6$; the diameter of the flip
graph is $O(n^2)$. We also show that for general point
sets, flip graphs of triangulations with degree $\leq k$
can be disconnected for any $k$.}
}
@InProceedings{aahkprsv-spia-08,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
Kornberger and S. Plantinga and G. Rote and A. Sturm and G.
Vegter},
title = {Seed Polytopes for Incremental Approximation},
booktitle = {Proc. $24^{th}$ European Workshop on Computational
Geometry EuroCG '08},
pages = {13--16},
year = 2008,
address = {Nancy, France},
abstract = {Approximating a given three-dimensional object in order to
simplify its handling is a classical topic in computational
geometry and related fields. A typical approach is based on
incremental approximation algorithms, which start with a
small and topologically correct polytope representation
(the seed polytope) of a given sample point cloud or input
mesh. In addition, a correspondence between the faces of
the polytope and the respective regions of the object
boundary is needed to guarantee correctness.
We construct such a polytope by first computing a
simplified though still homotopy equivalent medial axis
transform of the input object. Then, we inflate this medial
axis to a polytope of small size. Since our approximation
maintains topology, the simplified medial axis transform is
also useful for skin surfaces and envelope surfaces.}
}
@InProceedings{abdgh-cgm-08,
author = {O. Aichholzer and S. Bereg and A. Dumitrescu and A.
Garc\'{i}a and C. Huemer and F. Hurtado and M. Kano and A.
M{\'a}rquez and D. Rappaport and S. Smorodinsky and D.
Souvaine and J. Urrutia and D. Wood},
title = {Compatible Geometric Matchings},
booktitle = {Proc. $1st$ Topological \& Geometric Graph Theory 2008},
pages = {194--199},
year = 2008,
address = {Paris, France},
abstract = {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 result states that for any
two perfect matchings $M$ and $M'$ of the same set of $n$
points, for some $k \in O(log n)$, there is a sequence of
perfect matchings $M = M_0,M_1, . . . ,M_k = M'$, such that
each $M_i$ is compatible with $M_{i+1}$. This improves the
previous best bound of $k \leq n-2$. We then study the
conjecture: every perfect matching with an even number of
edges has an edge-disjoint compatible perfect matching. We
introduce a sequence of stronger conjectures that imply
this conjecture, and prove the strongest of these
conjectures in the case of perfec matchings that consist of
vertical and horizontal segments. Finally, we prove that
every perfect matching with $n$ edges has an edge-disjoint
compatible matching with approximately $4n/5$ edges.}
}
@InProceedings{acffhhhw-erncc-08,
author = {O. Aichholzer and S. Cabello and R. Fabila-Monroy and D.
Flores-Pe{\~n}aloza and T. Hackl and C. Huemer and F.
Hurtado and D.R. Wood},
title = {Edge-Removal and Non-Crossing Configurations in Geometric
Graphs},
booktitle = {Proc. $24^{th}$ European Workshop on Computational
Geometry EuroCG '08},
pages = {119--122},
year = 2008,
address = {Nancy, France},
url = {http://www.industrial-geometry.at/uploads/proj5/acffhhhw-erncc-08.pdf},
abstract = {We study the following extremal problem for geometric
graphs: How many arbitrary edges can be removed from a
complete geometric graph with $n$ vertices such that the
remaining graph still contains a certain non-crossing
subgraph. In particular we consider perfect matchings and
subtrees of a given size. For both classes of geometric
graphs we obtain tight bounds on the maximum number of
removable edges. We further present several conjectures and
bounds on the number of removable edges for other classes
of non-crossing geometric graphs.}
}
@InProceedings{affhhu-emt-08,
author = {O. Aichholzer and R. Fabila-Monroy and D.
Flores-Pe{\~n}aloza and T. Hackl and C. Huemer and J.
Urrutia},
title = {Empty Monochromatic Triangles},
booktitle = {Proc. $20th$ Annual Canadian Conference on Computational
Geometry CCCG 2008},
pages = {75--78},
year = 2008,
address = {Montreal, Quebec, Canada},
url = {http://www.industrial-geometry.at/uploads/proj5/affhhj-emt-08.pdf},
abstract = {We consider a variation of a problem stated by Erd\"os and
Guy in 1973 about the number of convex $k$-gons determined
by any set $S$ of $n$ points in the plane. In our setting
the points of $S$ are colored and we say that a spanned
polygon is monochromatic if all its points are colored with
the same color. As a main result we show that any
bi-colored set of $n$ points in $\mathcal{R}^2$ in general
position determines a super-linear number of empty
monochromatic triangles, namely $\Omega(n^{5/4})$.}
}
@InProceedings{aak-iubrp-07,
author = {E. Ackerman and O. Aichholzer and B. Keszegh},
title = {Improved Upper Bounds on the Reflexivity of Point Sets},
booktitle = {Proc. $19th$ Annual Canadian Conference on Computational
Geometry CCCG 2007},
pages = {29--32},
year = 2007,
address = {Ottawa, Ontario, Canada},
abstract = {Given a set $S$ of $n$ points in the plane, the
\emph{reflexivity} of $S$, $\rho(S)$, is the minimum number
of reflex vertices in a simple polygonalization of $S$.
Arkin et al. proved that $\rho(S) \le n/2$ for any set $S$,
and conjectured that the tight upper bound is $n/4$. We
show that the reflexivity of any set of $n$ points is at
most $\frac{3}{7}n + O(1) \approx 0.4286n$. Using
computer-aided abstract order type extension the upper
bound can be further improved to $\frac{5}{12}n + O(1)
\approx 0.4167n$.}
}
@InProceedings{aahjos-csacb-07,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
J\"uttler and M.Oberneder and Z. S\'ir},
title = {Computational and Structural Advantages of Circular
Boundary Representation},
booktitle = {Lecture Notes in Computer Science, Proc. 10th
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {4619},
address = {Halifax, Nova Scotia, Canada},
pages = {374--385},
year = 2007,
url = {http://www.ag.jku.at/pubs/2007aahjos.pdf},
abstract = {Boundary approximation of planar shapes by circular arcs
has quantitive and qualitative advantages compared to using
straight-line segments. We demonstrate this by way of three
basic and frequent computations on shapes -- convex hull,
decomposition, and medial axis. In particular, we propose a
novel medial axis algorithm that beats existing methods in
simplicity and practicality, and at the same time
guarantees convergence to the medial axis of the original
shape.}
}
@InProceedings{aahkpp-abtob-07,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
Kornberger and M. Peternell and H. Pottmann},
title = {Approximating Boundary-Triangulated Objects with Balls},
booktitle = {Proc. $23^{rd}$ European Workshop on Computational
Geometry EuroCG '07},
pages = {130--133},
year = 2007,
address = {Graz, Austria},
url = {http://www.igi.tugraz.at/auren/psfiles/aahkpp-abtob-07.ps.gz},
abstract = {We compute a set of balls that approximates a given
\mbox{3D object}, and we derive small additive bounds for
the overhead in balls with respect to the minimal solution
with the same quality. The algorithm has been implemented
and tested using the CGAL library.}
}
@InProceedings{aahs-pmwpt-07,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl and B.
Speckmann},
title = {On (Pointed) Minimum Weight Pseudo-Triangulations},
booktitle = {Proc. $19th$ Annual Canadian Conference on Computational
Geometry CCCG 2007},
pages = {209--212},
year = 2007,
address = {Ottawa, Ontario, Canada},
abstract = {In this note we discuss some structural properties of
minimum weight (pointed) pseudo-triangulations.}
}
@InProceedings{agor-nrlbn-07b,
author = {O. Aichholzer and J. Garc\'{i}a and D. Orden and P.A.
Ramos},
title = {New results on lower bounds for the number of $(\leq
k)$-facets},
booktitle = {Proceedings EuroComb'07, Electronic Notes in Discrete
Mathematics},
pages = {189--193},
year = 2007,
volume = {29C},
abstract = {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 bound $3{k+2 \choose 2}$ of
$(\leq k)$-edges for a fixed $k\leq \lfloor n/3 \rfloor
-1$; (2) We show that the lower bound $3{k+2 \choose
2}+3{k-\lfloor \frac{n}{3} \rfloor+2 \choose 2}$ for the
number of $(\leq k)$-edges of a planar point set is optimal
in the range $\lfloor n/3 \rfloor \leq k \leq \lfloor 5n/12
\rfloor -1$; (3) We show that, for $k < n/4$, the number of
$(\leq k)$-facets a set of $n$ points in $\mathbb{R}^3$ in
general position is at least $4{k+3 \choose 3}$, and that
this bound is tight in that range.}
}
@InProceedings{ahhhssv-mmaps-07b,
author = {O. Aichholzer and T. Hackl and M. Hoffmann and C. Huemer
and A. Por and F. Santos and B. Speckmann and B.
Vogtenhuber},
title = {Maximizing Maximal Angles for Plane Straight Line Graphs},
booktitle = {Lecture Notes in Computer Science, Proc. 10th
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {4619},
address = {Halifax, Nova Scotia, Canada},
pages = {458--469},
year = 2007,
abstract = {Let $G=(S, E)$ be a plane straight line graph on a finite
point set $S\subset {R}^2$ in general position. For a point
$p\in S$ let the {\em maximum incident angle} of $p$ in $G$
be the maximum angle between any two edges of $G$ that
appear consecutively in the circular order of the edges
incident to $p$. A plane straight line graph is called {\em
$\varphi$-open} if each vertex has an incident angle of
size at least $\varphi$. In this paper we study the
following type of question: What is the maximum angle
$\varphi$ such that for any finite set $S\subset {R}^2$ of
points in general position we can find a graph from a
certain class of graphs on $S$ that is $\varphi$-open? In
particular, we consider the classes of triangulations,
spanning trees, and paths on $S$ and give tight bounds in
all but one cases.}
}
@InProceedings{ahhhssv-mmaps-07,
author = {O. Aichholzer and T. Hackl and M. Hoffmann and C. Huemer
and F. Santos and B. Speckmann and B. Vogtenhuber},
title = {Maximizing Maximal Angles for Plane Straight Line Graphs},
booktitle = {Proc. $23^{rd}$ European Workshop on Computational
Geometry EuroCG '07},
pages = {98--101},
year = 2007,
address = {Graz, Austria},
htmlnote = {Also available as FSP-report S092-48, Austria, 2007, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {Let $G=(S, E)$ be a plane straight line graph on a finite
point set $S\subset {R}^2$ in general position. For a point
$p\in S$ let the {\em maximum incident angle} of $p$ in $G$
be the maximum angle between any two edges of $G$ that
appear consecutively in the circular order of the edges
incident to $p$. A plane straight line graph is called {\em
$\varphi$-open} if each vertex has an incident angle of
size at least $\varphi$. In this paper we study the
following type of question: What is the maximum angle
$\varphi$ such that for any finite set $S\subset {R}^2$ of
points in general position we can find a graph from a
certain class of graphs on $S$ that is $\varphi$-open? In
particular, we consider the classes of triangulations,
spanning trees, and paths on $S$ and give tight bounds in
all but one cases.}
}
@InProceedings{arsv-pdpg-07,
author = {O. Aichholzer and G. Rote and A. Schulz and B.
Vogtenhuber},
title = {Pointed Drawings of Planar Graphs},
booktitle = {Proc. $19th$ Annual Canadian Conference on Computational
Geometry CCCG 2007},
pages = {237--240},
year = 2007,
address = {Ottawa, Ontario, Canada},
abstract = {We study the problem how to draw a planar graph such that
every vertex is incident to an angle greater than $\pi$. In
general a straight-line embedding cannot guarantee this
property. We present algorithms which construct such
drawings with either tangent-continuous biarcs or quadratic
B\'ezier curves (parabolic arcs), even if the
\mbox{positions} of the vertices are predefined by a given
plane straight-line embedding of the graph. Moreover, the
graph can be embedded with circular arcs if the vertices
can be placed arbitrarily. The topic is related to
non-crossing drawings of multigraphs and vertex labeling.}
}
@incollection{awpp-vdos-07,
author = {F. Aurenhammer and J. Wallner and
M. Peternell and H. Pottmann},
title = {Voronoi Diagrams for Oriented Spheres},
booktitle = {Proc. ISVD'07: 4th Int. Conf. Voronoi Diagrams in
Science and Engineering},
year = {2007},
publisher = {IEEE Computer Society},
editor = {Chris Gold},
isbn = {0-7695-2869-4},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISVD.2007.45},
pages = {33--37},
url = {http://www.geometrie.tugraz.at/wallner/zykel_ieee.pdf},
}
@InProceedings{aah-ptlc-06,
author = {O. Aichholzer and F. Aurenhammer and T. Hackl},
title = {Pre-triangulations and liftable complexes},
booktitle = {$22^{nd}$ Ann. ACM Symp. Computational Geometry},
year = 2006,
pages = {282--291},
address = {Sedona, Arizona, USA},
htmlnote = {Also available as FSP-report S092-6, Austria, 2006, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {We introduce and discuss the concept of
pre-triangulations, a relaxation of triangulations that
goes beyond the well-established class of
pseudo-triangulations.}
}
@InProceedings{aahv-gceps-06,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and B.
Vogtenhuber},
title = {Gray code enumeration of plane straight-line graphs},
booktitle = {Proc. $22^{nd}$ European Workshop on Computational
Geometry EuroCG '06},
pages = {71--74},
year = 2006,
address = {Delphi, Greece},
htmlnote = {Also available as FSP-report S092-7, Austria, 2006, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {We develop Gray code enumeration schemes for geometric
straight-line graphs in the plane. The considered graph
classes include plane graphs, connected plane graphs, and
plane spanning trees. Previous results were restricted to
the case where the underlying vertex set is in convex
position.}
}
@InProceedings{ahhhkv-npg-06,
author = {O. Aichholzer and T. Hackl and C. Huemer and F. Hurtado
and H. Krasser and B. Vogtenhuber},
title = {On the number of plane graphs},
booktitle = {Proc. 17th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA)},
pages = {504-513},
year = 2006,
address = {Miami, Florida, USA},
htmlnote = {Also available as FSP-report S092-8, Austria, 2006, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {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 number of cycle-free
plane graphs is minimized when $S$ is in convex position.
Moreover, these results hold for all these graphs with an
arbitrary but fixed number of edges. Consequently, we
provide simple proofs that the number of spanning trees,
cycle-free graphs (forests), perfect matchings, and
spanning paths is also minimized for point sets in convex
position. In addition we construct a new extremal
configuration, the so-called double zig-zag chain. Most
noteworthy this example bears $\Theta^*(\sqrt{72}\,^n)$ =
$\Theta^*(8.4853^n)$ triangulations and
$\Theta^*(41.1889^n)$ plane graphs (omitting polynomial
factors in both cases), improving the previously known best
maximizing examples.}
}
@InProceedings{ahrst-pcdpc-06,
author = {O. Aichholzer and C. Huemer and S. Renkl and B. Speckmann
and C. D. T\'oth},
title = {Decompositions, Partitions, and Coverings with Convex
Polygons and Pseudo-Triangles},
booktitle = {Proceedings $31^{st}$ International Symposium on
Mathematical Foundations of Computer Science, Lecture Notes
in Computer Science},
editor = {Rastislav Královic,Pawel Urzyczyn},
year = 2006,
volume = {4162},
pages = {86-97},
address = {Stará Lesná, Slovakia},
abstract = {We propose a novel subdivision of the plane that consists
of both convex polygons and pseudo-triangles. This
pseudo-convex decomposition is significantly sparser than
either convex decompositions or pseudo-triangulations for
planar point sets and simple polygons. We also introduce
pseudo-convex partitions and coverings. We establish some
basic properties and give combinatorial bounds on their
complexity. Our upper bounds depend on new Ramsey-type
results concerning disjoint empty convex k-gons in point
sets.}
}
@InProceedings{aor-ssarc-06,
author = {O. Aichholzer and D. Orden and P.A. Ramos},
title = {On the Structure of sets attaining the rectilinear
crossing number},
booktitle = {Proc. $22^{nd}$ European Workshop on Computational
Geometry EuroCG '06},
pages = {43--46},
year = 2006,
address = {Delphi, Greece},
abstract = {We study the structural properties of the point
configurations attaining the rectilinear crossing number
$\overline{cr}(K_n)$, that is, those $n$-point sets that
minimize the number of crossings over all possible
straight-edge embeddings of $K_n$ in the plane. As a main
result we prove the conjecture that such sets always have a
triangular convex hull. The techniques developed allow us
to show a similar result for the halving-edge problem: For
any $n$ there exists a set of $n$ points with triangular
convex hull that maximizes the number of halving edges.
Moreover, we provide a simpler proof of the following
result: any set of points in the plane in general position
has at least $3{j+2 \choose 2}$ $(\leq j)$-edges. This
bound is known to be tight for $0\leq j\leq
\lfloor\frac{n}{3}\rfloor-1$. In addition, we show that for
point sets achieving this bound the
$\lfloor\frac{n+3}{6}\rfloor$ outermost convex layers are triangles.}
}
@InProceedings{aaghhhkrv-mefpp-05,
author = {O. Aichholzer and F. Aurenhammer and P. Gonzalez-Nava and
T. Hackl and C. Huemer and F. Hurtado and H. Krasser and S.
Ray and B. Vogtenhuber},
title = {Matching Edges and Faces in Polygonal Partitions},
booktitle = {Proc. $17th$ Annual Canadian Conference on Computational
Geometry CCCG 2005},
pages = {123--126},
year = 2005,
address = {Windsor, Ontario, Canada},
htmlnote = {Also available as FSP-report S092-4, Austria, 2005, at http://www.ig.jku.at/cgi-bin/CGI/Reports.pl.}
,
abstract = {We define general Laman (count) conditions for edges and
faces of polygonal partitions in the plane. Several
well-known classes, including $k$-regular partitions,
$k$-angulations, and rank $k$ pseudo-triangulations, are
shown to fulfill such conditions. As a consequence
non-trivial perfect matchings exist between the edge sets
(or face sets) of two such structures when they live on the
same point set. We also describe a link to spanning tree
decompositions that applies to quadrangulations and certain
pseudo-triangulations.}
}
@InProceedings{ahhhkv-bnpg-06,
author = {O. Aichholzer and T. Hackl and C. Huemer and F. Hurtado
and H. Krasser and B. Vogtenhuber},
title = {Bounding the number of plane graphs},
booktitle = {Proc. 15th Annual Fall Workshop on Computational Geometry
and Visualization},
pages = {31-32},
year = 2005,
address = {Philadelphia, Pennsylvania, USA},
abstract = {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 number of cycle-free
plane graphs is minimized when $S$ is in convex position.
Moreover, these results hold for all these graphs with an
arbitrary but fixed number of edges. Consequently, we
provide simple proofs that the number of spanning trees,
cycle-free graphs (forests), perfect matchings, and
spanning paths is also minimized for point sets in convex
position. In addition we construct a new extremal
configuration, the so-called double zig-zag chain. Most
noteworthy this example bears $\Theta^*(\sqrt{72}\,^n)$ =
$\Theta^*(8.4853^n)$ triangulations and
$\Theta^*(41.1889^n)$ plane graphs (omitting polynomial
factors in both cases), improving the previously known best
maximizing examples.}
}
@InProceedings{ak-aoten-05b,
author = {O. Aichholzer and H. Krasser},
title = {Abstract Order Type Extension and New Results on the
Rectilinear Crossing Number},
booktitle = {Proc. $21^{th}$ Ann. ACM Symp. Computational Geometry},
year = 2005,
pages = {91--98},
address = {Pisa, Italy},
abstract = {We extend the order type data base of all realizable order
types in the plane to point sets of cardinality 11. More
precisely, we provide a complete data base of all
combinatorial different sets of up to 11 points in general
position in the plane. Moreover we develop a novel and
efficient method for a complete extension to order types of
size 12 and more in an abstract sense, that is, without the
need to store or realize the sets. The presented method is
well suited for independent computations and thus time
intensive investigations benefit from the possibility of
distributed computing.\\ Our approach has various
applications to combinatorial problems which are based on
sets of points in the plane. This includes classic problems
like searching for (empty) convex k-gons (´happy end
problem´), decomposing sets into convex regions, counting
structures like triangulations or pseudo-triangulations,
minimal crossing numbers, and more. We present some
improved results to all these problems. As an outstanding
result we have been able to determine the exact rectilinear
crossing number for up to $n=17$, the largest previous
range being $n=12$, and slightly improved the asymptotic
upper bound. }
}
@InProceedings{aahlrss-swe-05,
author = {B. Aronov and F. Aurenhammer and F. Hurtado and S.
Langerman and D. Rappaport and S. Smorodinsky and C.
Seara},
title = {Small weak epsilon nets},
booktitle = {Proc. $17^{th}$ Canadian Conference on Computational
Geometry CCCG '05},
pages = {51--54},
year = 2005,
address = {Windsor, Ontario}
}