@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{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}
}
@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{aaabbcilsty-sseps-13,
author = {O. Aichholzer and S.R. Allen and G. Aloupis and L. Barba
and P. Bose and J.-L. De Carufel and J. Iacono and S.
Langerman and D.L. Souvaine and P. Taslakin and M.
Yagnatinsky},
title = {{{Sum of Squared Edges for MST of a Point Set in a Unit
Square}}},
booktitle = {Proc. of the $16^{th}$ Japan Conference on Discrete and
Computational Geometry and Graphs (JCDCG$^2$ 2013)},
year = 2013,
address = {Tokyo, Japan},
category = {3b},
abstract = {Given a set P of points in the unit square let w(P) be the
minimum sum of the squares of the edge lengths in the
minimum spanning tree of P. We show that w(P) < 3.411.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaabbli-ssemp-12,
author = {O. Aichholzer and S.R. Allen and G. Aloupis and L. Barba
and P. Bose and S. Langerman and J. Iacono},
title = {{{Sum of Squared Edges for MST of a Point Set in a Unit
Square}}},
booktitle = {Proc. $22^{nd}$ Annual Fall Workshop on Computational
Geometry},
year = 2012,
address = {University of Maryland, Maryland, USA},
category = {3b},
htmlnote = {For
proceedings see here.},
abstract = {Given a set P of points in the unit square let w(P) be the
minimum sum of the squares of the edge lengths in the
minimum spanning tree of P. We show that w(P) < 3.411.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{acklv-rpsot-14,
author = {Oswin Aichholzer and
Jean Cardinal and
Vincent Kusters and
Stefan Langerman and
Pavel Valtr},
title = {{{Reconstructing Point Set Order Types from Radial Orderings}}},
booktitle = {Algorithms and Computation - 25th International Symposium, {ISAAC}
2014, Jeonju, Korea, December 15-17, 2014, Proceedings},
pages = {15--26},
year = {2014},
crossref = {DBLP:conf/isaac/2014},
doi = {10.1007/978-3-319-13075-0_2},
timestamp = {Mon, 10 Nov 2014 13:24:45 +0100},
biburl = {http://dblp.uni-trier.de/rec/bib/conf/isaac/AichholzerCKLV14},
bibsource = {dblp computer science bibliography, http://dblp.org},
pdf = {/files/publications/geometry/acklv-rpsot.pdf},
abstract = {We consider the problem of reconstructing the combinatorial structure of a
set of $n$ points in the plane given partial information on the relative
position of the points. This partial information consists of the radial
ordering, for each of the $n$ points, of the $n-1$ other points around it. We
show that this information is sufficient to reconstruct the chirotope, or
labeled order type, of the point set, provided its convex hull has size at
least four. Otherwise, we show that there can be as many as $n-1$ distinct
chirotopes that are compatible with the partial information, and this bound
is tight. Our proofs yield polynomial-time reconstruction algorithms. These
results provide additional theoretical insights on previously studied
problems related to robot navigation and visibility-based reconstruction.},
originalfile = {/geometry/cggg.bib}
}
@article{acklv-rpsot-16,
author = {Oswin Aichholzer and
Jean Cardinal and
Vincent Kusters and
Stefan Langerman and
Pavel Valtr},
title = {{{Reconstructing Point Set Order Types from Radial Orderings}}},
journal = {International Journal of Computational Geometry \& Applications},
year = 2016,
volume = {26},
number = {3/4},
pages = {167--184},
category = {3a},
doi = {10.1142/S0218195916600037},
pdf = {/files/publications/geometry/acklv-rpsot.pdf},
abstract = {We consider the problem of reconstructing the combinatorial structure of a
set of $n$ points in the plane given partial information on the relative
position of the points. This partial information consists of the radial
ordering, for each of the $n$ points, of the $n-1$ other points around it. We
show that this information is sufficient to reconstruct the chirotope, or
labeled order type, of the point set, provided its convex hull has size at
least four. Otherwise, we show that there can be as many as $n-1$ distinct
chirotopes that are compatible with the partial information, and this bound
is tight. Our proofs yield polynomial-time reconstruction algorithms. These
results provide additional theoretical insights on previously studied
problems related to robot navigation and visibility-based reconstruction.},
originalfile = {/geometry/cggg.bib}
}
This file was generated by bibtex2html 1.98.