SMALL-DIMENSIONAL LINEAR-PROGRAMMING AND CONVEX HULLS MADE EASY

被引：130

作者：

SEIDEL, R ^{[1
]}

机构：

[1] PRINCETON UNIV,DIMACS,PRINCETON,NJ 08544

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1991年 / 6卷 / 05期

关键词：

D O I：

10.1007/BF02574699

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time O(m). The other constructs convex hulls of n points in R(d), d > 3, in expected time O(n[d/2]). In both bounds d is considered to be a constant. In the linear programming algorithm the dependence of the time bound on d is of the form d!. The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses.

引用

页码：423 / 434

页数：12

共 20 条

[1]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[2]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[3]

ARAGON CR, 1989, 30TH P ANN IEEE S F, P540

[4] AN ALGORITHM FOR CONVEX POLYTOPES [J].