License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.7
URN: urn:nbn:de:0030-drops-58993
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5899/
Go to the corresponding LIPIcs Volume Portal

Aichholzer, Oswin ; Alvarez, Victor ; Hackl, Thomas ; Pilz, Alexander ; Speckmann, Bettina ; Vogtenhuber, Birgit

An Improved Lower Bound on the Minimum Number of Triangulations

pdf-format:
LIPIcs-SoCG-2016-7.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{aichholzer_et_al:LIPIcs:2016:5899,
  author =	{Oswin Aichholzer and Victor Alvarez and Thomas Hackl and Alexander Pilz and Bettina Speckmann and Birgit Vogtenhuber},
  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 =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5899},
  URN =		{urn:nbn:de:0030-drops-58993},
  doi =		{10.4230/LIPIcs.SoCG.2016.7},
  annote =	{Keywords: Combinatorial geometry, Order types, Triangulations}
}

Keywords: Combinatorial geometry, Order types, Triangulations
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI