@inproceedings{ahvv-nng4h-16,
author = {Oswin Aichholzer and Thomas Hackl and Pavel Valtr and Birgit Vogtenhuber},
title = {{{A Note on the Number of General 4-holes in (Perturbed) Grids}}},
booktitle = {Discrete and Computational Geometry and Graphs. JCDCGG 2015.},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {9943},
editor = {Akiyama, Jin and Ito, Hiro and Sakai, Toshinori and Uno, Yushi},
publisher = {Springer, Cham},
pages = {1--12},
year = 2016,
e-isbn = {978-3-319-48532-4"},
isbn = {978-3-319-48531-7},
doi = {https://doi.org/10.1007/978-3-319-48532-4_1},
abstract = {{Considering a variation of the classical Erd{\H{o}}s-Szekeres type
problems, we count the number of general 4-holes (not necessarily convex, empty 4-gons)
in squared Horton sets of size $\sqrt{n}\!\times\!\sqrt{n}$.
Improving on previous upper and lower bounds we
show that this number is $\Theta(n^2\log n)$, which constitutes
the currently best upper bound on minimizing the number of general
\mbox{$4$-holes} for any set of $n$ points in the plane.
To obtain the improved bounds, we prove a result of independent
interest. We show that $\sum_{d=1}^n \frac{\varphi(d)}{d^2} =
\Theta(\log n)$, where $\varphi(d)$ is Euler's phi-function, the
number of positive integers less than~$d$ which are relatively prime
to $d$. This arithmetic function is also called Euler's totient
function and plays a role in number theory and cryptography.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahkprrrv-psst-16,
author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and G{\"u}nter Rote and Andr{\'e} van Renssen and Marcel Roeloffzen and Birgit Vogtenhuber},
title = {{{Packing Short Plane Spanning Trees in Complete Geometric Graphs}}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {9:1--9:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-026-2},
issn = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
url = {http://drops.dagstuhl.de/opus/volltexte/2016/6782},
urn = {urn:nbn:de:0030-drops-67823},
doi = {10.4230/LIPIcs.ISAAC.2016.9},
annote = {Keywords: Geometric Graphs, Graph Packing, Plane Graphs, Minimum Spanning Tree, Bottleneck Edge},
abstract = {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 that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two graphs. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. In both cases the obtained layers are plane.},
originalfile = {/geometry/cggg.bib}
}
@article{aaghlru-gapi-13,
author = {O. Aichholzer and G.~Araujo-Pardo and N.~Garc{\'i}a-Col{\'i}n and T.~Hackl and D.~Lara and C.~Rubio-Montiel and J.~Urrutia},
title = {{{Geometric achromatic and pseudoachromatic indices}}},
journal = {Graphs and Combinatorics},
year = 2016,
category = {3a},
volume = {32},
number = {2},
pages = {431--451},
thackl_label = {50J},
htmlnote = {
Springer Online First.},
pdf = {/files/publications/geometry/aaghlru-gapi-13.pdf},
doi = {http://dx.doi.org/10.1007/s00373-015-1610-x},
arxiv = {1303.4673},
abstract = {The pseudoachromatic index of a graph is the
maximum number of colors that can be assigned to its
edges, such that each pair of different colors is
incident to a common vertex. If for each vertex its
incident edges have different color, then this
maximum is known as achromatic index. Both indices
have been widely studied. A geometric graph is a
graph drawn in the plane such that its vertices are
points in general position, and its edges are
straight-line segments. In this paper we extend the
notion of pseudoachromatic and achromatic indices
for geometric graphs, and present results for
complete geometric graphs. In particular, we show
that for n points in convex position the achromatic
index and the pseudoachromatic index of the complete
geometric graph are
$\lfloor\frac{n^2+n}{4}\rfloor$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahvv-nng4h-15,
author = {O. Aichholzer and T.~Hackl and P.~Valtr and
B.~Vogtenhuber},
title = {{{A note on the number of general 4-holes in
perturbed grids}}},
booktitle = {Proc. $18^{th}$ Japan Conference on Discrete and
Computational Geometry and Graphs (JCDCG$^2$ 2015)},
pages = {68--69},
year = 2015,
address = {Kyoto, Japan},
category = {3b},
thackl_label = {49C},
xxarxiv = {},
xpdf = {/files/publications/geometry/ahvv-nng4h-15.pdf},
abstract = {Considering a variation of the classical Erd{\H{o}}s
and Szekeres type problems, we count the number of
general $4$-holes (empty \mbox{$4$-gons}) in the
$\sqrt{n}\!\times\!\sqrt{n}$ squared Horton
set. Improving on previous upper and lower bounds we
show that this number is $\Theta(n^2\log n)$, which
also constitutes the currently best upper bound on
minimizing the number of general \mbox{$4$-holes}
for any set of $n$ points in the plane.\\ To obtain
these bounds and as a result of independent
interest, we show that $\sum_{d=1}^n
\frac{\varphi(d)}{d^2} = \Theta(\log n)$, where
$\varphi(d)$ is Euler's phi-function, the number of
positive integers less than~$d$ which are relatively
prime to $d$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhhhpv-rdtss-15,
author = {O. Aichholzer and T.~Biedl and T.~Hackl
and M.~Held and S.~Huber and P.~Palfrader and B.~Vogtenhuber},
title = {{{Representing Directed Trees as Straight Skeletons}}},
booktitle = {Proc. $23^{nd}$ International Symposium on Graph Drawing (GD 2015)},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {9411},
nopublisher = {Springer, Heidelberg},
editor = {Emilio Di Giacomo and Anna Lubiw},
pages = {335--347},
year = 2015,
address = {Los Angeles, CA, USA},
category = {3b},
thackl_label = {48C},
arxiv = {1508.01076},
doi = {http://dx.doi.org/10.1007/978-3-319-27261-0},
isbn = {978-3-319-27260-3},
e-isbn = {978-3-319-27261-0},
issn = {0302-9743},
pdf = {/files/publications/geometry/abhhhpv-rdtss-15.pdf},
abstract = {The straight skeleton of a polygon is the geometric
graph obtained by tracing the vertices during a
mitered offsetting process. It is known that the
straight skeleton of a simple polygon is a tree, and
one can naturally derive directions on the edges of
the tree from the propagation of the shrinking
process.\\ In this paper, we ask the reverse
question: Given a tree with directed edges, can it
be the straight skeleton of a polygon? And if so,
can we find a suitable simple polygon? We answer
these questions for all directed trees where the
order of edges around each node is fixed.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aafhpprsv-agdsc-15,
author = {B.M.~\'Abrego and O. Aichholzer and S.~Fern\'andez-Merchant and T.~Hackl
and J.~Pammer and A.~Pilz and P.~Ramos and G.~Salazar and B.~Vogtenhuber},
title = {{{All Good Drawings of Small Complete Graphs}}},
booktitle = {Proc. $31^{st}$ European Workshop on Computational
Geometry EuroCG '15},
pages = {57--60},
year = 2015,
address = {Ljubljana, Slovenia},
category = {3b},
thackl_label = {46C},
xxarxiv = {},
pdf = {/files/publications/geometry/aafhpprsv-agdsc-15.pdf},
abstract = {\emph{Good drawings} (also known as \emph{simple
topological graphs}) are drawings of graphs such
that any two edges intersect at most once. Such
drawings have attracted attention as generalizations
of geometric graphs, in connection with the crossing
number, and as data structures in their own right.
We are in particular interested in good drawings of
the complete graph. In this extended abstract, we
describe our techniques for generating all different
weak isomorphism classes of good drawings of the
complete graph for up to nine vertices. In
addition, all isomorphism classes were enumerated.
As an application of the obtained data, we present
several existential and extremal properties of these
drawings.},
originalfile = {/geometry/cggg.bib}
}
@article{aahhpruvv-kcps-14,
author = {O. Aichholzer and F.~Aurenhammer and T.~Hackl and
F.~Hurtado and A.~Pilz and P.~Ramos and J.~Urrutia and P.~Valtr and B.~Vogtenhuber},
title = {{{On $k$-Convex Point Sets}}},
journal = {Computational Geometry: Theory and Applications},
year = 2014,
volume = {47},
number = {8},
pages = {809--832},
thackl_label = {40J},
category = {3a},
issn = {0925-7721},
url = {http://www.sciencedirect.com/science/article/pii/S0925772114000534},
doi = {http://dx.doi.org/10.1016/j.comgeo.2014.04.004},
pdf = {/files/publications/geometry/aahhpruvv-kcps-14.pdf},
abstract = {We extend the (recently introduced) notion of
$k$-convexity of a two-di\-men\-sional subset of the
Euclidean plane to finite point sets. A set of $n$
points is considered $k$-convex if there exists a
spanning (simple) polygonization such that the
intersection of any straight line with its interior
consists of at most~$k$ disjoint intervals. As the
main combinatorial result, we show that every
$n$-point set contains a subset of $\Omega(\log^2
n)$ points that are in 2-convex position. This
bound is asymptotically tight. From an algorithmic
point of view, we show that 2-convexity of a finite
point set can be decided in polynomial time, whereas
the corresponding problem on $k$-convexity becomes
NP-complete for any fixed $k\geq 3$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahplmv-mseup-15,
author = {O. Aichholzer and T.~Hackl
and S.~Lutteropp and T.~Mchedlidze and A.~Pilz and B.~Vogtenhuber},
title = {{{Monotone Simultaneous Embedding of Upward Planar Digraphs}}},
journal = {Journal of Graph Algorithms and Applications},
year = 2015,
volume = {19},
number = {1},
pages = {87--110},
thackl_label = {39J},
category = {3a},
issn = {1526-1719},
doi = {http://dx.doi.org/10.7155/jgaa.00350},
arxiv = {1310.6955v2},
pdf = {/files/publications/geometry/ahplmv-mseup-15.pdf},
abstract = {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 upwardness of different
graphs can differ. We first consider the special
case where each digraph is a directed path. In
contrast to the known result that any two directed
paths admit a monotone simultaneous embedding, there
exist examples of three paths that do not admit such
an embedding for any possible choice of directions
of monotonicity.\\ We prove that if a monotone
simultaneous embedding of three paths exists then it
also exists for any possible choice of directions of
monotonicity. We provide a polynomial-time
algorithm that, given three paths, decides whether a
monotone simultaneous embedding exists and, in the
case of existence, also constructs such an
embedding. On the other hand, we show that already
for three paths, any monotone simultaneous embedding
might need a grid whose size is exponential in the
number of vertices. For more than three paths, we
present a polynomial-time algorithm that, given any
number of paths and predefined directions of
monotonicity, decides whether the paths admit a
monotone simultaneous embedding with respect to the
given directions, including the construction of a
solution if it exists. Further, we show several
implications of our results on monotone simultaneous
embeddings of general upward planar digraphs.
Finally, we discuss complexity issues related to our
problems.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahplmv-msedp-14,
author = {O. Aichholzer and T.~Hackl
and S.~Lutteropp and T.~Mchedlidze and A.~Pilz and B.~Vogtenhuber},
title = {{{Monotone Simultaneous Embedding of Directed Paths}}},
booktitle = {Proc. $30^{th}$ European Workshop on Computational
Geometry EuroCG '14},
pages = {online},
year = 2014,
address = {Dead Sea, Israel},
category = {3b},
thackl_label = {39C},
arxiv = {1310.6955v2},
pdf = {/files/publications/geometry/ahplmv-msedp-14.pdf},
abstract = {We consider a variant of monotone simultaneous
embeddings (MSEs) of directed graphs where all
graphs are directed paths and have distinct
directions of monotonicity. In contrast to the
known result that any two directed paths admit an
MSE, there exist examples of three paths that do not
admit such an embedding for any possible choice of
directions of monotonicity. We prove that if an MSE
of three paths exists then it also exists for any
possible choice of directions of monotonicity. We
provide a polynomial-time algorithm that, given
three paths, decides whether an MSE exists.
Finally, we provide a polynomial-time algorithm that
answers the existence question for any given number
of paths and predefined directions of monotonicity.},
originalfile = {/geometry/cggg.bib}
}
@article{ahkpv-gpps-14,
author = {O. Aichholzer and T.~Hackl and M.~Korman and A.~Pilz and
B.~Vogtenhuber},
title = {{{Geodesic-preserving polygon simplification}}},
journal = {Int'l Journal of Computational Geometry \& Applications},
year = 2014,
volume = {24},
category = {3a},
number = {4},
oaich_label = {},
thackl_label = {38J},
pages = {307--323},
pdf = {/files/publications/geometry/ahkpv-gpps-13.pdf},
doi = {http://dx.doi.org/10.1142/S0218195914600097},
arxiv = {1309.3858},
abstract = {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
input polygon, the intrinsic complexity of the problems
these algorithms solve is often related to the reflex
vertices of the polygon. In this paper, we give an
easy-to-describe linear-time method to replace an input
polygon~$P$ by a polygon $P'$ such that (1)~$P'$
contains~$P$, (2)~$P'$ has its reflex vertices at the same
positions as~$P$, and (3)~the number of vertices of $P'$ is
linear in the number of reflex vertices. Since the
solutions of numerous problems on polygons (including
shortest paths, geodesic hulls, separating point sets, and
Voronoi diagrams) are equivalent for both $P$ and $P'$, our
algorithm can be used as a preprocessing step for several
algorithms and makes their running time dependent on the
number of reflex vertices rather than on the size of~$P$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahkpv-gpps-13,
author = {O. Aichholzer and T.~Hackl and M.~Korman and A.~Pilz and
B.~Vogtenhuber},
title = {{{Geodesic-preserving polygon simplification}}},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $24^{th}$ Int. Symp.
Algorithms and Computation (ISAAC 2013)},
pages = {11--21},
year = {2013},
volume = {8283},
address = {Hong Kong, China},
publisher = {Springer Verlag},
category = {3b},
pdf = {/files/publications/geometry/ahkpv-gpps-13.pdf},
thackl_label = {38C},
arxiv = {1309.3858},
abstract = {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
input polygon, the intrinsic complexity of the problems
these algorithms solve is often related to the reflex
vertices of the polygon. In this paper, we give an
easy-to-describe linear-time method to replace an input
polygon~$P$ by a polygon $P'$ such that (1)~$P'$
contains~$P$, (2)~$P'$ has its reflex vertices at the same
positions as~$P$, and (3)~the number of vertices of $P'$ is
linear in the number of reflex vertices. Since the
solutions of numerous problems on polygons (including
shortest paths, geodesic hulls, separating point sets, and
Voronoi diagrams) are equivalent for both $P$ and $P'$, our
algorithm can be used as a preprocessing step for several
algorithms and makes their running time dependent on the
number of reflex vertices rather than on the size of~$P$.},
originalfile = {/geometry/cggg.bib}
}
@article{afhhj-ems-13,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and
C.~Huemer and J.~Urrutia},
title = {{{Empty Monochromatic Simplices}}},
journal = {Discrete \& Computational Geometry},
year = 2014,
volume = {51},
category = {3a},
number = {2},
oaich_label = {},
thackl_label = {37J},
pages = {362--393},
pdf = {/files/publications/geometry/afhhu-ems-13.pdf},
doi = {http://dx.doi.org/10.1007/s00454-013-9565-2},
arxiv = {1210.7043},
abstract = {Let $S$ be a $k$-colored (finite) set of $n$ points in
${R}^d$, $d\geq 3$, in general position, that is, no
\mbox{$(d\!+\!1)$} points of $S$ lie in a common
\mbox{$(d\!-\!1)$}-dimensional hyperplane. We count the
number of empty monochromatic $d$-simplices determined by
$S$, that is, simplices which have only points from one
color class of $S$ as vertices and no points of $S$ in
their interior. For $3 \leq k \leq d$ we provide a lower
bound of $\Omega(n^{d-k+1+2^{-d}})$ and strengthen this to
$\Omega(n^{d-2/3})$ for $k=2$. On the way we provide
various results on triangulations of point sets in~${R}^d$.
In particular, for any constant dimension $d\geq3$, we
prove that every set of $n$ points ($n$ sufficiently
large), in general position in ${R}^d$, admits a
triangulation with at least $dn+\Omega(\log n)$ simplices.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{accchhkllmru-chidp-13,
author = {A.~Asinowski and J.~Cardinal and N.~Cohen and S.~Collette
and T.~Hackl and M.~Hoffmann and K.~Knauer and S.~Langerman
and M.~Laso\'n and P.~Micek and G.~Rote and T.~Ueckerdt},
title = {{{Coloring Hypergraphs Induced by Dynamic Point Sets
and Bottomless Rectangles}}},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $13^{th}$
Algorithms and Data Structures Symposium (WADS 2013)},
volume = {8037},
pages = {73--84},
year = 2013,
address = {London, Ontario, Canada},
category = {3b},
thackl_label = {36C},
arxiv = {1302.2426},
pdf = {/files/publications/geometry/accchhkllmru-chidp-13.pdf},
abstract = {We consider a coloring problem on dynamic, one-dimensional
point sets: points appearing and disappearing on a line at
given times. We wish to color them with $k$ colors so that
at any time, any sequence of $p(k)$ consecutive points, for
some function $p$, contains at least one point of each
color. We prove that no such function $p(k)$ exists in
general. However, in the restricted case in which points
appear gradually, but never disappear, we give a coloring
algorithm guaranteeing the property at any time with
$p(k)=3k-2$. This can be interpreted as coloring point sets
in ${R}^2$ with $k$ colors such that any bottomless
rectangle containing at least $3k-2$ points contains at
least one point of each color. Here a bottomless rectangle
is an axis-aligned rectangle whose bottom edge is below the
lowest point of the set. For this problem, we also prove a
lower bound $p(k)>ck$, where $c>1.67$. Hence, for every $k$
there exists a point set, every $k$-coloring of which is
such that there exists a bottomless rectangle containing
$ck$ points and missing at least one of the $k$ colors.
Chen {\em et al.} (2009) proved that no such function
$p(k)$ exists in the case of general axis-aligned
rectangles. Our result also complements recent results from
Keszegh and P\'alv\"olgyi on cover-decomposability of
octants (2011, 2012).},
originalfile = {/geometry/cggg.bib}
}
@article{achhkpsuvw-cpmbl-13a,
author = {O. Aichholzer and J.~Cardinal and T.~Hackl and F.~Hurtado
and M.~Korman and A.~Pilz and R.I.~Silveira and R.~Uehara
and B.~Vogtenhuber and E.~Welzl},
title = {{{Cell-Paths in Mono- and Bichromatic Line
Arrangements in the Plane}}},
journal = {Discrete Mathematics \& Theoretical Computer Science
(DMTCS)},
category = {3a},
oaich_label = {},
thackl_label = {35J},
pages = {317--332},
volume = {16},
number = {3},
year = 2014,
pdf = {/files/publications/geometry/achhkpsuvw-cpmbl-13.pdf},
url = {https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2590.1.html},
xdoi = {http://dx.doi.org/...},
abstract = {We show that in every arrangement of $n$ red and blue
lines (in general position and not all of the same color)
there is a path through a linear number of cells where red
and blue lines are crossed alternatingly (and no cell is
revisited). When all lines have the same color, and hence
the preceding alternating constraint is dropped, we prove
that the dual graph of the arrangement always contains a
path of length $\Theta(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{achhkpsuvw-cpmbl-13,
author = {O. Aichholzer and J.~Cardinal and T.~Hackl and F.~Hurtado
and M.~Korman and A.~Pilz and R.I.~Silveira and R.~Uehara
and B.~Vogtenhuber and E.~Welzl},
title = {{{Cell-Paths in Mono- and Bichromatic Line
Arrangements in the Plane}}},
booktitle = {Proc. $25^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2013},
pages = {169--174},
year = 2013,
address = {Waterloo, Ontario, Canada},
category = {3b},
thackl_label = {35C},
pdf = {/files/publications/geometry/achhkpsuvw-cpmbl-13.pdf},
abstract = {We show that in every arrangement of $n$ red and blue
lines (in general position and not all of the same color)
there is a path through a linear number of cells where red
and blue lines are crossed alternatingly (and no cell is
revisited). When all lines have the same color, and hence
the preceding alternating constraint is dropped, we prove
that the dual graph of the arrangement always contains a
path of length $\Theta(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahprsv-etgdc-15,
author = {O.~Aichholzer and T.~Hackl and A.~Pilz and P.~Ramos and
V.~Sacrist\'{a}n and B.~Vogtenhuber},
title = {{{Empty triangles in good drawings of the complete graph}}},
journal = {Graphs and Combinatorics},
issn = {0911-0119},
publisher = {Springer Japan},
pages = {335--345},
volume = {31},
number = {2},
htmlnote = {For
Springer Online First.},
doi = {http://dx.doi.org/10.1007/s00373-015-1550-5},
year = 2015,
thackl_label = {34J},
category = {3a},
pdf = {/files/publications/geometry/ahprsv-etgdc-13.pdf},
eprint = {1306.5081},
archiveprefix = {arXiv},
keywords = {Good drawings; Empty triangles; Erdős–Szekeres type problems},
abstract = {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 their end vertices, and any pair of edges
intersects at most once. In any good drawing, the edges of
three pairwise connected vertices form a Jordan curve which
we call a triangle. We say that a triangle is empty if one
of the two connected components it induces does not contain
any of the remaining vertices of the drawing of the graph.
We show that the number of empty triangles in any good
drawing of the complete graph $K_n$ with $n$ vertices is at
least $n$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahprsv-etgdc-13,
author = {O.~Aichholzer and T.~Hackl and A.~Pilz and P.~Ramos and
V.~Sacrist\'{a}n and B.~Vogtenhuber},
title = {{{Empty triangles in good drawings of the complete graph}}},
booktitle = {Mexican Conference on Discrete Mathematics and
Computational Geometry},
pages = {21--29},
year = 2013,
address = {Oaxaca, M{\'e}xico},
thackl_label = {34C},
category = {3b},
pdf = {/files/publications/geometry/ahprsv-etgdc-13.pdf},
eprint = {1306.5081},
abstract = {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 their end vertices, and any pair of edges
intersects at most once. In any good drawing, the edges of
three pairwise connected vertices form a Jordan curve which
we call a triangle. We say that a triangle is empty if one
of the two connected components it induces does not contain
any of the remaining vertices of the drawing of the graph.
We show that the number of empty triangles in any good
drawing of the complete graph $K_n$ with $n$ vertices is at
least $n$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahopsv-fcppt-14,
author = {O.~Aichholzer and T.~Hackl and D.~Orden and A.~Pilz and
M.~Saumell and B.~Vogtenhuber},
title = {{{Flips in combinatorial pointed
pseudo-triangulations with face degree at most four}}},
journal = {Int'l Journal of Computational Geometry \& Applications},
year = 2014,
volume = {24},
number = {3},
pages = {197--224},
thackl_label = {33J},
category = {3a},
issn = {0218-1959},
online-issn = {1793-6357},
doi = {http://dx.doi.org/10.1142/S0218195914600036},
eprint = {1310.0833},
archiveprefix = {arXiv},
pdf = {/files/publications/geometry/ahopsv-fcppt-14.pdf},
abstract = {In this paper we consider the flip operation for
combinatorial pointed pseudo-triangulations where faces
have size~3 or~4, so-called \emph{combinatorial 4-PPTs}. We
show that every combinatorial 4-PPT is stretchable to a
geometric pseudo-triangulation, which in general is not the
case if faces may have size larger than 4. Moreover, we
prove that the flip graph of combinatorial 4-PPTs with
triangular outer face is connected and has dia\/meter
$O(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahopsv-fcppt-13,
author = {O.~Aichholzer and T.~Hackl and D.~Orden and A.~Pilz and
M.~Saumell and B.~Vogtenhuber},
title = {{{Flips in combinatorial pointed
pseudo-triangulations with face degree at most four
(extended abstract)}}},
booktitle = {Proc. $15^{th}$ Spanish Meeting on Computational Geometry
2013},
pages = {131--134},
year = 2013,
address = {Sevilla, Spain},
thackl_label = {33C},
category = {3b},
eprint = {1310.0833},
pdf = {/files/publications/geometry/ahopsv-fcppt-13.pdf},
abstract = {In this paper we consider the flip operation for
combinatorial pointed pseudo-triangulations where faces
have size~3 or~4, so-called \emph{combinatorial 4-PPTs}. We
show that every combinatorial 4-PPT is stretchable to a
geometric pseudo-triangulation, which in general is not the
case if faces may have size larger than 4. Moreover, we
prove that the flip graph of combinatorial 4-PPTs with
triangular outer face is connected and has dia\/meter
$O(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahsvw-sdala-13,
author = {O.~Aichholzer and T.~Hackl and V.~Sacrist\'{a}n and
B.~Vogtenhuber and R.~Wallner},
title = {{{Simulating distributed algorithms for lattice agents}}},
booktitle = {Proc. $15^{th}$ Spanish Meeting on Computational Geometry
2013},
pages = {81--84},
year = 2013,
address = {Sevilla, Spain},
thackl_label = {32C},
category = {3b},
pdf = {/files/publications/geometry/ahsvw-sdala-13.pdf},
htmlnote = {Link
to simulators page},
abstract = {We present a practical Java tool for simulating
synchronized distributed algorithms on sets of 2- and
3-dimensional square/cubic lattice-based agents. This
\emph{AgentSystem} assumes that each agent is capable to
change position in the lattice and that neighboring agents
can attach and detach from each other. In addition, it
assumes that each module has some constant size memory and
computation capability, and can send/receive constant size
messages to/from its neighbors. The system allows the user
to define sets of agents and sets of rules and apply one to
the other. The \emph{AgentSystem} simulates the
synchronized execution of the set of rules by all the
modules, and can keep track of all actions made by the
modules at each step, supporting consistency warnings and
error checking. Our intention is to provide a useful tool
for the researchers from geometric distributed algorithms.},
originalfile = {/geometry/cggg.bib}
}
@article{afhhpv-lbnsc-14,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{Lower bounds for the number of small convex $k$-holes}}},
journal = {Computational Geometry: Theory and Applications},
year = 2014,
volume = {47},
number = {5},
pages = {605--613},
thackl_label = {31J},
category = {3a},
doi = {http://dx.doi.org/10.1016/j.comgeo.2013.12.002},
pdf = {/files/publications/geometry/afhhpv-lbnsc-13-cgta.pdf},
abstract = {Let $S$ be a set of $n$ points in the plane in general
position, that is, no three points of $S$ are on a line. We
consider an Erd{\H{o}}s-type question on the least number
$h_k(n)$ of convex \mbox{$k$-holes} in $S$, and give
improved lower bounds on $h_k(n)$, for $3\leq k\leq 5$.
Specifically, we show that $h_{3}(n) \geq n^2 -
\frac{32n}{7} + \frac{22}{7}$, $h_{4}(n) \geq \frac{n^2}{2}
- \frac{9n}{4} - o(n)$, and $h_5(n) \geq \frac{3n}{4} -
o(n)$. We further settle several questions on sets of 12
points posed by Dehnhardt in 1987.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afhhpv-lbnsc-12,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{Lower bounds for the number of small convex $k$-holes}}},
booktitle = {Proc. $24^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2012},
pages = {247--252},
year = 2012,
address = {Charlottetown, PEI, Canada},
category = {3b},
thackl_label = {31C},
pdf = {/files/publications/geometry/afhhpv-lbnsc-12-cccg.pdf},
abstract = {Let $S$ be a set of $n$ points in the plane in general
position, that is, no three points of $S$ are on a line. We
consider an Erd{\H{o}}s-type question on the least number
$h_k(n)$ of convex \mbox{$k$-holes} in $S$, and give
improved lower bounds on $h_k(n)$, for $3\leq k\leq 5$.
Specifically, we show that $h_{3}(n) \geq n^2 -
\frac{32n}{7} + \frac{22}{7}$, $h_{4}(n) \geq \frac{n^2}{2}
- \frac{9n}{4} - o(n)$, and $h_5(n) \geq \frac{3n}{4} - o(n)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{acdhhlr-wmtss-12a,
author = {O. Aichholzer and H.~Cheng and S.L.~Devadoss and T.~Hackl
and S.~Huber and B.~Li and A.~Risteski},
title = {{{What makes a Tree a Straight Skeleton?}}},
booktitle = {Proc. $24^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2012},
pages = {253--258},
xpages = {267--272},
year = 2012,
address = {Charlottetown, PEI, Canada},
category = {3b},
thackl_label = {30C},
pdf = {/files/publications/geometry/acdhhlr-wmtss-12b-cccg.pdf},
abstract = {Let $G$ be a cycle-free connected straight-line graph with
predefined edge lengths and fixed order of incident edges
around each vertex. We address the problem of deciding
whether there exists a simple polygon $P$ such that $G$ is
the straight skeleton of $P$. We show that for given $G$
such a polygon $P$ might not exist, and if it exists it
might not be unique. For the later case we give an example
with exponentially many suitable polygons. For small star
graphs and caterpillars we show necessary and sufficient
conditions for constructing $P$.\\ Considering only the
topology of the tree, that is, ignoring the length of the
edges, we show that any tree whose inner vertices have
degree at least $3$ is isomorphic to the straight skeleton
of a suitable convex polygon.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{acdhhlr-wmtss-12,
author = {O. Aichholzer and H.~Cheng and S.L.~Devadoss and T.~Hackl
and S.~Huber and B.~Li and A.~Risteski},
title = {{{What makes a Tree a Straight Skeleton?}}},
booktitle = {Proc. $28^{th}$ European Workshop on Computational
Geometry EuroCG '12},
pages = {137--140},
year = 2012,
address = {Assisi, Italy},
category = {3b},
thackl_label = {30C},
pdf = {/files/publications/geometry/acdhhlr-wmtss-12.pdf},
abstract = {Let $G$ be a cycle-free connected straight-line graph with
predefined edge lengths and fixed order of incident edges
around each vertex. We address the problem of deciding
whether there exists a simple polygon $P$ such that $G$ is
the straight skeleton of $P$. We show that for given $G$
such a polygon $P$ might not exist, and if it exists it
might not be unique. For small star graphs and caterpillars
we give necessary and sufficient conditions for
constructing $P$.},
originalfile = {/geometry/cggg.bib}
}
@article{afghhhuvv-okkps-15,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Hernan
Gonzalez-Aguilar and Thomas Hackl and Marco A. Heredia and
Clemens Huemer and Jorge Urrutia and Pavel Valtr and Birgit
Vogtenhuber},
title = {{{On $k$-Gons and $k$-Holes in Point Sets}}},
journal = {Computational Geometry: Theory and Applications},
year = 2015,
volume = {48},
number = {7},
pages = {528--537},
category = {3a},
thackl_label = {29J},
arxiv = {1409.0081},
doi = {http://dx.doi.org/10.1016/j.comgeo.2014.12.007},
pdf = {/files/publications/geometry/afghhhuvv-okkps-15.pdf},
abstract = {We consider a variation of the classical
Erd{\H{o}}os-Szekeres problems on the existence and number of
convex $k$-gons and $k$-holes (empty $k$-gons) in a set of
$n$ points in the plane. Allowing the $k$-gons to be
non-convex, we show bounds and structural results on
maximizing and minimizing their numbers. Most noteworthy,
for any $k$ and sufficiently large $n$, we give a quadratic
lower bound for the number of $k$-holes, and show that this
number is maximized by sets in convex position. We also
provide an improved lower bound for the number of convex
6-holes.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afghhhuvv-okkps-11,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Hernan
Gonzalez-Aguilar and Thomas Hackl and Marco A. Heredia and
Clemens Huemer and Jorge Urrutia and Pavel Valtr and Birgit
Vogtenhuber},
title = {{{On $k$-Gons and $k$-Holes in Point Sets}}},
booktitle = {Proc. $23^{rd}$ Annual Canadian Conference on
Computational Geometry CCCG 2011},
pages = {21--26},
year = 2011,
address = {Toronto, Canada},
category = {3b},
thackl_label = {29C},
pdf = {/files/publications/geometry/afghhhuvv-okkps-11.pdf},
abstract = {We consider a variation of the classical
Erd{\H{o}}os-Szekeres problems on the existence and number of
convex $k$-gons and $k$-holes (empty $k$-gons) in a set of
$n$ points in the plane. Allowing the $k$-gons to be
non-convex, we show bounds and structural results on
maximizing and minimizing their numbers. Most noteworthy,
for any $k$ and sufficiently large $n$, we give a quadratic
lower bound for the number of $k$-holes, and show that this
number is maximized by sets in convex position. We also
provide an improved lower bound for the number of convex
6-holes.},
originalfile = {/geometry/cggg.bib}
}
@incollection{ahv-5g5h-12,
author = {O. Aichholzer and T. Hackl and B. Vogtenhuber},
title = {{{On 5-{G}ons and 5-{H}oles}}},
volume = {7579},
issue = {},
editor = {A.~Marquez and P.~Ramos and J.~Urrutia},
booktitle = {Computational Geometry: XIV Spanish Meeting on
Computational Geometry, EGC 2011, Festschrift
Dedicated to Ferran Hurtado on the Occasion of His
60th Birthday, Alcal{\'a} de Henares, Spain, June 27-30,
2011, Revised Selected Papers},
xxbooktitle = {Special issue: XIV Encuentros de Geometr\'{\i}a
Computacional ECG2011},
series = {Lecture Notes in Computer Science (LNCS)},
category = {3a},
thackl_label = {28J},
pdf = {/files/publications/geometry/ahv-5g5h-12.pdf},
pages = {1--13},
year = 2012,
publisher = {Springer},
abstract = {We consider an extension of a question of Erd{\H{o}}s on the
number of $k$-gons in a set of $n$ points in the plane.
Relaxing the convexity restriction we obtain results on
5-gons and 5-holes (empty 5-gons). In particular, we show a
direct relation between the number of non-convex 5-gons and
the rectilinear crossing number, provide an improved lower
bound for the number of convex 5-holes any point set must
contain, and prove that the number of general 5-holes is
asymptotically maximized for point sets in convex
position.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahv-o5g5h-11,
author = {O. Aichholzer and T. Hackl and B. Vogtenhuber},
title = {{{On 5-gons and 5-holes}}},
booktitle = {Proc. XIV Encuentros de Geometr\'{\i}a Computacional},
category = {3b},
thackl_label = {28C},
pages = {7--10},
pdf = {/files/publications/geometry/ahv-o5g5h-11.pdf},
year = 2011,
address = {Alcal\'a, Spain},
abstract = {We consider an extention of a question of Erd{\H{o}}s on the
number of $k$-gons in a set of $n$ points in the plane.
Relaxing the convexity restriction we obtain results on
5-gons and 5-holes (empty 5-gons).},
originalfile = {/geometry/cggg.bib}
}
@article{afghhhuv-4hps-14,
author = {O.~Aichholzer and R.~Fabila-Monroy and
H.~Gonz{\'a}lez-Aguilar and T.~Hackl and M.A.~Heredia and
C.~Huemer and J.~Urrutia and B.~Vogtenhuber},
title = {{{\mbox{4-Holes} in Point Sets}}},
journal = {Computational Geometry: Theory and Applications},
note = {Special Issue on the 27th European Workshop on Computational Geometry (EuroCG 2011)},
year = 2014,
volume = {47},
number = {6},
pages = {644--650},
thackl_label = {27J},
category = {3a},
pdf = {/files/publications/geometry/afghhhuv-4hps-14.pdf},
doi = {http://dx.doi.org/10.1016/j.comgeo.2013.12.004},
abstract = {We consider a variant of a question of Erd{\H{o}}s on the
number of empty $k$-gons ($k$-holes) in a set of $n$ points
in the plane, where we allow the $k$-gons to be non-convex.
We show bounds and structural results on maximizing and
minimizing the number of general 4-holes, and maximizing
the number of non-convex 4-holes. In particular, we show
that for $n\geq 9$, the maximum number of general 4-holes
is ${n \choose 4}$, the minimum number of general 4-holes
is at least $\frac{5}{2}n^2 - \Theta(n)$, and the maximum
number of non-convex 4-holes is at least
$\frac{1}{2}n^3-\Theta(n^2\log n)$ and at most
$\frac{1}{2}n^3-\Theta(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afghhhuv-4hps-11,
author = {O.~Aichholzer and R.~Fabila-Monroy and
H.~Gonz{\'a}lez-Aguilar and T.~Hackl and M.A.~Heredia and
C.~Huemer and J.~Urrutia and B.~Vogtenhuber},
title = {{{\mbox{4-Holes} in Point Sets}}},
booktitle = {Proc. $27^{th}$ European Workshop on Computational
Geometry EuroCG '11},
pages = {115--118},
year = 2011,
address = {Morschach, Switzerland},
thackl_label = {27C},
category = {3b},
pdf = {/files/publications/geometry/afghhhuv-4hps-11.pdf},
abstract = {We consider a variant of a question of Erd{\H{o}}s on the
number of empty $k$-gons ($k$-holes) in a set of $n$ points
in the plane, where we allow the $k$-gons to be non-convex.
We show bounds and structural results on maximizing and
minimizing the number of general \mbox{4-holes}, and
maximizing the number of non-convex \mbox{4-holes}.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aahw-emacc-11,
author = {O. Aichholzer and W. Aigner and T. Hackl and N. Wolpert},
title = {{{Exact medial axis computation for circular arc
boundaries}}},
booktitle = {Proc. $7^{th}$ International Conference on Curves and
Surfaces 2010 (Avignon, France), LNCS 6920},
editor = {J.D. Boissonat and M.L. Mazure and L.L. Schumaker},
address = {Avignon, France},
publisher = {Springer},
series = {Lecture Notes in Computer Science (LNCS)},
number = {6920},
category = {3b},
thackl_label = {26C},
pages = {28--42},
year = {2011},
pdf = {/files/publications/geometry/aahw-emacc-11.pdf},
abstract = {We propose a method to compute the algebraically correct
medial axis for simply connected planar domains which are
given by boundary representations composed of rational
circular arcs. The algorithmic approach is based on the
Divide-and-Conquer paradigm. However, we show how to avoid
inaccuracies in the medial axis computations arising from a
non-algebraic biarc construction of the boundary. To this
end we introduce the Exact Circular Arc Boundary
representation (ECAB), which allows algebraically exact
calculation of bisector curves. Fractions of these bisector
curves are then used to construct the exact medial axis. We
finally show that all necessary computations can be
performed over the fild of rational numbers with a small
number of adjoint square-roots.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{st10d,
author = {Oswin Aichholzer and Daniel Detassis and Thomas Hackl and
Gerald Steinbauer and Johannes Thonhauser},
title = {{"{Playing Pylos with an Autonomous Robot}"}},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS)},
address = {Taipei, Taiwan},
pages = {2507--2508},
category = {3b},
thackl_label = {25C},
pdf = {/files/publications/geometry/adhst-ppwar-10.pdf},
year = {2010},
abstract = {In this paper we present an autonomous robot which is able
to play the board game Pylos (Copyright by GIGAMIC s.a.
France) with a human opponent.},
alpha_part = {25C},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahv-cppt-10,
author = {O. Aichholzer and T.~Hackl and B.~Vogtenhuber},
title = {{{Compatible Pointed Pseudo-Triangulations}}},
booktitle = {Proc. $22^{nd}$ Annual Canadian Conference on
Computational Geometry CCCG 2010},
pages = {91--94},
year = 2010,
address = {Winnipeg, Manitoba, Canada},
category = {3b},
thackl_label = {24C},
pdf = {/files/publications/geometry/ahv-cppt-10.pdf},
abstract = {For a given point set $S$ (in general position), two
pointed pseudo-triangulations are compatible if their union
is plane. We show that for any set $S$ there exist two
maximally disjoint compatible pointed
pseudo-triangulations, that is, their union is a
triangulation of~$S$. In contrast, we show that there are
point sets~$S$ and pointed pseudo-triangulations~$T$ such
that there exists no pointed pseudo-triangulation that is
compatible to and different from~$T$.},
originalfile = {/geometry/cggg.bib}
}
@article{afhkprv-bdt-12,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and M.~van
Kreveld and A.~Pilz and P.~Ramos and B.~Vogtenhuber},
title = {{{Blocking Delaunay Triangulations}}},
year = 2013,
volume = {46},
number = {2},
journal = {Computational Geometry: Theory and Applications},
pages = {154--159},
category = {3a},
oaich_label = {},
thackl_label = {23J},
doi = {http://dx.doi.org/10.1016/j.comgeo.2012.02.005},
pmcid = {3587385},
pmcurl = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3587385/},
pdf = {/files/publications/geometry/afhkprv-bdt-13.pdf},
abstract = {Given a set $B$ of $n$ blue points in general position, we
say that a set of red points $R$ blocks $B$ if in the
Delaunay triangulation of $B\cup R$ there is no edge
connecting two blue points. We give the following bounds
for the size of the smallest set $R$ blocking $B$:
(i)~$3n/2$ red points are always sufficient to block a set
of $n$ blue points, (ii)~if $B$ is in convex position,
$5n/4$ red points are always sufficient to block it, and
(iii)~at least $n-1$ red points are always necessary, and
there exist sets of blue points that require at least $n$
red points to be blocked.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afhkprv-bdt-10,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and M.~van
Kreveld and A.~Pilz and P.~Ramos and B.~Vogtenhuber},
title = {{{Blocking Delaunay Triangulations}}},
booktitle = {Proc. $22^{nd}$ Annual Canadian Conference on
Computational Geometry CCCG 2010},
pages = {21--24},
year = 2010,
address = {Winnipeg, Manitoba, Canada},
category = {3b},
thackl_label = {23C},
pdf = {/files/publications/geometry/afhkprv-bdt-10.pdf},
abstract = {Given a set $B$ of $n$ blue points in general position, we
say that a set of red points $R$ blocks $B$ if in the
Delaunay triangulation of $B\cup R$ there is no edge
connecting two blue points. We give the following bounds
for the size of the smallest set $R$ blocking $B$:
(i)~$3n/2$ red points are always sufficient to block a set
of $n$ blue points, (ii)~if $B$ is in convex position,
$5n/4$ red points are always sufficient to block it, and
(iii)~at least $n-1$ red points are always necessary, and
there exist sets of blue points that require at least $n$
red points to be blocked.},
originalfile = {/geometry/cggg.bib}
}
@article{aahhpv-3cpt-15,
author = {O.~Aichholzer and F.~Aurenhammer and T. Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{\mbox{3-Colorability} of Pseudo-Triangulations}}},
journal = {Int'l Journal of Computational Geometry \& Applications},
year = 2015,
volume = {25},
category = {3a},
number = {4},
oaich_label = {},
thackl_label = {22J},
pages = {283-298},
pdf = {/files/publications/geometry/aahhpv-3cpt-10.pdf},
doi = {http://dx.doi.org/10.1142/S0218195915500168},
xarxiv = {},
abstract = {Deciding $3$-colorability for general plane graphs is
known to be an NP-complete problem. However, for certain
classes of plane graphs, like triangulations, polynomial
time algorithms exist. We consider the family of
pseudo-triangulations (a generalization of triangulations)
and prove NP-completeness for this class, even if the
maximum face-degree is bounded to four, or pointed
pseudo-triangulations with maximum face degree five are
considered. As a complementary result, we show that for
pointed pseudo-triangulations with maximum face-degree
four, a $3$-coloring always exists and can be found in
linear time.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aahhpv-3cpt-10,
author = {O.~Aichholzer and F.~Aurenhammer and T. Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{\mbox{3-Colorability} of Pseudo-Triangulations}}},
booktitle = {Proc. $26^{th}$ European Workshop on Computational
Geometry EuroCG '10},
pages = {21--24},
year = 2010,
address = {Dortmund, Germany},
thackl_label = {22C},
pdf = {/files/publications/geometry/aahhpv-3cpt-10.pdf},
abstract = {Deciding $3$-colorability for general plane graphs is
known to be an NP-complete problem. However, for certain
classes of plane graphs, like triangulations, polynomial
time algorithms exist. We consider the family of
pseudo-triangulations (a generalization of triangulations)
and prove NP-completeness for this class, even if the
maximum face-degree is bounded to four, or pointed
pseudo-triangulations with maximum face degree five are
considered. As a complementary result, we show that for
pointed pseudo-triangulations with maximum face-degree
four, a $3$-coloring always exists and can be found in
linear time.},
originalfile = {/geometry/cggg.bib}
}
@phdthesis{h-rlt-10,
author = {T.~Hackl},
title = {{{Relaxing and lifting triangulations}}},
school = {IST \& IGI-TU Graz, Austria},
year = 2010,
category = {5},
thackl_label = {21T},
pdf = {/files/publications/geometry/h-rlt-10.pdf},
abstract = {The relaxation of triangulations to pseudo-triangulations
is already well known. We investigate the differences
between triangulations and pseudo-triangulations with
respect to the optimality criterion of minimal total edge
length. We show that, although (especially pointed)
pseudo-triangulations have significantly less edges than
triangulations, the minimum weight pseudo-triangulation can
be a triangulation in general. We study the flip graphs for
pseudo-triangulations whose maximum vertex degree is
bounded by some constant. For point sets in convex
position, we prove that the flip graph of such
pseudo-triangulations is connected if and only if the
degree bound is larger than~6. We present an upper bound of
$O(n^2)$ on the diameter of this flip graph and also
discuss point sets in general position. Finally we relax
triangulations even beyond the concept of
pseudo-triangulations and introduce the class of
pre-triangulations. When considering liftings of
triangulations in general polygonal domains and flipping
therein, pre-triangulations arise naturally in three
different contexts: When characterizing polygonal complexes
that are liftable to three-space in a strong sense, in flip
sequences for general liftable polygonal complexes, and as
graphs of maximal locally convex functions.},
originalfile = {/geometry/cggg.bib}
}
@article{ahhprsv-pgpc-10,
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}}},
year = 2014,
volume = {30},
number = {1},
category = {3a},
journal = {Graphs and Combinatorics},
pdf = {/files/publications/geometry/ahhprsv-pgpc-12.pdf},
thackl_label = {20J},
pages = {47--69},
publisher = {Springer},
htmlnote = {For
Springer Online First.},
doi = {http://dx.doi.org/10.1007/s00373-012-1247-y},
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.},
originalfile = {/geometry/cggg.bib}
}
@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}}},
pdf = {/files/publications/geometry/ahhprsv-pgpc-09.pdf},
oaich_label = {83},
thackl_label = {20C},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $11^{th}$
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.},
originalfile = {/geometry/cggg.bib}
}
@article{ahorrss-fgbdt-12,
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}}},
journal = {Graphs and Combinatorics},
volume = {29},
number = {6},
pages = {1577--1593},
category = {3a},
pdf = {/files/publications/geometry/ahorrss-fgbdt-20120426.pdf},
thackl_label = {19J},
year = 2013,
eprint = {0903.2184},
archiveprefix = {arXiv},
htmlnote = {For
Springer Online First.},
doi = {http://dx.doi.org/10.1007/s00373-012-1229-0},
abstract = {We study flip graphs of triangulations whose maximum
vertex degree is bounded by a constant $k$. In particular,
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 pointed pseudo-triangulations can be
disconnected for $k \leq 9$, and flip graphs of
triangulations can be disconnected for any~$k$.
Additionally, we consider a relaxed version of the original
problem. We allow the violation of the degree bound $k$ by
a small constant. Any two triangulations with maximum
degree at most $k$ of a convex point set are connected in
the flip graph by a path of length $O(n \log n)$, where
every intermediate triangulation has maximum degree at most
$k+4$.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
pages = {509--513},
pdf = {/files/publications/geometry/ahorrss-fgbdt-09.pdf},
oaich_label = {84},
thackl_label = {19C},
year = 2009,
eprint = {0903.2184},
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$.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
pages = {139--142},
pdf = {/files/publications/geometry/aadhtv-lubne-09.pdf},
oaich_label = {79},
thackl_label = {18C},
year = 2009,
address = {Brussels, Belgium},
htmlnote = {Also available as Research Report RR-6748 "Counting
Quadrics and Delaunay Triangulations and a new Convex Hull
Theorem", INRIA, 2008, at
http://hal.inria.fr/inria-00343651.},
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)$.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3a},
doi = {http://dx.doi.org/10.1137/090767947},
oaich_label = {78b},
thackl_label = {17J},
pdf = {/files/publications/geometry/ahhhv-lbpsa-09b.pdf},
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).},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
pages = {133--136},
pdf = {/files/publications/geometry/ahhhv-lbpsa-09.pdf},
oaich_label = {78},
thackl_label = {17C},
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).},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
pages = {167--170},
arxiv = {1503.05062},
pdf = {/files/publications/geometry/affhhuv-mimp-09.pdf},
oaich_label = {80},
thackl_label = {16C},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
note = {Special Issue on the 25th Annual Symposium on
Computational Geometry (SoCG'09)},
pages = {688--699},
volume = {43},
number = {8},
category = {3a},
doi = {http://dx.doi.org/10.1016/j.comgeo.2010.04.004},
year = 2010,
pdf = {/files/publications/geometry/aaahjpr-dcvdr-09b.pdf},
thackl_label = {15J},
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\log n)$
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
pages = {189--197},
pdf = {/files/publications/geometry/aaahjpr-dcvdr-09b.pdf},
oaich_label = {81b},
thackl_label = {15C},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
pages = {293--296},
pdf = {/files/publications/geometry/aaahjpr-dcvdr-09.pdf},
oaich_label = {81},
thackl_label = {15C},
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.},
originalfile = {/geometry/cggg.bib}
}
@article{affhhj-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},
category = {3a},
oaich_label = {75b},
thackl_label = {14J},
pdf = {/files/publications/geometry/affhhj-emt-09.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})$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{affhhj-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. $20^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2008},
pages = {75--78},
year = 2008,
address = {Montreal, Quebec, Canada},
category = {3b},
oaich_label = {75},
thackl_label = {14C},
pdf = {/files/publications/geometry/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})$.},
originalfile = {/geometry/cggg.bib}
}
@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 = {12},
category = {3a},
number = {1},
oaich_label = {83},
thackl_label = {13J},
pages = {75--86},
pdf = {/files/publications/geometry/acffhhhw-erncc-09.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.},
originalfile = {/geometry/cggg.bib}
}
@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},
pdf = {/files/publications/geometry/acffhhhw-erncc-08.pdf},
oaich_label = {73},
thackl_label = {13C},
year = 2008,
address = {Nancy, France},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
postscript = {/files/publications/geometry/aahkprsv-spia-08.ps.gz},
oaich_label = {74},
thackl_label = {12C},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3a},
number = {5},
oaich_label = {77},
thackl_label = {11J},
doi = {http://dx.doi.org/10.1016/j.cad.2008.08.008},
pdf = {/files/publications/geometry/aaahjr-macpf-09.pdf},
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.},
originalfile = {/geometry/cggg.bib}
}
@proceedings{ah-pewcg-07,
author = {O. Aichholzer and T. Hackl},
editor = {O. Aichholzer and T. Hackl},
title = {{{Collection of Abstracts of the $23^{rd}$ European Workshop
on Computational Geometry 2007}}},
booktitle = {{{Collection of Abstracts of the $23^{rd}$ European Workshop
on Computational Geometry 2007}}},
pages = {1--254},
oaich_label = {69},
thackl_label = {10P},
year = {2007},
address = {Graz, Austria},
isbn = {978-3-902465-62-7},
htmlnote = {Available at the conference homepage http://ewcg07.tugraz.at/EuroCG2007Abstracts.pdf.},
abstract = {The {\bf $\mathbf{ 23^{rd}}$ European Workshop on
Computational Geometry} (EWCG'07) was held at the
University of Technology in Graz (Austria) on March
$19^{th} - 21^{st}$, 2007. More information about the
workshop can be found at {\tt http://ewcg07.tugraz.at}.
This collection of extended abstracts contains the $60$
scientific contributions as well as three invited talks
presented at the workshop. The submission record of over
$70$ abstracts from more than $20$ different countries,
covering a wide range of topics, shows that Computational
Geometry is a lively and still growing research field in
Europe.},
originalfile = {/geometry/cggg.bib}
}
@article{ahhhssv-mmaps-09,
author = {O. Aichholzer and T. Hackl and M.~Hoffmann and C.~Huemer
and A.~P{\'o}r and F.~Santos and B.~Speckmann and B.~Vogtenhuber},
title = {{{Maximizing Maximal Angles for Plane Straight Line Graphs}}},
year = 2013,
volume = {46},
number = {1},
journal = {Computational Geometry: Theory and Applications},
pages = {17--28},
category = {3a},
oaich_label = {65c},
thackl_label = {9J},
pdf = {/files/publications/geometry/ahhhpssv-mmaps-12.pdf},
doi = {http://dx.doi.org/10.1016/j.comgeo.2012.03.002},
eprint = {0705.3820},
archiveprefix = {arXiv},
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.},
originalfile = {/geometry/cggg.bib}
}
@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}}},
pdf = {/files/publications/geometry/ahhhssv-mmaps-07b.pdf},
oaich_label = {65b},
thackl_label = {9C},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $10^{th}$
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {4619},
address = {Halifax, Nova Scotia, Canada},
pages = {458--469},
year = 2007,
eprint = {0705.3820},
doi = {10.1007/978-3-540-73951-7_40},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
pdf = {/files/publications/geometry/ahhhssv-mmaps-07.pdf},
oaich_label = {65},
thackl_label = {9C},
year = 2007,
address = {Graz, Austria},
eprint = {0705.3820},
archiveprefix = {arXiv},
htmlnote = {Also available as FSP-report S092-48, Austria, 2007, at http://www.industrial-geometry.at/techrep.php.},
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.},
originalfile = {/geometry/cggg.bib}
}
@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}}},
oaich_label = {68b},
thackl_label = {8J},
year = 2011,
volume = {21},
number = {1},
journal = {Int'l. Journal of Computational Geometry \& Applications},
pages = {47--69},
category = {3a},
pdf = {/files/publications/geometry/aahjos-csacb-09.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.},
originalfile = {/geometry/cggg.bib}
}
@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}}},
oaich_label = {68},
thackl_label = {8C},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $10^{th}$
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {4619},
address = {Halifax, Nova Scotia, Canada},
pages = {374--385},
year = 2007,
category = {3b},
postscript = {/files/publications/geometry/aahjos-csacb-07.ps.gz},
htmlnote = {Also available as FSP-report S092-38, Austria, 2006, at http://www.industrial-geometry.at/techrep.php.},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
pdf = {/files/publications/geometry/aahkpp-abtop-07.pdf},
oaich_label = {66},
thackl_label = {7C},
year = 2007,
address = {Graz, Austria},
htmlnote = {Also available as FSP-report S092-49, Austria, 2007, at http://www.industrial-geometry.at/techrep.php.},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3a},
oaich_label = {71a},
thackl_label = {6J},
year = 2009,
pdf = {/files/publications/geometry/aahs-mwpt-09.pdf},
abstract = {In this note we discuss some structural properties of
minimum weight pseudo-triangulations of point sets.},
originalfile = {/geometry/cggg.bib}
}
@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. $19^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2007},
pages = {209--212},
year = 2007,
address = {Ottawa, Ontario, Canada},
category = {3b},
oaich_label = {71},
thackl_label = {6C},
pdf = {/files/publications/geometry/aahs-pmwpt-07.pdf},
abstract = {In this note we discuss some structural properties of
minimum weight (pointed) pseudo-triangulations.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3a},
oaich_label = {60},
thackl_label = {5J},
postscript = {/files/publications/geometry/aahh-ccps-06.ps.gz},
htmlnote = {Also available as FSP-report S092-45, Austria, 2006, at http://www.industrial-geometry.at/techrep.php.},
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. },
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3a},
number = {},
oaich_label = {61a},
thackl_label = {4J},
pages = {701--725},
postscript = {/files/publications/geometry/aah-ptlc-06a.ps.gz},
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.},
originalfile = {/geometry/cggg.bib}
}
@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},
category = {3b},
oaich_label = {61},
thackl_label = {4C},
address = {Sedona, Arizona, USA},
postscript = {/files/publications/geometry/aah-ptlc-06.ps.gz},
htmlnote = {Also available as FSP-report S092-6, Austria, 2006, at http://www.industrial-geometry.at/techrep.php.},
abstract = {We introduce and discuss the concept of
pre-triangulations, a relaxation of triangulations that
goes beyond the well-established class of
pseudo-triangulations.},
originalfile = {/geometry/cggg.bib}
}
@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)},
oaich_label = {58a},
thackl_label = {3J},
category = {3a},
postscript = {/files/publications/geometry/ahhhkv-npgg-06.ps.gz},
year = 2007,
doi = {https://doi.org/10.1007/s00373-007-0704-5},
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.},
originalfile = {/geometry/cggg.bib}
}
@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. $17^{th}$ Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA)},
pages = {504-513},
year = 2006,
address = {Miami, Florida, USA},
category = {3b},
oaich_label = {58},
thackl_label = {3C},
pdf = {/files/publications/geometry/ahhhkv-npg-06.pdf},
htmlnote = {Also available as FSP-report S092-8, Austria, 2006, at http://www.industrial-geometry.at/techrep.php.},
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.},
originalfile = {/geometry/cggg.bib}
}
@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. $15^{th}$ Annual Fall Workshop on Computational
Geometry and Visualization},
pages = {31-32},
year = 2005,
address = {Philadelphia, Pennsylvania, USA},
category = {3b},
oaich_label = {58b},
thackl_label = {3C},
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.},
originalfile = {/geometry/cggg.bib}
}
@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)},
category = {3a},
oaich_label = {57a},
thackl_label = {2J},
year = 2008,
postscript = {/files/publications/geometry/aaghhhkrv-mefpp-06.ps.gz},
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.},
originalfile = {/geometry/cggg.bib}
}
@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. $17^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2005},
pages = {123--126},
year = 2005,
address = {Windsor, Ontario, Canada},
category = {3b},
oaich_label = {57},
thackl_label = {2C},
postscript = {/files/publications/geometry/aaghhhkrv-mefpp-05.ps.gz},
htmlnote = {Also available as FSP-report S092-4, Austria, 2005, at http://www.industrial-geometry.at/techrep.php.},
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.},
originalfile = {/geometry/cggg.bib}
}
@mastersthesis{h-mpts-04,
author = {T. Hackl},
title = {{{Manipulation of Pseudo-Triangular Surfaces}}},
school = {IGI-TU Graz, Austria},
year = 2004,
category = {11},
postscript = {/files/publications/geometry/h-mpts-04.ps.gz},
pdf = {/files/publications/geometry/h-mpts-04.pdf},
thackl_label = {1T},
abstract = {This diploma thesis deals with pseudo-triangular surfaces
and flipping therein, as introduced by Aichholzer et al.
They defined a {\em projectivity\/} attribute for
pseudo-triangulations and introduced a {\em stability\/}
condition to decide it. Using a program from preliminary
work of this thesis, we found a counter-example for
concluding from stability to projectivity. Our aim is to
redefine the stability-condition to be able to correctly
conclude to projectivity in all cases. Our investigations
lead to a proper combinatorial understanding of the
projectivity of pseudo-triangulations. Thereby, we find a
new class of cell complexes: {\em punched
pseudo-triangulations}, which are a relaxation of
pseudo-triangulations. In addition, we prove the existence
of finite flipping sequences to the optimal surface that
avoid the creation of non-pseudo-triangular cell complexes.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhpv-ltdbm-14,
author = {Aichholzer, Oswin and Barba, Luis and Hackl, Thomas
and Pilz, Alexander and Vogtenhuber, Birgit},
title = {{{Linear Transformation Distance for Bichromatic
Matchings}}},
booktitle = {Proc. 30\textsuperscript{th} Symposium on
Computational Geometry (SOCG 2014)},
remseries = {SOCG'14},
year = {2014},
isbn = {978-1-4503-2594-3},
location = {Kyoto, Japan},
pages = {154--162},
articleno = {154},
numpages = {9},
url = {http://doi.acm.org/10.1145/2582112.2582151},
doi = {http://dx.doi.org/10.1145/2582112.2582151},
acmid = {2582151},
publisher = {ACM},
remaddress = {New York, NY, USA},
keywords = {bichromatic point set, compatible matchings,
perfect matchings, reconfiguration problem,
transformation graph},
arxiv = {1312.0884v1},
pdf = {/files/publications/geometry/abhpv-ltdbm-14.pdf},
category = {3b},
thackl_label = {41C},
abstract = {Let $P=B\cup R$ be a set of $2n$ points in general
position, where $B$ is a set of $n$ blue points and
$R$ a set of $n$ red points. A \emph{$BR$-matching}
is a plane geometric perfect matching on $P$ such
that each edge has one red endpoint and one blue
endpoint. Two $BR$-matchings are compatible if their
union is also plane.\\ The \emph{transformation
graph of $BR$-matchings} contains one node for each
$BR$-matching and an edge joining two such nodes if
and only if the corresponding two $BR$-matchings are
compatible. In SoCG 2013 it has been shown by
Aloupis, Barba, Langerman, and Souvaine that this
transformation graph is always connected, but its
diameter remained an open question. In this paper we
provide an alternative proof for the connectivity of
the transformation graph and prove an upper bound of
$2n$ for its diameter, which is asymptotically
tight.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhv-ssmvd-14,
author = {Oswin Aichholzer and Thomas Hackl and Stefan Huber and Birgit Vogtenhuber},
title = {{{Straight Skeletons by Means of Voronoi Diagrams Under Polyhedral Distance Functions}}},
booktitle = {Proc. $26^{th}$ Annual Canadian Conference on
Computational Geometry (CCCG 2014)},
pages = {online},
year = 2014,
address = {Halifax, Nova Scotia, Canada},
category = {3b},
arxiv = {},
pdf = {/files/publications/geometry/ahhv-ssmvd-14.pdf},
thackl_label = {42C},
abstract = {We consider the question under which circumstances the straight
skeleton and the Voronoi diagram of a given input shape coincide.
More precisely, we investigate convex distance functions that stem
from centrally symmetric convex polyhedra as unit balls and derive
sufficient and necessary conditions for input shapes in order to
obtain identical straight skeletons and Voronoi diagrams with
respect to this distance function.
This allows us to present a new approach for generalizing straight
skeletons by means of Voronoi diagrams, so that the straight
skeleton changes continuously when vertices of the input shape are
dislocated, that is, no discontinuous changes as in the Euclidean
straight skeleton occur.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahkklpsw-ppstp-14,
author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Marc
van Kreveld and Maarten L\"offler and Alexander Pilz and Bettina Speckmann and Emo Welzl},
title = {{{Packing Plane Spanning Trees and Paths in Complete Geometric Graphs}}},
booktitle = {Proc. $26^{th}$ Annual Canadian Conference on
Computational Geometry (CCCG 2014)},
pages = {online},
year = 2014,
address = {Halifax, Nova Scotia, Canada},
category = {3b},
arxiv = {},
pdf = {/files/publications/geometry/ahkklpsw-ppstp-14.pdf},
thackl_label = {43C},
abstract = {We consider the following question: How many
edge-disjoint plane spanning trees are contained in a complete
geometric graph $GK_n$ on any set $S$ of $n$ points in general
position in the plane?},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahlmv-efdpc-14,
author = {Oswin Aichholzer and Thomas Hackl and Sarah Lutteropp and Tamara Mchedlidze and Birgit Vogtenhuber},
title = {{{Embedding Four-directional Paths on Convex Point Sets}}},
booktitle = {Proc. $22^{nd}$ International Symposium on Graph Drawing (GD 2014)},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {8871},
nopublisher = {Springer, Heidelberg},
editor = {C.~Duncan and A.~Symvonis},
pages = {355--366},
year = 2014,
address = {W{\"u}rzburg, Germany},
category = {3b},
arxiv = {1408.4933},
pdf = {/files/publications/geometry/ahlmv-efdpc-14.pdf},
thackl_label = {44C},
abstract = {A directed path whose edges are assigned labels ``up'', ``down'', ``right'', or ``left'' is called \emph{four-directional}, and \emph{three-directional} if at most three out of the four labels are used.
A \emph{direction-consistent embedding} of an \mbox{$n$-vertex} four-directional path $P$ on a set $S$ of $n$ points in the plane
is a straight-line drawing of $P$ where each vertex of $P$ is mapped to a distinct point of $S$ and every edge points to the direction specified by its label.
We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets.},
originalfile = {/geometry/cggg.bib}
}
@article{ahlmv-efdpc-15,
author = {Oswin Aichholzer and Thomas Hackl and Sarah Lutteropp and Tamara Mchedlidze and Birgit Vogtenhuber},
title = {{{Embedding Four-directional Paths on Convex Point Sets}}},
journal = {Journal of Graph Algorithms and Applications},
year = 2015,
volume = {19},
number = {2},
pages = {743--759},
thackl_label = {44J},
category = {3a},
issn = {1526-1719},
doi = {http://dx.doi.org/10.7155/jgaa.00368},
arxiv = {1408.4933},
pdf = {/files/publications/geometry/ahlmv-efdpc-14.pdf},
abstract = {A directed path whose edges are assigned labels
``up'', ``down'', ``right'', or ``left'' is called
\emph{four-directional}, and
\emph{three-directional} if at most three out of the
four labels are used. A \emph{direction-consistent
embedding} of an \mbox{$n$-vertex} four-directional
path $P$ on a set $S$ of $n$ points in the plane is
a straight-line drawing of $P$ where each vertex of
$P$ is mapped to a distinct point of $S$ and every
edge points to the direction specified by its label.
We study planar direction-consistent embeddings of
three- and four-directional paths and provide a
complete picture of the problem for convex point
sets.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{bkhas-pnmmh-14,
author = {Sven Bock and Roland Kl{\"o}bl and Thomas Hackl and Oswin Aichholzer and
Gerald Steinbauer},
title = {{"{Playing Nine Men's Morris with the Humanoid Robot Nao}"}},
booktitle = {Proc. Austrian Robotics Workshop (AWS 2014)},
address = {Linz, Austria},
pages = {58--63},
category = {3b},
thackl_label = {45C},
pdf = {/files/publications/geometry/bkhas-pnmmh-14.pdf},
year = {2014},
abstract = {Playing games is an important aspect in human life
in order to develop skills or in terms of
entertainment. Games also play a major role in
research such as Artificial Intelligence and
Robotics. In this paper we present an approach to
enable the humanoid robot Nao to play a board game
against a human opponent. We discuss the challenges
that arise by the task of playing a board game with
a humanoid robot, provide solutions for the Nao, and
introduce our proof-of-concept implementation for
the board game Nine Men's Morris. Finally, we will
present a first experimental evaluation of the
approach. The main contribution of this paper is the
integration of various techniques into one real
robot system, enabling it to manage a complex task
such as playing a board game.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahpsv-dmgdc-15,
author = {Oswin Aichholzer and Thomas Hackl and Alexander Pilz and Gelasio Salazar and Birgit Vogtenhuber},
title = {{{Deciding monotonicity of good drawings of the complete graph}}},
booktitle = {Proc. XVI Spanish Meeting on Computational Geometry (EGC 2015)},
pages = {33--36},
year = {2015},
category = {3b},
thackl_label = {47C},
pdf = {/files/publications/geometry/ahpsv-dmgdc-15.pdf},
abstract = {We describe an $O(n^5)$ time algorithm for deciding whether a good drawing of the complete graph $K_n$, given in terms of its rotation system, can be re-drawn using only $x$-monotone arcs.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhprvv-hitcps-16,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and A.~Pilz and P.~Ramos and B.~Vogtenhuber and P.~Valtr},
title = {{{Holes in two convex point sets}}},
booktitle = {Proc. $32^{st}$ European Workshop on Computational Geometry EuroCG '16},
pages = {263--266},
year = 2016,
address = {Lugano, Switzerland},
category = {3b},
eprint = {},
pdf = {/files/publications/geometry/abhprvv-hitcps-16.pdf},
thackl_label = {52C},
abstract = {Let $S$ be a finite set of $n$ points in the plane in
general position. A $k-hole$ of $S$ is a simple
polygon with $k$ vertices from $S$ and no points of
$S$ in its interior. A simple polygon $P$ is
$l$-convex if no straight line intersects the
interior of $P$ in more than $l$ connected
components. Moreover, a point set $S$ is $l$-convex
if there exists an $l$-convex polygonalization of
$S$. Considering a typical Erd{\H{o}}s-Szekeres type
problem we show that every 2-convex point set of
size $n$ contains a convex hole of size $\Omega(log n)$.
This is in contrast to the well known fact that
there exist general point sets of arbitrary size
that do not contain a convex 7-hole. Further, we
show that our bound is tight by providing a
construction for 2-convex point sets with holes of
size at most $O(log n)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhprvv-hi2cps-17,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and A.~Pilz and P.~Ramos and P.~Valtr and B.~Vogtenhuber},
title = {{{Holes in 2-convex point sets}}},
booktitle = {Proc. $28^{th}$ International Workshop on Combinatorial Algorithms (IWOCA2017)},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {10765},
pages = {169--181},
year = 2018,
address = {Newcastle, Australia},
doi = {https://doi.org/10.1007/978-3-319-78825-8_14},
abstract = {Let $S$ be a set of $n$ points in the plane in general position
(no three points from $S$ are collinear).
For a positive integer $k$, a \emph{$k$-hole} in $S$ is a convex polygon
with $k$ vertices from~$S$ and no points of~$S$ in its interior.
For a positive integer $l$, a simple polygon~$P$ is \emph{$l$-convex}
if no straight line intersects the interior of~$P$ in more than $l$ connected components.
A point set $S$ is \emph{$l$-convex} if there exists an $l$-convex polygonization of $S$.
Considering a typical Erd{\H{o}}s--Szekeres-type problem, we show that every 2-convex point
set of size~$n$ contains an $\Omega(\log n)$-hole.
In comparison, it is well known that there exist arbitrarily
large point sets in general position with no 7-hole.
Further, we show that our bound is tight by constructing 2-convex point sets with holes
of size at most $O(\log n)$.},
originalfile = {/geometry/cggg.bib}
}
@article{abhprvv-hi2cps-18,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and A.~Pilz and P.~Ramos and P.~Valtr and B.~Vogtenhuber},
title = {{{Holes in 2-convex point sets}}},
journal = {Computational Geometry: Theory and Applications},
volume = {74},
pages = {38--49},
year = 2018,
doi = {https://doi.org/10.1016/j.comgeo.2018.06.002},
abstract = {Let $S$ be a set of $n$ points in the plane in general position
(no three points from $S$ are collinear).
For a positive integer $k$, a \emph{$k$-hole} in $S$ is a convex polygon
with $k$ vertices from~$S$ and no points of~$S$ in its interior.
For a positive integer $l$, a simple polygon~$P$ is \emph{$l$-convex}
if no straight line intersects the interior of~$P$ in more than $l$ connected components.
A point set $S$ is \emph{$l$-convex} if there exists an $l$-convex polygonization of $S$.
Considering a typical Erd{\H{o}}s--Szekeres-type problem, we show that every 2-convex point
set of size~$n$ contains an $\Omega(\log n)$-hole.
In comparison, it is well known that there exist arbitrarily
large point sets in general position with no 7-hole.
Further, we show that our bound is tight by constructing 2-convex point sets with holes
of size at most $O(\log n)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahs-plsps-15,
author = {O.~Aichholzer and T.~Hackl and M.~Scheucher},
title = {{{Planar L-Shaped Point Set Embedding of Trees}}},
booktitle = {Proc. $32^{st}$ European Workshop on Computational Geometry EuroCG '16},
pages = {51--54},
year = 2016,
address = {Lugano, Switzerland},
category = {3b},
eprint = {},
pdf = {/files/publications/geometry/ahs-plsps-15.pdf},
thackl_label = {51C},
abstract = {In this paper we consider planar L-shaped embeddings of
trees in point sets, that is, planar drawings where
the vertices are mapped to a subset of the given
points and where every edge consists of two
axis-aligned line segments. We investigate the
minimum number $m$, such that any $n$ vertex tree
with maximum degree 4 admits a planar L-shaped
embedding in any point set of size $m$. First we
give an upper bound $O(n^c)$ with $c=log_23
{\approx} 1.585$ for the general case, and thus
answer the question by Di Giacomo et al. whether
a sub- quadratic upper bound exists. Then we
introduce the saturation function for trees and show
that trees with low saturation can be embedded
even more efficiently. In particular, we improve
the upper bound for caterpillars and extend the
class of trees that require only a linear number of
points. In addition, we present some probabilistic
results for either randomly chosen trees or randomly
chosen point sets.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aahpsv-ilbnt-16,
author = {O.~Aichholzer and V.~Alvarez and T.~Hackl and A.~Pilz and B.~Speckmann and B.~Vogtenhuber},
title = {{{An improved lower bound on the number of triangulations}}},
booktitle = {\em Proc. $32^{nd}$ Int. Sympos. Comput. Geom. (SoCG) volume~51 of
Leibniz International Proceedings in Informatics (LIPIcs)},
pages = {7:1--7:16},
year = 2016,
address = {Boston, USA},
category = {3b},
eprint = {},
doi = {10.4230/LIPIcs.SoCG.2016.7},
pdf = {/files/publications/geometry/aahpsv-ilbnt-16.pdf},
thackl_label = {53C},
abstract = {Upper and lower bounds for the number of geometric
graphs of specific types on a given set of points in
the plane have been intensively studied in recent
years. For most classes of geometric graphs it is
now known that point sets in convex position
minimize their number. However, it is still unclear
which point sets minimize the number of geometric
triangulations; the so-called double circles are
conjectured to be the minimizing sets. In this paper
we prove that any set of $n$ points in general
position in the plane has at least $\Omeag(2.631^n)$
geometric triangulations. Our result improves the
previously best general lower bound of $\Omega(2.43^n)$
and also covers the previously best lower bound of
$\Omega(2.63^n)$ for a fixed number of extreme points. We
achieve our bound by showing and combining several
new results, which are of independent interest: 1.
Adding a point on the second convex layer of a given
point set (of $7$ or more points) at least doubles
the number of triangulations. 2. Generalized
configurations of points that minimize the number of
triangulations have at most ${[}n/2{]}$ points on
their convex hull. 3. We provide tight lower
bounds for the number of triangulations of point
sets with up to 15 points. These bounds further
support the double circle conjecture.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkpsvv-slbnh-17,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and J.~Kyn\v{c}l and
I.~Parada and M.~Scheucher and P.~Valtr and B.~Vogtenhuber},
title = {{{A superlinear lower bound on the number of 5-holes}}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {8:1--8:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
year = 2017,
address = {Brisbane, Australia},
category = {3b},
eprint = {1703.05253},
archiveprefix = {arXiv},
doi = {10.4230/LIPIcs.SoCG.2017.8},
pdf = {/files/publications/geometry/abhkpsvv-slbnh-17.pdf},
abstract = {Let $P$ be a finite set of points in the plane in
\emph{general position}, that is, no three points of
$P$ are on a common line. We say that a set $H$ of
five points from $P$ is a \emph{$5$-hole in~$P$} if
$H$ is the vertex set of a convex $5$-gon containing
no other points of~$P$. For a positive integer $n$,
let $h_5(n)$ be the minimum number of 5-holes among
all sets of $n$ points in the plane in general
position. Despite many efforts in the last 30
years, the best known asymptotic lower and upper
bounds for $h_5(n)$ have been of order $\Omega(n)$
and~$O(n^2)$, respectively. We show that $h_5(n) =
\Omega(n\log^{4/5}{n})$, obtaining the first
superlinear lower bound on $h_5(n)$. The following
structural result, which might be of independent
interest, is a crucial step in the proof of this
lower bound. If a finite set $P$ of points in the
plane in general position is partitioned by a line
$\ell$ into two subsets, each of size at least 5 and
not in convex position, then $\ell$ intersects the
convex hull of some 5-hole in~$P$. The proof of
this result is computer-assisted.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkpsvv-slbnh-17a,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and J.~Kyn\v{c}l and
I.~Parada and M.~Scheucher and P.~Valtr and B.~Vogtenhuber},
title = {{{A superlinear lower bound on the number of 5-holes}}},
booktitle = {Proc. $33^{rd}$ European Workshop on Computational Geometry EuroCG '17},
pages = {69--73},
year = 2017,
address = {Malm\"o, Sweden},
category = {3b},
eprint = {},
pdf = {/files/publications/geometry/abhkpsvv-slbnh-17a.pdf},
abstract = {Let $P$ be a finite set of points in the plane in
\emph{general position}, that is, no three points of
$P$ are on a common line. We say that a set $H$ of
five points from $P$ is a \emph{$5$-hole in~$P$} if
$H$ is the vertex set of a convex $5$-gon containing
no other points of~$P$. For a positive integer $n$,
let $h_5(n)$ be the minimum number of 5-holes among
all sets of $n$ points in the plane in general
position. Despite many efforts in the last 30
years, the best known asymptotic lower and upper
bounds for $h_5(n)$ have been of order $\Omega(n)$
and~$O(n^2)$, respectively. We show that $h_5(n) =
\Omega(n\log^{4/5}{n})$, obtaining the first
superlinear lower bound on $h_5(n)$. The following
structural result, which might be of independent
interest, is a crucial step in the proof of this
lower bound. If a finite set $P$ of points in the
plane in general position is partitioned by a line
$\ell$ into two subsets, each of size at least 5 and
not in convex position, then $\ell$ intersects the
convex hull of some 5-hole in~$P$. The proof of
this result is computer-assisted.},
originalfile = {/geometry/cggg.bib}
}
@article{ahkklpsw-ppstp-17,
author = {O.~Aichholzer and T.~Hackl and M.~Korman and M.~van~Kreveld and
M.~L\"offler and A.~Pilz and B.~Speckmann and E.~Welzl},
title = {{{Packing Plane Spanning Trees and Paths in Complete Geometric Graphs}}},
journal = {Information Processing Letters (IPL)},
volume = {124},
pages = {35--41},
year = 2017,
category = {3a},
arxiv = {1707.05440},
doi = {http://dx.doi.org/10.1016/j.ipl.2017.04.006},
pdf = {/files/publications/geometry/ahkklpsw-ppstp-17.pdf},
abstract = {We consider the following question: How many
edge-disjoint plane spanning trees are contained in a complete
geometric graph $GK_n$ on any set $S$ of $n$ points in general
position in the plane?},
originalfile = {/geometry/cggg.bib}
}
@article{abhpv-ltdbm-17,
author = {Oswin Aichholzer and Luis Barba and Thomas Hackl and Alexander Pilz and Birgit Vogtenhuber},
title = {{{Linear Transformation Distance for Bichromatic
Matchings}}},
journal = {Computational Geometry: Theory and Applications},
year = 2018,
volume = {68},
pages = {77--88},
category = {3a},
doi = {http://dx.doi.org/10.1016/j.comgeo.2017.05.003},
arxiv = {1312.0884v1},
note = {Special Issue in Memory of Ferran Hurtado},
issn = {0925-7721},
url = {http://www.sciencedirect.com/science/article/pii/S0925772117300366},
pdf = {/files/publications/geometry/abhpv-ltdbm-17.pdf},
abstract = {Let $P=B\cup R$ be a set of $2n$ points in general
position, where $B$ is a set of $n$ blue points and
$R$ a set of $n$ red points. A \emph{$BR$-matching}
is a plane geometric perfect matching on $P$ such
that each edge has one red endpoint and one blue
endpoint. Two $BR$-matchings are compatible if their
union is also plane.\\ The \emph{transformation
graph of $BR$-matchings} contains one node for each
$BR$-matching and an edge joining two such nodes if
and only if the corresponding two $BR$-matchings are
compatible. In SoCG 2013 it has been shown by
Aloupis, Barba, Langerman, and Souvaine that this
transformation graph is always connected, but its
diameter remained an open question. In this paper we
provide an alternative proof for the connectivity of
the transformation graph and prove an upper bound of
$2n$ for its diameter, which is asymptotically
tight.},
originalfile = {/geometry/cggg.bib}
}
@article{affhhuv-mimp-17,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and David Flores-Pe{\~n}aloza and Thomas Hackl and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Modem Illumination of Monotone Polygons}}},
journal = {Computational Geometry: Theory and Applications},
year = 2018,
volume = {68},
number = {},
pages = {101--118},
category = {3a},
doi = {https://doi.org/10.1016/j.comgeo.2017.05.010},
arxiv = {1503.05062},
note = {Special Issue in Memory of Ferran Hurtado},
issn = {0925-7721},
url = {http://www.sciencedirect.com/science/article/pii/S0925772117300433},
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.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{adhopvv-estg-19,
author = {Oswin Aichholzer and Jos{\'e} Miguel D\'{\i}az-B{\'a}{\~n}ez and Thomas Hackl and David Orden and Alexander Pilz and Inmaculada Ventura and Birgit Vogtenhuber},
title = {{{Erd{\H{o}}s-Szekeres-Type Games}}},
booktitle = {Proc. {$35^{th}$} European Workshop on Computational Geometry EuroCG '19},
year = 2019,
pages = {23:1-23:7},
address = {Utrecht, The Netherlands},
pdf = {/files/publications/geometry/adhopvv-estg-19.pdf},
url = {http://www.eurocg2019.uu.nl/papers/23.pdf},
abstract = {{We consider several combinatorial games, inspired by the Erd{\H{o}}s-Szekeres theorem that states the
existence of a convex $k$-gon in every sufficiently large point set. Two players take turns to place
points in the Euclidean plane and the game is over as soon as the first $k$-gon appears. In the
Maker-Maker setting the player who placed the last point wins, while in the Avoider-Avoider
version this player loses. Combined versions like Maker-Breaker are also possible. Moreover,
variants can be obtained by considering that (1) the points to be placed are either uncolored or
bichromatic, (2) both players have their own color or can play with both colors, (3) the
$k$-gon must be empty of other points, or (4) the $k$-gon has to be convex.}},
originalfile = {/geometry/cggg.bib}
}
@article{ahkprrrv-ppsgs-19,
author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and Andr{\'e} van Renssen and Marcel Roeloffzen and G\"unter Rote and Birgit Vogtenhuber},
title = {{{Packing plane spanning graphs with short edges in complete geometric graphs}}},
journal = {Computational Geometry},
volume = {782},
pages = {1--15},
year = {2019},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2019.04.001},
url = {http://www.sciencedirect.com/science/article/pii/S0925772119300495},
pdf = {/files/publications/geometry/ahkprrrv-ppsgs-19.pdf},
abstract = {Given a set of points in the plane, we want to establish a connected spanning graph between these points, called connection network, that consists of several disjoint layers. Motivated by sensor networks, our goal is that each layer is connected, spanning, and plane. No edge in this connection network is too long in comparison to the length needed to obtain a spanning tree. We consider two different approaches. First we show an almost optimal centralized approach to extract two layers. Then we consider a distributed model in which each point can compute its adjacencies using only information about vertices at most a predefined distance away. We show a constant factor approximation with respect to the length of the longest edge in the graphs. In both cases the obtained layers are plane.},
originalfile = {/geometry/cggg.bib}
}
@article{abhkpsvv-slbnh-19,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and J.~Kyn\v{c}l and
I.~Parada and M.~Scheucher and P.~Valtr and B.~Vogtenhuber},
title = {{{A superlinear lower bound on the number of 5-holes}}},
journal = {Journal of Combinatorial Theory A},
year = 2019,
pages = {1--31},
note = {online},
eprint = {1703.05253},
doi = {10.1016/j.jcta.2020.105236},
url = {https://doi.org/10.1016/j.jcta.2020.105236},
pdf = {/files/publications/geometry/abhkpsvv-slbnh-17.pdf},
abstract = {Let $P$ be a finite set of points in the plane in
\emph{general position}, that is, no three points of
$P$ are on a common line. We say that a set $H$ of
five points from $P$ is a \emph{$5$-hole in~$P$} if
$H$ is the vertex set of a convex $5$-gon containing
no other points of~$P$. For a positive integer $n$,
let $h_5(n)$ be the minimum number of 5-holes among
all sets of $n$ points in the plane in general
position. Despite many efforts in the last 30
years, the best known asymptotic lower and upper
bounds for $h_5(n)$ have been of order $\Omega(n)$
and~$O(n^2)$, respectively. We show that $h_5(n) =
\Omega(n\log^{4/5}{n})$, obtaining the first
superlinear lower bound on $h_5(n)$. The following
structural result, which might be of independent
interest, is a crucial step in the proof of this
lower bound. If a finite set $P$ of points in the
plane in general position is partitioned by a line
$\ell$ into two subsets, each of size at least 5 and
not in convex position, then $\ell$ intersects the
convex hull of some 5-hole in~$P$. The proof of
this result is computer-assisted.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahlppsv-bdte-22,
author = {Oswin Aichholzer and Thomas Hackl and Maarten L{\"o}ffler and Alexander
Pilz and Irene Parada and Manfred Scheucher and Birgit Vogtenhuber},
title = {{{Blocking Delaunay Triangulations from Exterior}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {9:1--9:7},
year = 2022,
address = {Perugia, Italy},
eprint = {2210.12015},
archiveprefix = {arXiv},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=65},
originalfile = {/geometry/cggg.bib}
}
This file was generated by bibtex2html 1.98.