On the number of pseudo-triangulations of certain point sets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:115

Article

Aichholzer, Oswin¹  Orden, David²  Santos, Francisco³  Speckmann, Bettina⁴ 

[1] Graz Univ Technol, Inst Software Technol, Graz, Austria

[2] Univ Alcala de Henares, Dept Matemat, Alcala De Henares, Spain

[3] Univ Cantabria, Dept Stat & Computat Math, Santander, Spain

[4] Tech Univ Eindhoven, Dept Math & Comp Sci, Eindhoven, Netherlands

关键词: pseudo-triangulations;    triangulations;    double-circle;    double-chain;    counting;   

DOI  :  10.1016/j.jcta.2007.06.002

来源: Elsevier

【 摘 要 】

We pose a monotonicity conjecture on the number of pseudo-triangulations of any planar point set, and check it on two prominent families of point sets, namely the so-called double circle and double chain. The latter has asymptotically 12(n)n(Theta)(1) pointed pseudo-triangulations, which lies significantly above the maximum number of triangulations in a planar point set known so far. (c) 2007 Elsevier Inc. All rights reserved.

【 授权许可】

Free