Search Results

Documents authored by Hackl, Thomas

Document
DOI: 10.4230/LIPIcs.SoCG.2017.8
A Superlinear Lower Bound on the Number of 5-Holes

Authors: Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Let P be a finite set of points in the plane in 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 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 n)^(4/5)), 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 l into two subsets, each of size at least 5 and not in convex position, then l intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.
Cite as

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber. A Superlinear Lower Bound on the Number of 5-Holes. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2017.8,
  author =	{Aichholzer, Oswin and Balko, Martin and Hackl, Thomas and Kyncl, Jan and Parada, Irene and Scheucher, Manfred and Valtr, Pavel and Vogtenhuber, Birgit},
  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)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.8},
  URN =		{urn:nbn:de:0030-drops-72008},
  doi =		{10.4230/LIPIcs.SoCG.2017.8},
  annote =	{Keywords: Erd\"{o}s-Szekeres type problem, k-hole, empty k-gon, empty pentagon, planar point set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.9
Packing Short Plane Spanning Trees in Complete Geometric Graphs

Authors: Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

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 trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.
Cite as

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber. Packing Short Plane Spanning Trees in Complete Geometric Graphs. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.ISAAC.2016.9,
  author =	{Aichholzer, Oswin and Hackl, Thomas and Korman, Matias and Pilz, Alexander and Rote, G\"{u}nter and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Vogtenhuber, Birgit},
  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 =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.9},
  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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.7
An Improved Lower Bound on the Minimum Number of Triangulations

Authors: Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

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 Omega(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.
Cite as

Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. An Improved Lower Bound on the Minimum Number of Triangulations. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2016.7,
  author =	{Aichholzer, Oswin and Alvarez, Victor and Hackl, Thomas and Pilz, Alexander and Speckmann, Bettina and Vogtenhuber, Birgit},
  title =	{{An Improved Lower Bound on the Minimum Number of Triangulations}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.7},
  URN =		{urn:nbn:de:0030-drops-58993},
  doi =		{10.4230/LIPIcs.SoCG.2016.7},
  annote =	{Keywords: Combinatorial geometry, Order types, Triangulations}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact