On the number of pseudo-triangulations of certain point sets

被引：10

作者：

Aichholzer, Oswin ^{[1
]}

Orden, David ^{[2
]}

Santos, Francisco ^{[3
]}

Speckmann, Bettina ^{[4
]}

机构：

[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

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2008年 / 115卷 / 02期

基金：

奥地利科学基金会;

关键词：

pseudo-triangulations; triangulations; double-circle; double-chain; counting;

D O I：

10.1016/j.jcta.2007.06.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：254 / 278

页数：25

共 31 条

[1] Deformable free-space tilings for kinetic collision detection
Agarwal, PK
Basch, J
Guibas, LJ
Hershberger, J
Zhang, L
[J]. INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 2002, 21 (03) : 179 - 197
[2] Convexity minimizes pseudo-triangulations
Aichholzer, O
Aurenhammer, F
Krasser, H
Speckmann, B
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 28 (01): : 3 - 10
[3] A lower bound on the number of triangulations of planar point sets
Aichholzer, O
Hurtado, F
Noy, M
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 29 (02): : 135 - 145
[4] Pseudotriangulations from surfaces and a novel type of edge flip
Aichholzer, O
Aurenhammer, F
Krasser, H
Brass, P
[J]. SIAM JOURNAL ON COMPUTING, 2003, 32 (06) : 1621 - 1653
[5] Aichholzer O, 2003, LECT NOTES COMPUT SC, V2748, P12
[6] AICHHOLZER O, 2001, P 13 CAN C COMP GEOM, P17
[7] On the Number of Plane Graphs
Aichholzer, Oswin
Hackl, Thomas
Vogtenhuber, Birgit
Huemer, Clemens
Hurtado, Ferran
Krasser, Hannes
[J]. PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 504 - +
[8] [Anonymous], P 13 CAN C COMP GEOM
[9] RAY SHOOTING IN POLYGONS USING GEODESIC TRIANGULATIONS
CHAZELLE, B
EDELSBRUNNER, H
GRIGNI, M
GUIBAS, L
HERSHBERGER, J
SHARIR, M
SNOEYINK, J
[J]. ALGORITHMICA, 1994, 12 (01) : 54 - 68
[10] Enumerating a class of lattice paths
Coker, C
[J]. DISCRETE MATHEMATICS, 2003, 271 (1-3) : 13 - 28

← 1 2 3 4 →