A lower bound on the number of triangulations of planar point sets

被引：31
|
作者：
Aichholzer, O
Hurtado, F
Noy, M
机构：
[1] Graz Univ Technol, Inst Software Technol, A-8010 Graz, Austria
[2] Univ Politecn Catalunya, Dept Matemat Aplicada 2, E-08028 Barcelona, Spain
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2004年 / 29卷 / 02期
关键词：
straight-edge triangulations; counting; lower bound;
D O I：
10.1016/j.comgeo.2004.02.003
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We show that the number of straight-edge triangulations exhibited by any set of n points in general position in the plane is bounded from below by Omega (2.33(n)). (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：135 / 145
页数：11
相关论文
共 50 条
  • [1] Counting Triangulations of Planar Point Sets
    Sharir, Micha
    Sheffer, Adam
    ELECTRONIC JOURNAL OF COMBINATORICS, 2011, 18 (01):
  • [2] On the number of pseudo-triangulations of certain point sets
    Aichholzer, Oswin
    Orden, David
    Santos, Francisco
    Speckmann, Bettina
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2008, 115 (02) : 254 - 278
  • [3] A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems
    Alvarez, Victor
    Seidel, Raimund
    PROCEEDINGS OF THE TWENTY-NINETH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SOCG'13), 2013, : 1 - 8
  • [4] On Degrees in Random Triangulations of Point Sets
    Sharir, Micha
    Sheffer, Adam
    Welzl, Emo
    PROCEEDINGS OF THE TWENTY-SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'10), 2010, : 297 - 306
  • [5] A lower bound for β-skeleton belonging to minimum weight triangulations
    Wang, CA
    Yang, BT
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2001, 19 (01): : 35 - 46
  • [6] Chains, Koch Chains, and Point Sets with Many Triangulations
    Rutschmann, Daniel
    Wettstein, Manuel
    JOURNAL OF THE ACM, 2023, 70 (03)
  • [7] A lower bound for the nodal sets of Steklov eigenfunctions
    Wang, Xing
    Zhu, Jiuyi
    MATHEMATICAL RESEARCH LETTERS, 2015, 22 (04) : 1243 - 1253
  • [8] Optimal estimation for lower bound of the packing number
    Liu, Youming
    Qi, Xinyu
    STATISTICS & PROBABILITY LETTERS, 2022, 186
  • [9] A lower bound on the chromatic number of Mycielski graphs
    Caramia, M
    Dell'Olmo, P
    DISCRETE MATHEMATICS, 2001, 235 (1-3) : 79 - 86
  • [10] A lower bound for the number of reidemeister moves for unknotting
    Hayashi, C
    JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS, 2006, 15 (03) : 313 - 325
12345