@article{klmpsv-ddt-17,
title = {{{The dual diameter of triangulations}}},
journal = {Computational Geometry: Theory and Applications},
volume = {68},
pages = {243--252},
year = {2018},
note = {Special Issue in Memory of Ferran Hurtado},
issn = {0925-7721},
doi = {http://dx.doi.org/10.1016/j.comgeo.2017.06.008},
url = {http://www.sciencedirect.com/science/article/pii/S0925772117300603},
author = {Matias Korman and Stefan Langerman and Wolfgang Mulzer and Alexander Pilz and Maria Saumell and Birgit Vogtenhuber},
keywords = {Triangulation},
keywords = {Dual graph},
keywords = {Diameter},
keywords = {Optimization},
keywords = {Simple polygon},
abstract = {{Let $\mathcal{P}$ be a simple polygon with $n$ vertices.
The \emph{dual graph} $T^*$ of a triangulation~$T$ of~$\mathcal{P}$
is the graph whose vertices correspond to the bounded faces of
$T$ and whose edges connect those faces of~$T$ that share an edge.
We consider triangulations of~$\mathcal{P}$ that minimize or maximize the
diameter of their dual graph.
We show that both triangulations can be constructed in $O(n^3\log n)$ time
using dynamic programming.
If $\mathcal{P}$ is convex, we show that any minimizing triangulation has dual
diameter exactly $2\cdot\lceil\log_2(n/3)\rceil$ or
$2\cdot\lceil\log_2(n/3)\rceil -1$, depending on~$n$. Trivially, in this
case any maximizing triangulation has dual diameter $n-2$.
Furthermore, we investigate the relationship between the dual diameter
and the number of \emph{ears} (triangles with exactly two edges incident
to the boundary of $\mathcal{P}$) in a triangulation.
For convex $\mathcal{P}$, we show that there is always a triangulation that
simultaneously minimizes the dual diameter and maximizes the number of
ears.
In contrast, we give examples of general simple polygons where every
triangulation that maximizes the number of ears has dual diameter that
is quadratic in the minimum possible value.
We also consider the case of point sets in general position in the plane.
of~$T$ is defined as before.
We show that for any such set of $n$ points there are triangulations with
dual diameter in~$O(\log n)$ and in~$\Omega(\sqrt n)$.}},
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}
}
@inproceedings{akmpw-oarps-15,
author = {O. Aichholzer and V. Kusters and W. Mulzer and A. Pilz and M. Wettstein},
title = {{{An optimal algorithm for reconstructing point set order types from radial orderings}}},
booktitle = {Proceedings $26^{th}$ Int. Symp. Algorithms and Computation (ISAAC 2015)},
pages = {505--516},
eprint = {1507.08080},
archiveprefix = {arXiv},
year = 2015,
category = {3b},
abstract = {Given a set $P$ of $n$ labeled points in the plane, the radial system of~$P$ describes, for each $p\in P$, the radial order of the other points around~$p$.
This notion is related to the order type of~$P$, which describes the orientation (clockwise or counterclockwise) of every ordered triple of~$P$.
Given only the order type of $P$, it is easy to reconstruct the radial system of $P$, but the converse is not true.
Aichholzer et~al.\ (Reconstructing Point Set Order Types from Radial Orderings, in Proc.~ISAAC 2014) defined $T(R)$ to be the set of order types with radial system~$R$ and showed that sometimes $|T(R)|=n-1$.
They give polynomial-time algorithms to compute $T(R)$ when only given~$R$.
We describe an optimal $O(kn^2)$ time algorithm for computing $T(R)$, where $k$ is the number of order types reported by the algorithm.
The reporting relies on constructing the convex hulls of all possible point sets with the given radial system, after which sidedness queries on point triples can be answered in constant time.
This set of convex hulls can be constructed in linear time.
Our results generalize to abstract order types.},
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{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}
}
@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}
}
@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}
}
@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}
}
@inproceedings{p-acg-12,
author = {Alexander Pilz},
title = {{{Augmentability to Cubic Graphs}}},
booktitle = {Proc. $28^{th}$ European Workshop on Computational Geometry (EuroCG 2012)},
pages = {29--32},
year = {2012},
address = {Assisi, Italy},
month = {March},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{mp-sephe-12,
author = {Tillmann Milzow and Alexander Pilz},
title = {{{Selection of Extreme Points and Halving Edges of a Set by its Chirotope}}},
booktitle = {Proc. $28^{th}$ European Workshop on Computational Geometry (EuroCG 2012)},
pages = {85-88},
year = {2012},
address = {Assisi, Italy},
month = {march},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akpv-got-12,
author = {Oswin Aichholzer and Matias Korman and Alexander Pilz and Birgit Vogtenhuber},
title = {{{Geodesic Order Types}}},
rembooktitle = {Computing nd Combinatorics, Proc. 18$^{th}$ Annual International Computing and Combinatorics Conference},
booktitle = {{Proc. $18^{th}$ International Computing and Combinatorics Conference (COCOON 2012)}},
pages = {216--227},
year = {2012},
address = {Sydney, Australia},
month = {August},
editor = {Joachim Gudmundsson and Juli{\'a}n Mestre and Taso Viglas},
series = {Lecture Notes in Computer Science},
volume = {7434},
publisher = {Springer},
eprint = {1708.06064},
archiveprefix = {arXiv},
doi = {10.1007/978-3-642-32241-9_19},
abstract = {The geodesic between two points $a$ and $b$ in the interior of a simple polygon~$P$ is the shortest polygonal path inside $P$ that connects $a$ to $b$.
It is thus the natural generalization of straight line segments on unconstrained point sets to polygonal environments.
In this paper we use this extension to generalize the concept of the order type of a set of points in the Euclidean plane to geodesic order types.
In particular, we show that, for any set $S$ of points and an ordered subset $\blue \subseteq S$ of at least four points, one can always construct a polygon $P$ such that the points of $\blue$ define the geodesic hull of~$S$ w.r.t.~$P$, in the specified order.
Moreover, we show that an abstract order type derived from the dual of the Pappus arrangement can be realized as a geodesic order type.},
originalfile = {/geometry/cggg.bib}
}
@article{amp-ephes-13,
author = {Oswin Aichholzer and
Tillmann Miltzow and
Alexander Pilz},
title = {{{Extreme point and halving edge search in abstract order
types}}},
journal = {Comput. Geom.},
volume = {46},
number = {8},
year = {2013},
pages = {970--978},
doi = {http://dx.doi.org/10.1016/j.comgeo.2013.05.001},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set.
However, many fundamental algorithms in computational geometry rely on coordinate representations.
This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time.
In his monograph \emph{Axioms and Hulls}, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set's chirotope, as a source of information.
We answer this question in the affirmative.
More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time.
We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.},
originalfile = {/geometry/cggg.bib}
}
@article{p-pdtpp-14,
author = {Alexander Pilz},
title = {{{Flip Distance Between Triangulations of a Planar Point Set is {APX}-Hard}}},
journal = {Comput. Geom.},
doi = {http://dx.doi.org/10.1016/j.comgeo.2014.01.001},
year = 2014,
pages = {589--604},
volume = {47},
number = {5},
eprint = {1206.3179},
archiveprefix = {arXiv},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{amp-fdtsp-13b,
author = {Oswin Aichholzer and
Wolfgang Mulzer and
Alexander Pilz},
title = {{{Flip Distance between Triangulations of a Simple Polygon
is {NP}-Complete}}},
booktitle = {Proc. $21^{st}$ European Symposium on Algorithms (ESA 2013)},
year = {2013},
pages = {13--24},
doi = {http://dx.doi.org/10.1007/978-3-642-40450-4_2},
crossref = {DBLP:conf/esa/2013},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {Let $T$ be a triangulation of a simple polygon.
A \emph{flip} in~$T$ is the operation of replacing one diagonal of~$T$
by a different one such that the resulting graph is again
a triangulation. The \emph{flip distance} between two triangulations is the smallest
number of flips required to transform one triangulation into the
other. For the special case of convex polygons, the problem of determining
the shortest flip distance between two triangulations is equivalent
to determining the rotation distance between two binary trees,
a central problem which is still open after over 25 years of intensive study.
We show that computing the flip distance between two
triangulations of a simple polygon is NP-hard. This complements a recent
result that shows APX-hardness of determining the flip distance between two
triangulations of a planar point set.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{amp-fdtsp-13a,
author = {Oswin Aichholzer and
Wolfgang Mulzer and
Alexander Pilz},
title = {{{Flip Distance between Triangulations of a Simple Polygon
is {NP}-Complete}}},
booktitle = {Proc. $29^{th}$ European Workshop on Computational Geometry (EuroCG 2013)},
year = {2013},
pages = {115--118},
address = {Braunschweig, Germany},
abstract = {Let $T$ be a triangulation of a simple polygon.
A \emph{flip} in~$T$ is the operation of replacing one diagonal of~$T$
by a different one such that the resulting graph is again
a triangulation. The \emph{flip distance} between two triangulations is the smallest
number of flips required to transform one triangulation into the
other. For the special case of convex polygons, the problem of determining
the shortest flip distance between two triangulations is equivalent
to determining the rotation distance between two binary trees,
a central problem which is still open after over 25 years of intensive study.
We show that computing the flip distance between two
triangulations of a simple polygon is NP-hard. This complements a recent
result that shows APX-hardness of determining the flip distance between two
triangulations of a planar point set.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{dkppss-nrssp-13,
author = {Jos{\'e} Miguel D\'{\i}az-B{\'a}{\~n}ez and
Matias Korman and
Pablo P{\'e}rez-Lantero and
Alexander Pilz and
Carlos Seara and
Rodrigo I. Silveira},
title = {{{New Results on Stabbing Segments with a Polygon}}},
booktitle = {Proc. $8^{th}$ International Conference on Algorithms and Complexity (CIAC 2013)},
year = {2013},
pages = {146--157},
doi = {http://dx.doi.org/10.1007/978-3-642-38233-8_13},
crossref = {DBLP:conf/ciac/2013},
bibsource = {DBLP, http://dblp.uni-trier.de},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{klmpv-mddt-14,
author = {Matias Korman and Stefan Langerman and Wolfgang Mulzer and Alexander Pilz and Maria Saumell and Birgit Vogtenhuber},
title = {{{Minimum Dual Diameter Triangulations}}},
booktitle = {Proc. $30^{th}$ European Workshop on Computational Geometry (EuroCG 2014)},
year = {2014},
month = {March},
pages = {online},
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}
}
@article{dkppsr-nrsswp-15,
author = {D\'iaz-B\'a\~nez, Jos\'e Miguel and Korman, Matias and
P\'erez-Lantero, Pablo and Pilz, Alexander and
Seara, Carlos and Silveira, Rodrigo I.},
title = {{{New results on stabbing segments with a polygon}}},
journal = {Comput. Geom.},
volume = {48},
number = {1},
pages = {14--29},
year = {2015},
doi = {http://dx.doi.org/10.1016/j.comgeo.2014.06.002},
url = {http://www.sciencedirect.com/science/article/pii/S0925772114000686},
eprint = {1211.1490v3},
abstract = {We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s is stabbed by a simple polygon P if at least one endpoint of s is contained in P, and a segment set S is stabbed by P if P stabs every element of S. Given a segment set S, we study the problem of finding a simple polygon P stabbing S in a way that some measure of P (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by L\"offler and van Kreveld [Algorithmica 56(2), 236--269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard.},
originalfile = {/geometry/cggg.bib}
}
@article{akpv-got-14,
author = {Oswin Aichholzer and Matias Korman and Alexander Pilz and Birgit Vogtenhuber},
title = {{{Geodesic Order Types}}},
journal = {Algorithmica},
volume = {70},
number = {1},
year = {2014},
pages = {112--128},
doi = {http://dx.doi.org/10.1007/s00453-013-9818-8},
eprint = {1708.06064},
archiveprefix = {arXiv},
archiveprefix = {arXiv},
url = {http://link.springer.com/article/10.1007\%2Fs00453-013-9818-8},
pdf = {/files/publications/geometry/akpv-got-14.pdf},
abstract = {The geodesic between two points a and b in the interior of a simple polygon P is the shortest polygonal path inside P that connects a to b. It is thus the natural generalization of straight line segments on unconstrained point sets to polygonal environments. In this paper we use this extension to generalize the concept of the order type of a set of points in the Euclidean plane to geodesic order types. In particular, we show that, for any set S of points and an ordered subset B ⊆ S of at least four points, one can always construct a polygon P such that the points of B define the geodesic hull of S w.r.t. P, in the specified order. Moreover, we show that an abstract order type derived from the dual of the Pappus arrangement can be realized as a geodesic order type.},
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{fp-hscao-14,
author = {Stefan Felsner and
Alexander Pilz},
title = {{{Ham-Sandwich Cuts for Abstract Order Types}}},
booktitle = {Algorithms and Computation - 25th International Symposium, {ISAAC}
2014, Jeonju, Korea, December 15-17, 2014, Proceedings},
pages = {726--737},
year = {2014},
crossref = {DBLP:conf/isaac/2014},
url = {http://dx.doi.org/10.1007/978-3-319-13075-0_57},
doi = {10.1007/978-3-319-13075-0_57},
timestamp = {Mon, 10 Nov 2014 13:24:45 +0100},
biburl = {http://dblp.uni-trier.de/rec/bib/conf/isaac/FelsnerP14},
bibsource = {dblp computer science bibliography, http://dblp.org},
originalfile = {/geometry/cggg.bib}
}
@article{amp-fdtsp-15,
author = {Oswin Aichholzer and
Wolfgang Mulzer and
Alexander Pilz},
title = {{{Flip Distance Between Triangulations of a Simple Polygon is {NP}-Complete}}},
journal = {Discrete Comput. Geom.},
volume = {54},
number = {2},
pages = {368--389},
year = {2015},
url = {http://dx.doi.org/10.1007/s00454-015-9709-7},
doi = {10.1007/s00454-015-9709-7},
timestamp = {Thu, 23 Jul 2015 10:18:03 +0200},
biburl = {http://dblp.uni-trier.de/rec/bib/journals/dcg/AichholzerMP15},
bibsource = {dblp computer science bibliography, http://dblp.org},
abstract = {Let $T$ be a triangulation of a simple polygon.
A \emph{flip} in~$T$ is the operation of replacing one diagonal of~$T$
by a different one such that the resulting graph is again
a triangulation. The \emph{flip distance} between two triangulations is
the smallest number of flips required to transform one triangulation into the
other. For the special case of convex polygons, the problem of determining the
shortest flip distance between two triangulations is equivalent to determining
the rotation distance between two binary trees, a central problem which is still
open after over 25 years of intensive study.
We show that computing the flip distance between two
triangulations of a simple polygon is NP-hard. This complements a recent
result that shows APX-hardness of determining the flip distance between two
triangulations of a planar point set.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{pw-oo-15,
author = {Alexander Pilz and
Emo Welzl},
title = {{{Order on Order Types}}},
booktitle = {Proc. 31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {285--299},
year = {2015},
crossref = {DBLP:conf/compgeom/2015},
url = {http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.285},
doi = {10.4230/LIPIcs.SOCG.2015.285},
timestamp = {Mon, 15 Jun 2015 17:02:26 +0200},
biburl = {http://dblp.uni-trier.de/rec/bib/conf/compgeom/PilzW15},
bibsource = {dblp computer science bibliography, http://dblp.org},
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{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}
}
@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{affmpps-mmvqt-17,
title = {{{Minimization and Maximization Versions of the Quadratic Traveling Salesman Problem}}},
author = {O.~Aichholzer and A.~Fischer and F.~Fischer J.F.~Meier and U.~Pferschy and A.~Pilz and R.~Stanek},
journal = {OPTIMIZATION},
doi = {http://dx.doi.org/10.1080/02331934.2016.1276905},
volume = {66},
number = {4},
pages = {521--546},
year = {2017},
publisher = {TAYLOR \& FRANCIS LTD 2-4 PARK SQUARE, MILTON PARK, ABINGDON OR14 4RN, OXON, ENGLAND},
pdf = {/files/publications/geometry/affmpps-mmvqt-17.pdf},
abstract = {The traveling salesman problem (TSP) asks for a shortest
tour through all vertices of a graph with respect to
the weights of the edges. The symmetric quadratic
traveling salesman problem (SQTSP) associates a
weight with every three vertices traversed in
succession. If these weights correspond to the
turning angles of the tour, we speak of the
angular-metric traveling salesman problem (Angle
TSP). In this paper, we first consider the SQTSP
from a computational point of view. In particular,
we apply a rather basic algorithmic idea and perform
the separation of the classical subtour elimination
constraints on integral solutions
only. Surprisingly, it turns out that this approach
is faster than the standard fractional separation
procedure known from the literature. We also test
the combination with strengthened subtour
elimination constraints for both variants, but these
turn out to slow down the computation. Secondly, we
provide a completely different, mathematically
interesting MILP linearization for the Angle TSP
that needs only a linear number of additional
variables while the standard linearization requires
a cubic one. For medium sized instances of a variant
of the Angle TSP this formulation yields reduced
running times. However, for larger instances or pure
Angle TSP instances the new formulation takes more
time to solve than the known standard model.
Finally, we introduce MaxSQTSP, the maximization
version of the quadratic traveling salesman
problem. Here it turns out that using some of the
stronger subtour elimination constraints helps. For
the special case of the MaxAngle TSP we can observe
an interesting geometric property if the number of
vertices is odd. We show that the sum of inner
turning angles in an optimal solution always equals
$\pi$. This implies that the problem can be solved
by the standard ILP model without producing any
integral subtours. Moreover, we give a simple
constructive polynomial time algorithm to find such
an optimal solution. If the number of vertices is
even the optimal value lies between 0 and $2\pi$ and
these two bounds are tight, which can be shown by an
analytic solution for a regular $n$-gon.},
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}
}
@inproceedings{abhkmppsvvw-mggrot-18,
author = {Oswin Aichholzer and
Martin Balko and
Michael Hoffmann and
Jan Kyn\v{c}l and
Wolfgang Mulzer and
Irene Parada and
Alexander Pilz and
Manfred Scheucher and
Pavel Valtr and
Birgit Vogtenhuber and
Emo Welzl},
title = {{{Minimal Geometric Graph Representations of Order Types}}},
booktitle = {Proc. {$34^{th}$} European Workshop on Computational Geometry EuroCG '18},
year = 2018,
pages = {21:1--21:6},
address = {Berlin, Germany},
abstract = {We consider the problem of characterizing small geometric graphs
whose structure uniquely determines the order type of its vertex set.
We describe a set of edges that prevent the order type from changing
by continuous movement and identify properties of the resulting graphs.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aepv-assdcg-17,
author = {Oswin Aichholzer and
Florian Ebenf\"{u}hrer and
Irene Parada and
Alexander Pilz and
Birgit Vogtenhuber},
title = {{{On semi-simple drawings of the complete graph}}},
booktitle = {Proc. XVII Encuentros de Geometr\'{\i}a Computacional},
pages = {25--28},
year = 2017,
address = {Alicante, Spain},
pdf = {/files/publications/geometry/aepv-assdcg-17.pdf},
abstract = {In this work we study rotation systems and semi-simple drawings of $K_n$. A simple drawing of a graph is a drawing in which every pair of edges intersects in at most one point. In a semi-simple drawing, edge pairs might intersect in multiple points, but incident edges only intersect in their common endpoint. A rotation system is called (semi-)realizable if it can be realized with a (semi-)simple drawing. It is known that a rotation system is realizable if and only if all its 5-tuples are realizable. For the problem of characterizing semi-realizability, we present a rotation system with six vertices that is not semi-realizable, although all its 5-tuples are semi-realizable. Moreover, by an exhaustive computer search, we show that also for seven vertices there exist minimal not semi-realizable rotation systems (that is, rotation systems in which all proper sub-rotation systems are semi-realizable). This indicates that checking semi-realizability is harder than checking realizability. Finally we show that for semi-simple drawings, generalizations of Conway's Thrackle Conjecture and the conjecture on the existence of plane Hamiltonian cycles do not hold.},
originalfile = {/geometry/cggg.bib}
}
@article{akmpw-oarps-17,
author = {O. Aichholzer and V. Kusters and W. Mulzer and A. Pilz and M. Wettstein},
title = {{{An optimal algorithm for reconstructing point set order types from radial orderings}}},
journal = {International Journal of Computational Geometry \& Applications},
year = 2017,
volume = {27},
number = {1--2},
pages = {57--83},
doi = {10.1142/S0218195917600044},
url = {http://www.scopus.com/inward/record.url?scp=85029349312&partnerID=8YFLogxK},
eprint = {1507.08080},
abstract = {Let $P$ be a set of $n$ labeled points in the plane.
The \emph{radial system} of~$P$ describes, for each
$p\in P$, the order in which a ray that rotates
around $p$ encounters the points in $P \setminus \{p\}$.
This notion is related to the \emph{order type}
of~$P$, which describes the orientation (clockwise
or counterclockwise) of every ordered triple in~$P$.
Given only the order type, the radial
system is uniquely determined and can
easily be obtained. The converse, however,
is not true. Indeed, let $R$ be the radial system
of $P$, and let $T(R)$ be the set of all order
types with radial system $R$
(we define $T(R) = \emptyset$ for the
case that $R$ is not a valid radial system).
Aichholzer \etal~(\emph{Reconstructing
Point Set Order Types from Radial Orderings}, in
Proc.~ISAAC 2014) show that
$T(R)$ may contain up to $n-1$ order types.
They also provide polynomial-time algorithms to
compute $T(R)$ when only $R$ is given.
We describe a new algorithm for
finding $T(R)$. The algorithm constructs the convex
hulls of all possible point sets with the radial
system $R$. After that, orientation queries on point triples
can be answered in constant time. A representation of this set of convex
hulls can be found in $O(n)$ queries to the radial system,
using $O(n)$ additional processing time. This is optimal.
Our results also generalize
to \emph{abstract order types}.},
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}
}
@inproceedings{aappttuv-hmpcb-19,
author = {Oswin Aichholzer and Carlos Alegr\'{i}a Galicia and Irene Parada and Alexander Pilz and Javier Tejel and Csaba D. T\'{o}th and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Hamiltonian meander paths and cycles on bichromatic point sets}}},
booktitle = {Proc. XVIII Encuentros de Geometr\'{\i}a Computacional},
pages = {35--38},
year = 2019,
address = {Girona, Spain},
pdf = {/files/publications/geometry/aappttuv-hmpcb-19.pdf},
url = {http://imae.udg.edu/egc2019/doc/BookAbstractsEGC2019.pdf},
abstract = {We show that any set of $n$ blue and $n$ red points on a
line admits a plane meander path, that is, a crossing-free
panning path that passes across the line on red
and blue points in alternation. For meander cycles,
we derive tight bounds on the minimum number of
necessary crossings which depend on the coloring of
the points. Finally, we provide some relations for the
number of plane meander paths.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aappttuv-hmpcb2-19,
author = {Oswin Aichholzer and Carlos Alegr\'{i}a Galicia and Irene Parada and Alexander Pilz and Javier Tejel and Csaba D. T\'{o}th and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Hamiltonian meander paths and cycles on bichromatic point sets}}},
booktitle = {EasyChair Preprint no. 3130},
year = 2019,
url = {https://easychair.org/publications/preprint/N7TX},
abstract = {We show that any set of $n$ blue and $n$ red points on a
line admits a plane meander path, that is, a crossing-free
panning path that passes across the line on red
and blue points in alternation. For meander cycles,
we derive tight bounds on the minimum number of
necessary crossings which depend on the coloring of
the points. Finally, we provide some relations for the
number of plane meander paths.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkmppsvvw-mrotg-19,
author = {Oswin Aichholzer and Martin Balko and Michael Hoffmann and Jan Kyn\v{c}l and Wolfgang Mulzer and Irene Parada and Alexander Pilz and Manfred Scheucher and Pavel Valtr and Birgit Vogtenhuber and Emo Welzl},
title = {{{Minimal representations of order types by geometric graphs}}},
booktitle = {Graph Drawing and Network Visualization. GD 2019},
nonote = {27th International Symposium on Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11904},
pages = {101--113},
address = {Prague, Czechia},
year = 2019,
eprint = {1908.05124},
doi = {https://doi.org/10.1007/978-3-030-35802-0_8},
abstract = {In order to have a compact visualization of the order type of
a given point set $S$,
we are interested in geometric graphs on $S$ with few edges that unequivocally display %
the order type of $S$.
We introduce the concept of \emph{exit edges},
which prevent the order type from changing under continuous motion of vertices.
Exit edges have a natural dual characterization,
which allows us to efficiently compute them and to bound their number.},
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{abhkmppsvvw-mrotg-20,
author = {Oswin Aichholzer and Martin Balko and Michael Hoffmann and Jan Kyn\v{c}l and Wolfgang Mulzer and Irene Parada and Alexander Pilz and Manfred Scheucher and Pavel Valtr and Birgit Vogtenhuber and Emo Welzl},
title = {{{{{Minimal representations of order types by geometric graphs}}}}},
journal = {Journal of Graph Algorithms and Applications},
volume = {24},
number = {4},
pages = {551--572},
doi = {10.7155/jgaa.00545},
note = {special issue of the 27th International Symposium on Graph Drawing and Network Visualization GD$\,$2019},
year = {2020},
abstract = {In order to have a compact visualization of the order type of
a given point set $S$,
we are interested in geometric graphs on $S$ with few edges that unequivocally display
the order type of $S$.
We introduce the concept of \emph{exit edges},
which prevent the order type from changing under continuous motion of vertices.
Exit edges have a natural dual characterization,
which allows us to efficiently compute them and to bound their number.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aamppptv-cm2021,
author = {Oswin Aichholzer and Alan Arroyo and Zuzana Mas\'{a}rov\'{a} and Irene Parada and Daniel Perz and Alexander Pilz and Josef Tkadlec and Birgit Vogtenhuber},
title = {{{On Compatible Matchings}}},
booktitle = {WALCOM: Algorithms and Computation},
year = {2021},
publisher = {Springer International Publishing},
adress = {Cham},
pages = {221--233},
editor = {Ryuhei Uehara and Seok-Hee Hong and Subhas C. Nandy},
eprint = {2101.03928},
doi = {10.1007/978-3-030-68211-8_18},
note = {Best Paper Award},
isbn = {978-3-030-68211-8},
abstract = {A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $\lfloor \sqrt {2n}\rfloor$ edges. More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $\Omega(n^{1/\ell})$. As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has $\mathcal{O}(n^{2/(\ell+1)})$ edges. Finally, we show that $\Theta(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
originalfile = {/geometry/cggg.bib}
}
@article{aamppptv-cm2022,
author = {{Oswin} {Aichholzer} and {Alan} {Arroyo} and {Zuzana} {Mas\'{a}rov\'{a}} and {Irene} {Parada} and {Daniel} {Perz} and {Alexander} {Pilz} and {Josef} {Tkadlec} and {Birgit} {Vogtenhuber}},
title = {{{On Compatible Matchings}}},
journal = {Journal of Graph Algorithms and Applications},
year = {2022},
volume = {26},
number = {2},
pages = {225--240},
doi = {10.7155/jgaa.00591},
abstract = {A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $\lfloor \sqrt {2n}\rfloor$ edges. More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $\Omega(n^{1/\ell})$. As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has $\mathcal{O}(n^{2/(\ell+1)})$ edges. Finally, we show that $\Theta(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
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.