Monotone Paths in Geometric Triangulations

被引：0

作者：

Dumitrescu, Adrian ^{[1
]}

Mandal, Ritankar ^{[1
]}

Toth, Csaba D. ^{[2
,3
]}

机构：

[1] Univ Wisconsin, Dept Comp Sci, Milwaukee, WI 53706 USA

[2] Calif State Univ Northridge, Dept Math, Los Angeles, CA USA

[3] Tufts Univ, Dept Comp Sci, Medford, MA 02155 USA

来源：

THEORY OF COMPUTING SYSTEMS | 2018年 / 62卷 / 06期

基金：

美国国家科学基金会;

关键词：

Monotone path; Triangulation; Counting algorithm; SIMPLEX-ALGORITHM; HIRSCH CONJECTURE; RANDOM-EDGE; GRAPHS; DIAMETER; BOUNDS; MATCHINGS; POLYHEDRA; CYCLES;

D O I：

10.1007/s00224-018-9855-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

(I) We prove that the (maximum) number of monotone paths in a geometric triangulation of n points in the plane is O(1.7864 (n) ). This improves an earlier upper bound of O(1.8393 (n) ); the current best lower bound is Omega(1.7003 (n) ). (II) Given a planar geometric graph G with n vertices, we show that the number of monotone paths in G can be computed in O(n (2)) time.

引用

页码：1490 / 1524

页数：35

共 29 条

[1]

Adler I., 2014, LNCS, V8494

[2]

Ajtai M., 1982, THEORY PRACTICE COMB, P9, DOI [10.1016/S0304-0208(08), DOI 10.1016/S0304-0208(08), DOI 10.1016/S0304-0208(08)73484-4]

[3]

Buchin K., 2007, LNCS, V4598

[4]

De Berg M., 2008, Computational Geometry: Algorithms and Applications, V17

[5]

Dumitrescu Adrian, 2012, SIGACT News, V43, P90

[6]

Dumitrescu A., 2013, DISCRETE GEOMETRY OP, V69 of, P79

[7] Convex Polygons in Geometric Triangulations [J].

Dumitrescu, Adrian ;

Toth, Csaba D. .

COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (05) :641-659

[8] Counting Carambolas [J].

Dumitrescu, Adrian ;

Loffler, Maarten ;

Schulz, Andre ;

Toth, Csaba D. .

GRAPHS AND COMBINATORICS, 2016, 32 (03) :923-942

[9] BOUNDS ON THE MAXIMUM MULTIPLICITY OF SOME COMMON GEOMETRIC GRAPHS [J].

Dumitrescu, Adrian ;

Schulz, Andre ;

Sheffer, Adam ;

Toth, Csaba D. .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) :802-826

[10] Two new bounds for the random-edge simplex-algorithm [J].

Gaertner, Bernd ;

Kaibel, Volker .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) :178-190

← 1 2 3 →